凌文靜，芮紹平

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

0 引言

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

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

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

1 基礎(chǔ)知識

通過下述引理將求解信賴域子問題（1）轉(zhuǎn)化為求解互補(bǔ)問題.

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

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

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

定義2［9］滿足以下三條性質(zhì)的函數(shù)稱為V上的范數(shù)‖·‖: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］對于非光滑函數(shù)g:Rn→Rm，含有參數(shù)μ的函數(shù)gμ:Rn→Rm滿足下列性質(zhì)

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

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

定義5［10-11］設(shè)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時稱為強(qiáng)半光滑.

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

2 光滑函數(shù)及性質(zhì)

一個經(jīng)典的光滑函數(shù)是著名的Chen-Harker-Kanzow-Smale（CHKS）光滑函數(shù)［13］，即

本文中構(gòu)造函數(shù)φ:R+×R×R→R：

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

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

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

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

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

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

不妨設(shè)a＞b，對任意μ＞0，有

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

即

由式（7）有

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

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

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

其中

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

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

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

步驟0任取z0=(μ0,λ0,d0)∈R+×R+×Rn，選取常數(shù)δ∈(0,1)，σ∈(0,1)，γ∈(0,1)，使得γμ0＜1，另取序列{ηk}滿足ηk∈[0,η]，這里為一個常數(shù)，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.假設(shè)

只需要證Δ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適定性的證明與參考文獻(xiàn)［10］中的證明類似，在此不再贅述.

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

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

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

證明與文獻(xiàn)［8］中定理4證明類似.

4 數(shù)值實驗

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

測試函數(shù)均來自于文獻(xiàn)［15］，如下：

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

表1 Function1與雙割線折線法的數(shù)值結(jié)果

表2 Function2與雙割線折線法的數(shù)值結(jié)果

表3 部分Δ下運行的結(jié)果