非線性互補問題的光滑化擬牛頓算法

牛瀟萌

赤峰學院 數學與統計學院，內蒙古 赤峰 024000

非線性互補問題的光滑化擬牛頓算法

牛瀟萌

赤峰學院 數學與統計學院，內蒙古 赤峰 024000

1 引言

設F:Rn→Rn是一非線性映射，非線性互補問題（簡記為NCP（F））是指：求一個向量x∈Rn，使得：

非線性互補問題在很多領域都有重要應用[1-3]，其理論和算法的研究在近些年來得到了長足發展[1]。很多求解NCP（F）的有效算法已被提出[3]，其中比較流行的方法之一是首先把NCP（F）轉化成一個非線性方程組H(x)=0，然后利用求解方程組的相關方法[4]間接求解得到NCP（F）的解。牛頓型方法是求解非線性互補問題的一類重要的數值迭代算法，其局部收斂性的研究取得了很好的成果[1]。近些年來，此類算法的全局收斂性研究也得到了諸多進展[5-9]。然而對于計算上更為實用的擬牛頓算法的研究相對較少。其主要困難在于即使對于光滑的非線性方程組，擬牛頓法產生的方向不能保證是某個度量函數的下降方向，常用的線搜索（如Armijo型線搜索）此時已不適用[10]。另外對擬牛頓法來說，那些需要計算導數的線搜索是不適合的。因此，為了得到求解非線性方程組的擬牛頓法的全局收斂性，需要一個無導數線搜索（Derivative-Free Line Search）。

1986 年，Griwank[11]首先提出了一種無導數線搜索，并證明了求解非線性方程組的Broyden秩一校正方法在該線搜索下的全局收斂性，但此線搜索在某些情況下，可能不能實現[12]。Li和Fukushima在文獻[12]中，針對文獻[11]中無導數線搜索的不足，提出了一個新的易于實現的無導數線搜索。

2 光滑對稱擾動Fischer-Burmeister函數

使用如下光滑函數[13]：

其中(μ，a，b)∈R3，它是通過光滑化對稱擾動的Fischer-Burmeister函數：

而得到的。

設z=(μ，x)∈Rn+1且

其中：

易知H(z)=0?μ=0，x是NCP（F）的解。

H(z)的Jacobian矩陣為：

3 光滑化擬牛頓算法

設γ∈(0，1)。定義函數ρ:Rn+1→R+為：

算法：

步驟1選擇常數設，任取初始點x0∈Rn。設z0= (μ0，x0)。選擇γ∈(0，1)，使得γμ0＜1。設η＞0是一個給定常數并選擇一正數列{ηk}滿足：

選一個初始非奇異矩陣B0∈Rn×n。設k=0。

步驟2若‖H(zk)‖=0，停。否則，設ρk:=ρ(zk)。若μk＞ρkμ0，解下面的方程得Dzk=(Dμk，Dxk)。

否則，令Dzk=(Dμk，Dxk):=(0，Dxk)，并解如下方程組得Dxk，

其中Gk∈R(n+1)×(n+1)定義為：

且Bk是?xΦ(zk)T的一個近似。

步驟3若

則設λk:=1，轉步驟5。

步驟4設λk是取自集合{1，δ，δ2，…}使得λ=δi滿足如下線搜索的最大數：

步驟5

步驟6用如下Broyden-like校正公式修正Bk得Bk+1：

其中sk=λkDxk=xk+1-xk，yk=Φ(μk，xk+1)-Φ(μk，xk)，參數θk滿足且Bk+1非奇異。

步驟7令k=k+1，轉步驟2。

對算法的說明：

由方程（6）求Dzk分兩步：首先由下面的方程求Dμk：

然后解如下線性方程組求Dxk：

定理1算法是有定義的，且產生一無窮序列{zk=(μk,xk)}滿足{μk}?R++是單調非增的。

證明由Bk非奇異知Gk+1非奇異，因此線性方程組（6）和（7）唯一可解。易知對充分小的λ＞0，不等式（10）成立。事實上，當λ→0時，式（10）的左邊趨于‖H(zk)‖，但右邊趨于(1+ηk)‖H(zk)‖。因此算法是有定義的。

下面用歸納法證明{μk}?R++。因為μ0＞0，假設μk＞0，則‖H(zk)‖≠0，從而：

如果μk＞ρkμ0，由式（11）和λk∈(0，1]知：

如果μk≤ρkμ0，由算法步驟2可知此時如果Dμk=0，從而μk+1=μk＞0。所以{μk}?R++。故算法產生一無窮序列。

下面證明{μk}是單調非增序列。

事實上，如果μk＞ρkμ0，由式（11）知Dμk＜0，從而μk+1=μk+λkDμk＜μk。

