求解信賴域子問題的Newton-GMRES方法

摘要：

為求解信賴域子問題，通過構造新的光滑函數將子問題的互補模型轉化成等價的方程組，將非精確牛頓法與GMRES算法相結合，得到求解信賴域子問題的NewtonGMRES算法，在一定條件下證明該算法的全局收斂性與適定性。數值實驗結果表明，該算法可行有效。

關鍵詞：

信賴域子問題；非精確牛頓法；光滑函數；全局收斂

中圖分類號：O221.2

文獻標志碼：A

NewtonGMRES" Method for Solving Trust Region Subproblems

YIN Wanru， RUI Shaoping

（School of Mathematical Sciences， Huaibei Normal University， Huaibei 235000， China）

Abstract：

In order to solve the trust region subproblem NewtonGMRES algorithm" was constructed with a new smooth approximation function， complementary model of subproblem was converted into an equivalent system of equations. The inexact Newton method was combined with the GMRES algorithm to obtain the NewtonGMRES algorithm for solving trust region subproblems. The convergence and wellposedness of the algorithm was proved under certain conditions. Numerical experimental results show that the algorithm is practicable and effective.

Keywords：

trust region subproblem; inexact Newton method; smooth function; global convergence

針對無約束優化問題

minx∈Rnfx（1）

其中，f：Rn→R是二次連續可微函數，信賴域算法具有較強的收斂性，是解決無約束優化問題的重要算法，實現的關鍵步驟就是子問題的求解。信賴域子問題是以二次函數為目標函數的約束優化問題，第k次迭代步的信賴域子問題形式

min qkd=gTkd+0.5dTBkd

s.t.‖d‖≤Δk（2）

記fk=f（xk），gk=SymbolQC@f（xk），Bk記為Hesse矩陣

信賴域子問題的求解策略對信賴域算法的數值計算效率具有直接影響[1]，求解方法主要包括折線法[24]、共軛梯度法[5]、牛頓法[6]等。這些方法各有優點和局限，例如，折線法在下降方向與牛頓方向偏離時，其收斂速度會減慢，而精確光滑牛頓法則需在迭代點接近最小值時才能確保收斂，計算成本較高。非精確牛頓法是內外層雙迭代算法，外層迭代使用經典牛頓法，內層迭代利用Krylov子空間進行求解，而NewtonGMRES方法是雙層迭代算法的代表，提高計算效率且節省時間成本，適用于解決規模較大的問題。本文在新光滑函數基礎上將信賴域子問題的互補模型轉化為光滑方程組，并使用NewtonGMRES算法求解，進而求解信賴域子問題。

1 基礎知識

通過引理1將信賴域子問題轉化為互補問題。

引理1[7] d是子問題（2）的解，當且僅當

Bk+λId－gk=0

s.t. λ≥0，Δ2k－‖d‖22≥0，λΔ2k－‖d‖22=0（3）

其中，Bk+λI是半定矩陣。

定義1[8] 如果對（a，b）∈R2，φ（a，b）=0當且僅當a≥0，b≥0，ab=0，那么函數φ：R2→R稱為互補函數。

目前應用最廣泛的是FischerBurmeister函數（FB互補函數）

φFB（a，b）=a+b－a2+b2，（a，b）∈R2（4）

由于FB互補函數在特定點不具備可微性，需要引入光滑參數對其光滑化處理，從而得到多種光滑互補函數。本文利用式（4），通過引入光滑參數[9]，構造一個新的光滑函數

φμ，a，b=1+sin μa+b－a+bsin μ2+asin μ+b2+2μ2（5）

下面證明式（5）的性質。

定理1 設（μ，a，b）∈R3，φ（μ，a，b）由式（5）定義，那么：

（a）φ（0，a，b）=0a≥0，b≥0，ab=0，即φμ，a，b是φ0，a，b的一個光滑函數；

