信賴域子問題的一種非精確光滑牛頓法

凌文靜，芮紹平

（淮北師范大學 數學科學學院，安徽 淮北 235000）

0 引言

信賴域方法最早由Powell［1］提出，因其具有較為理想的全局收斂性和穩(wěn)定性備受廣大學者的青睞.信賴域算法的基本思想是：在給定的信賴域半徑內，以當前迭代點為中心做一個閉球區(qū)域，在此區(qū)域內求解信賴域子問題來確定迭代步dk，產生新的迭代點.也就是說在每次迭代時都需要求解信賴域子問題，所以信賴域方法中信賴域子問題的求解是算法實現的關鍵.考慮信賴域子問題

其中gk=?f(xk)，Bk為Hesse矩陣?2f(xk)的第k次近似，Δk為信賴域半徑，‖‖·是Euclidean范數.

常見求解信賴域子問題的方法是折線法［2］、特征值分解法［2］、共軛梯度法［3-5］以及精確光滑牛頓法［6］等，這些方法各有優(yōu)點和不足，如特征值分解法對于二維或低維子空間問題算法有效，折線法當下降方向不靠近牛頓方向時下降速度較慢，精確光滑牛頓法需要在迭代點靠近最小值時才能保證收斂性等.本文提出一種求解信賴域子問題的非精確光滑牛頓法，當Hesse矩陣?2f(xk)的第k次近似矩陣Bk為對稱正定矩陣時，該方法具有迭代次數少、迭代時間快等特點，還可推廣到求解高維子空間的信賴域子問題.受文獻［7-8］光滑函數的啟發(fā)，本文提出一個新的光滑互補函數，在此基礎上，應用非精確牛頓法求解信賴域子問題.

1 基礎知識

通過下述引理將求解信賴域子問題（1）轉化為求解互補問題.

引理1［9］d是子問題（1）的解當且僅當

并且Bk+λI是半定矩陣.

定義1［9］設向量值函數F:Rn→Rm，x∈Rn，若存在Lipschitz常數L＞0，使得對任意的y∈Rn，滿足‖F(x)-F(y)‖≤L‖x-y‖，則稱F在x處是Lipschitz連續(xù)的.若對任意的x,y∈Rn都成立，則稱F在Rn內是全局Lipschitz連續(xù)的.

定義2［9］滿足以下三條性質的函數稱為V上的范數‖·‖:V→R

（1）正定性：‖x‖≥0,?x∈V且‖x‖=0?x=0；

（2）正齊次性：‖αx‖=|α|‖x‖,?α∈R,?x∈V；

（3）三角不等式：‖x+y‖≤‖x‖+‖y‖,?x,y∈V.

定義3［8］對于非光滑函數g:Rn→Rm，含有參數μ的函數gμ:Rn→Rm滿足下列性質

（1）對于任意的μ＞0，gμ是可微的；

定義4［9］設算法產生的點列{xk}收斂于極小點x*，并且，則稱該算法是局部二次收斂的.

定義5［10-11］設H:Rn→Rm是局部Lipschitz連續(xù)的，0＜p≤1.如果對?h→0和D∈?H(x+h)，有Dh-H′(x;h)=O(‖‖h1+p)，則稱H是p-階半光滑，特別是p=1時稱為強半光滑.

引理2［12］假設函數F:Rn→Rm在x處是p-階半光滑，函數G:Rm→Rn在F(x)處是p-階半光滑，則復合函數H=G?F在x處是p-階半光滑.

2 光滑函數及性質

一個經典的光滑函數是著名的Chen-Harker-Kanzow-Smale（CHKS）光滑函數［13］，即

本文中構造函數φ:R+×R×R→R：

定理1令(μ,a,b)∈R+×R×R，φ(μ,a,b)由式（3）定義，則下述結論成立

（i）φ(μ,a,b)是φ(0,a,b)的一個光滑函數；

（ii）φ是全局Lipschitz連續(xù)且當μ＞0時強半光滑，φ在(μ,a,b)∈R+×R×R是連續(xù)可微的，且其雅可比矩陣為

證明（i）令，則式（3）可寫成φ:=(1+μ)(a+b)-K.對K求偏導有，

則 對 于 任 意μ＞0，K(w)的 偏 導 在 任 意(μ,a,b)∈R+×R×R都 存 在，φ(μ,a,b)的 偏 導 在 任 意(μ,a,b)∈R+×R×R也存在，于是φ(μ,a,b)在定義域內每一點都可微，又，則由定義3可知，φ(μ,a,b)是φ(0,a,b)的一個光滑函數.

（ii）先證明φ是全局Lipschitz連續(xù)的.