如果μk≤ρkμ0，由算法步驟2可知Dμk=0從而μk+1=μk。

所以{μk}是單調非增序列。

4 數值實驗結果

算法中相關參數取α=0.9，δ=0.9，σ1=0.8，μ0=10-3，γ= 0.2，η=0.5。程序中取ε=10-6為結束準則，當‖H(zk)‖ ≤ε時終止。

算例1（Josephy問題[14]）求解如下4維非線性互補問題NCP（F），其中F(x)定義如下：

表1 算例1的計算結果

算例2（Murty問題[15]）這是一組n維線性互補問題，設F(x)=Μx+q，n階方陣M和n維向量q定義如下：

唯一解x*=(0，…，0，1)T。

取初始點x0=(0，…，0)T，計算結果見表2。

表2 算例2的計算結果

算例3（Kojshin問題[14]）求解如下非線性互補問題NCP（F），其中F(x)定義如下：

表3 算例3的計算結果

5 結論

基于光滑對稱擾動函數并利用無導數線搜索給出了求解P0函數非線性互補問題的光滑化擬牛頓算法。數值結果表明該算法有效，可靠。

[1]Harker P T，Pang J S.Finite-dimensional variational inequality and nonlinear complementarity problems：a survey of theory，algorithms and applications[J].Mathematical Programming，1990，48：161-220.

[2]Ferris M C，Pang J S，Engineering and economic applications of complementarity problems[J].SIAM Review，1997，39：669-713.

[3]韓繼業，修乃華，戚厚鐸.非線性互補理論與算法[M].上海：上海科學技術出版社，2006.

[4]Dennis J E，Schnabel R B.Numerical methods for unconstrained optimization and nonlinear equations[M].Englewood Cliffs：Prentice-Hall，1983.

[5]Pang J S，Chen D.Iterative methods for variational and complementarity problems[J].Mathematical Programming，1982，24：284-313.

[6]Chen C，Manasarian O L.A class of smoothing functions for nonlinear and mixed complementarity problems[J].Comput Optim Appl，1996，5：97-138.

[7]Jiang H Y，Qi L Q.A new nonsmooth equations approach to nonlinear complementarity problems[J].SIAM J Control Optim，1997，35：178-193.

[8]Chen X，Qi L，Sun D.Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities[J].Mathematics of Computation，1998，67：519-540.

[9]Qi L Q，Chen X J.A globally convergent successive approximation method for severely nonsmooth equations[J].SIAM J Control Optim，1995，33：402-418.

[10]Li D H，Fukushima M.A globally and superlinearly convergence Gauss-Newton-based BFGS method for symmetric nonlinear equations[J].SIAM Numer Anal，1999，37：152-172.

[11]Griewank A.The“global”convergence of Broyden-like methods with a suitable line search[J].Journal of Australia Mathematical Society Ser.B，1986，28：75-92.

[12]Li D H，Fukushima M.A derivative-free line search and global convergence Broyden-like method for nonlinear equations[J].Optimization Methods and Software，2000，13：181-201.

[13]Huang Z，Han J，Xu D，et al.The non-interior continuation methods for solving theP0-function nonlinear complementarity problem[J].Science in China，2001，44：1107-1114.

[14]Dirkse S P，Ferris M C.MCPLIB：a collection of nonlinear mixed complementarity problems[J].Optimization Methods and Software，1997，5：123-156.

[15]Kanzow C.Some noninterior continuation methods for linear complementarity problems[J].SIAM Journal on Matrix Analysis and Applications，1996，17：851-868.

NIU Xiaomeng

School of Mathematics and Statistics,Chifeng University,Chifeng,Inner Mongolia 024000,China

To solve nonlinear complementarity problem,a new smoothing quasi-newton algorithm based on the smoothing symmetric perturbed Fischer-Burmeister function is put forward.The algorithm makes use of the derivative-free line search rule.Numerical results indicate this algorithm is efficient.

nonlinear complementarity problem;quasi-newton algorithm;smoothing approximation

為求解非線性互補問題，給出了一種新的基于光滑對稱擾動Fischer-Burmeister函數的光滑化擬牛頓算法。該算法利用了無導數線搜索。數值實驗表明，算法是有效的。

非線性互補問題；擬牛頓算法；光滑逼近

A

O224

10.3778/j.issn.1002-8331.1205-0118

NIU Xiaomeng.Smoothing quasi-newton for nonlinear complementarity problem.Computer Engineering and Applications, 2013,49（18）：33-35.

牛瀟萌（1982—），女，講師，研究領域為最優化。E-mail：ndnxm@126.com

2012-05-16

2012-07-16

1002-8331（2013）18-0033-03

CNKI出版日期：2012-08-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120816.1045.010.html