（b）φμ，a，b是處處全局Lipschitz連續的，對（μ，a，b）∈R++×R×R，φ（μ，a，b）是連續可微的，雅可比矩陣為：

φ′μ，a，b=φ′μφ′aφ′b=a+bcos μ－a+bsin μbcos μ+b+asin μacos μ+2μa+bsin μ2+b+asin μ2+2μ21+sin μ－a+bsin μ+b+asin μsin μa+bsin μ2+b+asin μ2+2μ21+sin μ－a+bsin μsin μ+b+asin μa+bsin μ2+b+asin μ2+2μ2

證明：由φ（0，a，b）=φFB（a，b）可知，φ（0，a，b）=0a≥0，b≥0，ab=0。易知φ（μ，a，b）在任意點（μ，a，b）∈R++×R×R處連續可微，且

φ′μ（μ，a，b）=cos μ（a+b）－（a+sin μb）bcos μ+（b+sin μa）acos μ+2μ（a+sin μb）2+（b+sin μa）2+2μ2

φ′a（μ，a，b）=1+sin μ－（a+sin μb）+（b+asin μ）sin μ（a+sin μb）2+（b+sin μa）2+2μ2

φ′b（μ，a，b）=1+sin μ－（a+sin μb）sin μ+（b+sin μa）（a+sin μb）2+（b+sin μa）2+2μ2

下面對式（3）的非線性互補問題使用光滑函數（5）將其轉化為與其等價的光滑方程組。

令z=（μ，λ，d）∈R+×R+×Rn，問題（3）等價于

H（z）：=H（μ，λ，d）=μφ（μ，λ，Δ2k－‖d‖22）B+λId－gk=0（6）

其中

φ（μ，λ，Δ2k－‖d‖22）=1+sin μλ－‖d‖22+Δ2k－

λ+Δ2k－‖d‖22sin μ2+λsin μ+Δ2k－‖d‖222+2μ2 （7）

Hz在任意點z∈R+×R+×Rn是連續可微的，計算得到其Jacobi矩陣為

H′z=100φ′μφ′λφ′d0dBk+λI（8）

其中

φ′μ=（λ－‖d‖22+Δ2k）cos μ－L－1wLpΔ2k－‖d‖22cos μ+Lqλcos μ+2μ（9）

φ′λ=（1+sin μ）－L－1wLp+Lqsin μ（10）

φ′d=－2dΤ1+sin μ－L－1wLpsin μ+Lq（11）

其中，Lp=λ+Δ2k－‖d‖22sin μ，Lq=λsin μ+Δ2k－‖d‖22，Lw=L2p+L2q+2μ2。

2 非精確光滑牛頓算法及其收斂性

下面是求解信賴域子問題的NewtonGMRES具體算法。

算法1 求解信賴域子問題的非精確NewtonGMRES方法

Step 1 給定z0，ε0∈Rn，μ0gt;0，ηmax∈0，1，δ，σ∈0，1，選取γ∈0，1，使γμ0lt;1，令k：=0；

Step 2 如果‖Hzk‖gt;ε0

（1）選擇k∈0，ηmax；

（2）執行GNE過程：（a）選取Δz0k∈Rn，令r0k=－H（zk）－

SymbolQC@H（zk）Δzk‖；

Step 3 設定步長λk為1，δ，δ2，…中使下式成立的最大值：‖Hzk+λΔzk‖≤1－σ1－γμ0－ηkλk‖Hzk‖；

Step 4 令zk：=zk+λkΔzk并且k：=k+1，回到Step 1。

定理2 假設z=μ，λ，d∈R+×R+×Rn，Hz：=Hμ，λ，d=μφμ，λ，Δ2k－‖d‖22Bk+λId－gk=0，如果Bk是對稱正定矩陣，那么對任意的z=（μ，λ，d）∈R+×R+×Rn，其Jacobian矩陣H′（z）是可逆的，且算法1是適定的。

證明：任取μgt;0，令Δz=Δμ，Δλ，Δd∈R+×R+×Rn，下面只需驗證方程組