不妨設a＞b，對任意μ＞0，有

對?(μ,a1,b1),(μ,a2,b2)∈R+×R×R，結合式（5）～（6）有

即

由式（7）有

由（i）知，φ在點(μ,a,b)∈R+×R×R連續(xù)可微，注意到φ(μ,a,b)=φCHKS(μ,(1+μ)a,(1+μ)b)，由文獻［14］可知，當μ＞0時，φCHKS是強光滑的，又函數(1+μ)a和(1+μ)b也是強半光滑的，由引理2知φ是強半光滑的.

下證式（4）成立.對于任意z=(μ,a,b)∈R+×R×R，通過式（5）及求微分的鏈式法則可知

即式（4）成立.令z=(μ,λ,d)∈R+×R+×Rn.由引理1可知問題（1）等價于

其中

3 非精確光滑牛頓法及收斂性

基于光滑函數（3），將信賴域子問題的互補模型（2）轉化為等價方程組式（8），給出求解信賴域子問題的非精確光滑牛頓法.

算法3.1（非精確光滑牛頓法）

步驟0任取z0=(μ0,λ0,d0)∈R+×R+×Rn，選取常數δ∈(0,1)，σ∈(0,1)，γ∈(0,1)，使得γμ0＜1，另取序列{ηk}滿足ηk∈[0,η]，這里為一個常數，k:=0.

步驟1若‖H(zk)‖=0，則終止.

步驟2由下式計算Δzk=(Δμk,Δλk,Δdk)：

這里βk=β(zk):=γ‖H(zk)‖min{1,‖H(zk)‖}，rk∈Rn滿足‖rk‖≤ηk‖H(zk)‖.

步驟3讓λk為1,δ,δ2,…中使下式成立的最大值：

步驟4令zk+1:=zk+λkΔzk，k:=k+1，返回步驟1.

定理2令若Bk對稱正定，則對

任意的z=(μ,λ,d)∈R+×R+×Rn,雅可比矩陣H′(z)是非奇異的，且算法3.1中的步驟2和步驟3是適定的.

證明任取μ＞0，令Δz=(Δμ,Δλ,Δd)∈R+×R+×Rn.假設

只需要證Δz=0.

由式（9）、式（10）可得

于是-(1-θk)(Bk+λI)Δd=2(1+θk)ddTΔd.若Δd≠0，則-(1-θk)ΔdT(Bk+λI)Δd=2(1+θk)(dTΔd)2，由于0＜θk＜1，Bk+λI半正定，等式左邊小于0，等式右邊大于0，等式兩邊不相等，矛盾.于是Δd=0，從而Δλ=0，故Δz=(Δμ,Δλ,Δd)=( 0,0,0).即證雅可比矩陣H′(z)是非奇異的.步驟2和步驟3適定性的證明與參考文獻［10］中的證明類似，在此不再贅述.

定理3［8］設函數H單調連續(xù)可微，且z*=(μ*,x*,y*)是算法3.1所產生的迭代點列{zk}的一個聚點，則

（i）z*=(μ*,x*,y*)是H(zk)=0的一個解；

（ii）如 果 所 有 的V∈?H(z*)可 逆，且?HLipschitz連 續(xù)，則{zk}局 部 二 階 收 斂 于z*，即

證明與文獻［8］中定理4證明類似.

4 數值實驗

針對無約束優(yōu)化的信賴域子問題（1），本節(jié)對不同的信賴域半徑，給出算法3.1的數值結果，并與雙割線折線法［15］進行數值比較，比較結果列在表1和表2中，其中Δ表示信賴域半徑，qk(d)表示函數值，DSD表示雙割線折線法，ISN表示非精確光滑牛頓法，qDSD-qISN表示使用雙割線折線法與非精確光滑牛頓法得到的最優(yōu)解的差值，該差值越大，表明非精確光滑牛頓法越好.為進一步觀察非精確光滑牛頓法的性能，表3列出部分Δ下迭代次數k與CPU時間（單位：s），其中CPU時間和迭代次數均是多次求解后的平均值.算法中參數取值為：

測試函數均來自于文獻［15］，如下：

從表1、表2和表3結果可以看出，本文所設計的算法穩(wěn)定可靠，且當信賴域半徑較?。ㄆ渲蠪unction1：Δ≤9，Function2：Δ≤4.）時非精確光滑牛頓法（ISN）比雙割線折線法（DSD）更接近精確解，所需迭代次數和CPU時間很少，說明文中所設計的算法適合求解信賴域子問題.

表1 Function1與雙割線折線法的數值結果

表2 Function2與雙割線折線法的數值結果

表3 部分Δ下運行的結果