H′zΔz=0（12）

存在唯一零解，即Δz=0。根據式（8）和式（12）有Δμ=0，dΔλ+Bk+λIΔd=0

φ′μΔμ+φ′λΔλ+φ′dΔd=0（13）

由式（9）、式（10）、式（11）和式（13），得

1+sin μΔλ－2dΤΔdLw=LpΔλ+Lqsin μΔλ+Lp－2dΤsin μΔd+Lq－2dΤΔd

兩邊同時取極限，得

limμ→01+sin μΔλ－2dΤΔdLw=limμ→0［LpΔλ+Lqsin μΔλ+Lp－2dΤsin μΔd+Lq－2dΤΔd］

有Δλ－2dΤΔdλ2+Δ2k－‖d‖222=λΔλ+Δ2k－‖d‖22－2dΤΔd，從而

λ2+Δ2k－‖d‖222Δλ－2dΤλ2+Δ2k－‖d‖222Δd=λΔλ－2dΤΔ2k－‖d‖22Δd（14）

可知Δλ=0，Δd=0，所以H′z僅在Δμ=0，Δλ=0，Δd=0處為零，故Δz=Δμ，Δλ，Δd=0，即證明Jacobian矩陣H′z是可逆的，因此算法1是適定的。

定理3 若信賴域子問題的互補問題Hz是單調且連續可微的，zk為算法1所生成的迭代點列，而z*=μ*，x*，y*為迭代點列zk的一個聚點，則：

（1）z*=μ*，x*，y*是方程Hzk=0的一個解；

（2）若任意的V∈Hz*可逆，且H′z是Lipschitz連續，那么zk局部二階收斂于z*，即‖zk+1－z*‖=ο‖zk－z*‖2。

證明：證明與文獻[10]中定理4的證明類似，不再贅述。

3 數值實驗

在Matlab（R2018a）環境下利用數值實驗驗證算法1的可行性和有效性。采用NewtonGMRES算法求解信賴域子問題時，在不同的信賴域半徑下比較切線單折線法[5]和分段切線算法[11]的數值實驗結果，數值越小說明所對應的算法越好。圖表中NewtonGMRES方法對應的函數值為qFNGM，切線單折線法對應的函數值為qTDL，分段切線算法對應的函數值為qSTL，qTDL－qFNGM以及qSTL－qFNGM表示使用兩種方法函數值的差，差值越大說明算法結果可行有效。

變量的維數記作n，采用的信賴域半徑記作Δ，cpu為多次測試的時間平均值，單位為秒（s）。在測試中，算法的停機標準為‖gk‖≤10－6或迭代次數kgt;50，參數取值：γ=005，ε=10－6，ρ=06，σ=02，μ0=005，λ0=005，ηk=12k+1。

算例1[5]：min qd=－10－10Td+12dT1005d，s.t.‖d‖2≤Δ。

算例2[11]：min qd=100－50020－500Td+12dT80－1000－101000300030100－1000－1050d，s.t.‖d‖2≤Δ。

由表1與表2的數值實驗結果可以看出，FNGM方法的函數值明顯小于另外兩種方法，說明該方法的函數值更接近于最優值，即NewtonGMRES算法相比于切線單折線法與分段切線法在算例1和算例2中計算結果較好，更適用于求解信賴域子問題。

下列測試函數均來自于無約束優化測試函數集[12]。

算例3（Perturbed Quadratic Diagonal Function）：f（x）=∑ni=1xi2+∑ni=1i100x2i，x0=［05，05，…，05］，其子問題為min qk（d）=gΤkd+05dΤkBkd，s.t.‖d‖≤Δk，其中

gk=2×∑ni=1xi+i50x12×∑ni=1xi+i50x22×∑ni=1xi+i50xn，Bk=2+1502…222+250…222…2+n50

算例4（Extend Quadratic Penalty QP1 Function）：f（x）=∑ni=1（x2i－2）2+（∑ni=1（x2i－0.5））2，x0=［1，1，…，1］，其子問題為min qkd=gTkd+0.5dTkBkd，s.t.‖d‖≤Δk，其中

gk=4x1x21－2+∑ni=1x2i－0.54x2x22－2+∑ni=1x2i－0.54xnx2n－2+∑ni=1xni－0.5，

Bk=20x21－8+4S8x1x2…8x1xn8x2x120x12－8+4S…8x2xn8xnx18xnx2…20x2n－8+4S

由表3的數據實驗結果可知，在不同的信賴域半徑下，算例3和算例4所需迭代次數k和cpu運算時間較少，計算成本降低。隨著n增大，k變化不大，進一步驗證算法1穩定可靠，同時說明NewtonGMRES算法求解較大規模的信賴域子問題可行有效。

算例5：f（x）=∑n－1i=1xi2－xi+12，x0=［1，0，…，1，0］。

對于大規模的信賴域子問題，在不同維數下對比NewtonGMRES法與共軛梯度法[1314]，通過比較梯度值的k和cpu，說明算法的可行性。共軛梯度法用RTPCGT表示，NewtonGMRES法用FNGM表示，信賴域半徑Δmax=1。由表4的數值實驗結果可知，當n較大時NewtonGMRES方法的迭代次數和共軛梯度法相比明顯較少，節省計算成本。

4 結論

針對信賴域子問題，在將其互補模型轉化為等價方程組時提供了一個光滑函數的新選擇，初步數值實驗表明，NewtonGMRES方法不僅對低維數的信賴域子問題求解效果良好，對求解維數較高的信賴域子問題也是穩定可行的。

參考文獻

[1]范曉宇， 李丹琳， 王希云. 求解信賴域子問題的Adams四階預報校正格式算法[J]. 太原科技大學學報， 2021， 42（1）： 7378.

[2]趙英良， 徐成賢. 信賴域子問題使用重新開始策略的共軛梯度法[J]. 高校應用數學學報A輯（中文版）， 2003（3）： 341349.

[3]趙丹. 求解信賴域子問題的混合雙割線折線法[J]. 江蘇教育學院學報（自然科學）， 2013， 29（2）： 1416.

[4]王希云， 邵安. 一種雙割線折線法求解信賴域子問題[J]. 應用數學， 2012， 25（2）： 419424.

[5]趙英良， 徐成賢. 解信賴域子問題的切線單折線法[J]. 數值計算與計算機應用， 2000（1）： 7780.

[6]陳爭， 馬昌鳳. 求解信賴域子問題的一個光滑牛頓法[J]. 福建師范大學學報（自然科學版）， 2011， 27（4）： 3135.

[7]馬昌鳳. 最優化計算方法及其 Matlab 程序實現[M]. 北京：科學出版社， 2010.

[8]CHEN J S， PAN S. A family of NCP functions and a descent method for the nonlinear complementarity problem[J]. Computational Optimization and Applications， 2008， 40： 389404.

[9]TANG J， HE G， DONG L， et al. A new onestep smoothing Newton method for secondorder cone programming[J]. Applications of Mathematics， 2012， 57（4）： 311331.

[10] 張運勝， 高雷阜. 對稱錐互補問題的一種非精確光滑牛頓算法[J]. 數學物理學報， 2015， 35（4）： 824832.

[11] 王希云， 李亮， 張雅琦， 等. 一種求解二次函數模型信賴域子問題的分段切線算法[J]. 應用數學， 2015， 28（1）： 2632.

[12] ANDREI N. An unconstrained optimization test functions collection[J]. Advanced Modeling and Optimization， 2008， 10（1）： 147161.

[13] 袁遠. 信賴域子問題求解方法及其數值試驗研究[J]. 大理大學學報， 2022， 7（6）： 18.

[14] 楊郁， 王希云. 基于信賴域子問題的共軛梯度法[J]. 太原科技大學學報， 2010， 31（6）： 481484.