孫菊賀，紀(jì)東辰,王 琪

(沈陽(yáng)航空航天大學(xué) 理學(xué)院，沈陽(yáng) 110136)

?

求解非線性互補(bǔ)問(wèn)題的一類光滑牛頓算法

孫菊賀，紀(jì)東辰,王 琪

(沈陽(yáng)航空航天大學(xué) 理學(xué)院，沈陽(yáng) 110136)

主要研究一類光滑函數(shù)法求解非線性互補(bǔ)問(wèn)題?；贔ischer-Burmeister(FB)互補(bǔ)函數(shù)的光滑形式，將非線性互補(bǔ)問(wèn)題轉(zhuǎn)化為一類光滑的非線性方程組問(wèn)題。為了求解該光滑非線性方程組問(wèn)題，提出一類的全局收斂光滑牛頓算法。討論了方程算子的雅克比矩陣的非奇異性。應(yīng)用所提出的牛頓方法求解一類互補(bǔ)問(wèn)題，得到相應(yīng)的數(shù)值結(jié)果。

非線性互補(bǔ)問(wèn)題;互補(bǔ)函數(shù);光滑牛頓法;非光滑性;收斂性

非線性互補(bǔ)問(wèn)題(NCP)是指：求矢量x∈Rn，使其滿足

x≥0,F(x)≥0,xTF(x)=0

(1)

其中F:Rn→Rn是連續(xù)可微的。

變分不等式和非線性互補(bǔ)問(wèn)題(NCP)起源于20世紀(jì)60年代。到20世紀(jì)80年代變分不等式和非線性互補(bǔ)問(wèn)題在數(shù)學(xué)規(guī)劃領(lǐng)域中已經(jīng)發(fā)展到一個(gè)卓有成效的學(xué)科，并將其應(yīng)用到了工程學(xué)、經(jīng)濟(jì)學(xué)、物理學(xué)等重要領(lǐng)域中。

1 預(yù)備知識(shí)

定義 1.1 設(shè)φ：R2→R為二元函數(shù)且滿足

φ(a,b)=0?a≥0,b≥0,ab=0

(2)

則二元函數(shù)φ稱為非線性互補(bǔ)(NCP)函數(shù)。

所謂的FB函數(shù)是指

φFB(a,b)=(a2+b2)1/2-(a+b)

(3)

易得FB函數(shù)(3)是一類NCP函數(shù)且在原點(diǎn)處是不可微的。因此我們給出下面的光滑的FB函數(shù)

(4)

顯然，當(dāng)u>0時(shí)，φu(a,b)是連續(xù)可微的。

下面欲將非線性互補(bǔ)問(wèn)題(1)轉(zhuǎn)化為方程問(wèn)題。先給出以下假設(shè)。

假設(shè)1.1 函數(shù)A：R→R連續(xù)可微，并且設(shè)A(u)滿足以下3個(gè)條件：

(1)A′(u)>0對(duì)所有u∈R成立；

(2)A(u)有唯一零點(diǎn)u=0；

令

(5)

定義效益函數(shù)ψu(yù);Rn→R+：

(6)

應(yīng)用光滑函數(shù)(4)可以將(1)轉(zhuǎn)化成下面非線性方程組問(wèn)題：

(7)

其中z=(u,x)∈Rn+1,A:R→R滿足假設(shè)1.1。令

(8)

則(1)等價(jià)于下面最小值問(wèn)題:

(9)

注1.1 假設(shè)1.1對(duì)于下一部分的算法起著關(guān)鍵性的作用。根據(jù)假設(shè)1.1中的(1)可以得出H(u,x)的半光滑性；根據(jù)假設(shè)1.1中的(2)可以得出H(u,x)=0必然u=0；根據(jù)假設(shè)1.1中的(3)可以得出Δu<0，并且對(duì)t∈[0,1]，u+tΔu>0，這意味著在下一部分的算法中迭代點(diǎn)列{uk}是遞減的并且對(duì)于全部的k,uk>0。

下面的性質(zhì)將在下一部分算法的收斂性證明中用到。

證明 很明顯Γ(x)在(0,a)上連續(xù)可微，并且有

(10)

所以，Γ(x)在(0,a)上嚴(yán)格遞增。

性質(zhì)1.2 對(duì)于u1,u2≥0,x∈Rn，映射Φu滿足以下不等式

(11)

性質(zhì)1.3 H(u,x)在u>0時(shí)連續(xù)可微，其Jacobin矩陣有如下形式：

(12)

其中C∈Rn,D和E都是Rn×n中的對(duì)角矩陣，并且滿足

(13)

并且

(14)

2 光滑牛頓算法及其全局收斂性

我們提出了一類牛頓算法求解非線性方程組H(z)=0。這種算法包含牛頓步和梯度步，在沒(méi)有F是單調(diào)的或是P0的條件下，該算法也是有效的。另外，在牛頓方程是不可解的時(shí)候，我們采用最速下降方向，這不同于經(jīng)典的Armijo線搜索。

算法2.1

步驟2 (牛頓步)求解線性方程組

JH′(zk)Δz=-H(zk)

(15)

得到解Δzk∈Rn+1。設(shè)mk是{0,1,2,…,lmax}中滿足下式的最小非負(fù)整數(shù):

f(zk+λmkΔzk)≤(1-2σλmk)f(zk)

(16)

計(jì)算tk=λmk,zk+1=zk+tkΔzk,βk+1=βk.令k←k+1，轉(zhuǎn)到步驟1。

Δxk=-Ψ(xk)

(17)

Ψ(xk+λmkΔxk)≤Ψ(xk)-σλmk‖Δxk‖2

(18)

令tk=λmk,xk+1=xk+tkΔxk，轉(zhuǎn)步驟4；

步驟4 如果下式成立

(19)

則令βk+1=‖Φ(xk+1)‖，并取uk+1:

(20)

如果(19)式不成立，那么令βk+1=βk，并取uk+1：

(21)

令zk+1=(uk+1,xk+1),k←k+1,轉(zhuǎn)步驟1。

注2.1

(2)如果牛頓方程JH(zk)Δz=-H(zk)有解，設(shè)為Δzk，那么

即Δzk是效益函數(shù)f(z)在zk處的一個(gè)下降方向。

(3)如果線性方程組(15)無(wú)解或{0,1,2,…,lmax}中不存在mk滿足(16)式，本部分最速下降方向負(fù)梯度-Ψ(x)為搜索方向，并采用經(jīng)典的Armijo線搜索(18)進(jìn)行搜索。此時(shí)，uk是一個(gè)光滑因子，uk+1的選取方法分成了(20)和(21)兩種情況。

接下來(lái)，取A(u)=eu+u-1，給出下面的性質(zhì)和定理。

(2)首先，利用數(shù)學(xué)歸納法容易證明如下結(jié)論：對(duì)x≥y≥0,m為正整數(shù)，有

xm-ym≤(x-y)(x+y)m-1，又有

(eu1+u1-1)2-(eu2+u2-1)2=(eu1+eu2+u1+u2-2)(eu1+u1-eu2-u2)

(22)

其中

類似可以得到 (eu1+u1-eu2-u2)≤2e2u1(u1-u2)。完成證明。

注2.2 為了后續(xù)工作的方便，在性質(zhì)2.1中取4u1。

定理2.1 對(duì)任何k≥0，如果zk=(uk,xk)∈R++×Rn并且步驟1的終止準(zhǔn)則不成立，那么由算法產(chǎn)生序列zk+1=(uk+1,xk+1)∈R++×Rn。

證明 根據(jù)算法說(shuō)明4易知uk+1>0，即(uk+1,xk+1)∈R++×Rn。

引理2.1 如果第k步采用牛頓步，那么uk+1≤(1-λlmaxe-u0)uk。

uk+λmk(-uke-uk)=uk(1-λmke-uk)≤uk(1-λlmaxe-u0)

結(jié)合式(20)和式(21)，我們得到有以下結(jié)論。

‖Φuk+1(xk+1)‖+c1uk+1≤‖Φuk(xk)‖+c1uk。 證明 由引理2.1可知，uk+1≤c0uk，再由性質(zhì)1.1

另一方面，由式(16)，我們有

‖Φuk+1(xk+1)‖2+(euk+1+uk+1-1)2≤‖Φuk(xk)‖2+(euk+uk-1)2

并且

進(jìn)而

所以有

‖Φuk+1(xk+1)‖+c1uk+1≤‖Φuk(xk)‖+c1uk。

完成證明。

證明 根據(jù)式(18)，有‖Φ(xk+1)‖<‖Φ(xk)‖，即‖Φ(xk)‖-‖Φ(xk+1)‖>0。由性質(zhì)1.2，推出

‖Φuk+1(xk+1)‖≤‖Φuk+1(xk+1)-Φ(xk+1)‖+‖Φ(xk+1)‖≤cuk+1+‖Φ(xk+1)‖=

cuk+1+‖Φ(xk)‖-(‖Φ(xk)‖-‖Φ(xk+1)‖)≤

cuk+1+‖Φuk+1(xk)‖+(‖Φ(xk)‖-‖Φuk+1(xk)‖)-(‖Φ(xk)‖-‖Φ(xk+1)‖)≤

2cuk+1+‖Φuk+1(xk)‖-(‖Φ(xk)‖-‖Φ(xk+1)‖)

根據(jù)(21)得‖Φ(xk)‖-‖Φ(xk+1)‖≥2cuk+1，于是有‖Φuk+1(xk+1)‖≤‖Φuk+1(xk)‖且

‖Φuk+1(xk)‖≤‖Φuk(xk)‖+‖Φuk+1(xk)-Φuk(xk)‖≤‖Φuk(xk)‖+c(uk-uk+1)

即是‖Φuk+1(xk)‖+cuk+1≤‖Φuk(xk)‖+cuk。因此

‖Φuk+1(xk+1)‖+cuk+1≤‖Φuk+1(xk+1)‖+cuk+1≤‖Φuk(xk)‖+cuk

完成證明。

推論2.2 對(duì)k≥0，如果(19)不成立，那么

我們給出兩個(gè)標(biāo)集：

L={k∈N|第k-1步采用了梯度步}

引理2.4 假設(shè)集合K由0=k0

從(1)到(2)，對(duì)kj∈K，總有βkj≤rβkj-1,j=1,2,…，進(jìn)而βkj≤rjβ0=rj‖Φ(x0)‖。

完成證明。

證明 任意給定k∈N，記kj為集合K中滿足kj

首先證明下面的不等式成立：

(23)

分兩種情況：(1)如果kj=k，則‖Φ(xk)‖=‖Φ(xkj)‖=βkj,(23)式顯然成立。

(2)如果kj≠k，即kj

結(jié)合性質(zhì)1.2，有

由引理2.4，

即xk∈L0。完成證明。

推論2.3 設(shè)算法2.1產(chǎn)生的點(diǎn)列為{zk=(uk,xk)}，那么任給k，有

證明 對(duì)k∈N,uk≤u0，那么我們有

引理2.5 設(shè)算法2.1產(chǎn)生的點(diǎn)列為{zk=(uk,xk)}，假設(shè)下標(biāo)集K為無(wú)限集，則點(diǎn)列{xk}的任一極限點(diǎn)都是NCP問(wèn)題的一個(gè)解。

引理2.6 設(shè)算法2.1產(chǎn)生的點(diǎn)列為{zk=(uk,xk)}，{xk}L1是其子序列且以x*∈Rn為極限點(diǎn)，如果?k∈L1，第k次迭代采用梯度步，那么x*是Ψ的一個(gè)穩(wěn)定點(diǎn)。

并且

下面用反證法來(lái)證明x*是Ψ(x)的穩(wěn)定點(diǎn)。若不然，則Ψ(x*)≠0。首先證明。假如,由于對(duì)k∈L1,Δxk=-Ψ(xk)由(17)式可知

故

所以

Ψ(xk+λmk-1Δxk)≤Ψ(xk)-σλmk-1‖Δxk‖2，即

而對(duì)k∈L1,Δxk=-Ψ(xk)，故

即(1-σ)‖Ψ(x*)‖2≤0。由假設(shè)Ψ(x*)≠0，那么σ≥1，這與算法2.1中σ∈(0,1)矛盾。所以只能有Ψ(x*)=0即x*是Ψ(x)的穩(wěn)定點(diǎn)。完成證明。

由以上結(jié)論不難得到下面的全局收斂定理。

定理2.3 設(shè)算法2.1產(chǎn)生的點(diǎn)列為{zk=(uk,xk)}，則

(1){uk}線性收斂到0;

(2){xk}的任一極限點(diǎn)都是函數(shù)Ψ(x)的穩(wěn)定點(diǎn)。

3 數(shù)值試驗(yàn)

在本部分中，參數(shù)選?。?/p>

lmax=16，λ=0.5，σ=0.001，α=0.1，η=0.8

當(dāng)效益函數(shù)Ψ(x)≤ε或迭代次數(shù)超過(guò)500時(shí)終止。以下算例可以在文獻(xiàn)[6-7]中找到。

例子3.1 使

表1 例子3.1的數(shù)值結(jié)果

初始點(diǎn)牛頓步次數(shù)梯度步次數(shù)解Ψ(X)(0，0，0)1021(2000001，1342840，0764282)866e-11(01，01，01)791(2000013，1342842，0764282)902e-11(1，1，1)681(200000，1342840，0764282)915e-11(2，1，1)221(200000，1342843，0764282)771e-11(2，13，07)170(200000，1342843，0764280)905e-11(2，2，2)290(200000，1342843，0764282)815e-11(10，10，10)1151(2000013，1342840，0764282)988e-11(-1，-1，-1)741(2000012，1342840，0764282)930e-11

通過(guò)算例的結(jié)果可以看出，本部分構(gòu)造的光滑牛頓法具有較好的全局收斂性，在任何點(diǎn)處都能在有限步內(nèi)收斂到互補(bǔ)問(wèn)題的解，并且在解的附近具有較快的收斂速率，這也從實(shí)際上說(shuō)明了算法的收斂性質(zhì)。

4 總結(jié)

本文利用光滑的FB函數(shù)將互補(bǔ)問(wèn)題轉(zhuǎn)化為光滑方程組問(wèn)題，并提出一類光滑牛頓算法求解該光滑方程組問(wèn)題。本文的兩點(diǎn)在于：(1) 光滑方程組中用函數(shù)A(u)替代了常規(guī)的u，并給出A(u)的一類特殊的選取方式，令

A(u)=eu+u-1；

(2)算法的設(shè)計(jì)中包含牛頓步和梯度步兩種，這樣不僅降低了計(jì)算的復(fù)雜度使算法具有全局收斂性，也加大了該算法的使用范圍。最后的一個(gè)經(jīng)典算例說(shuō)明了該算法的有效性。

[1]AGHASSI M,BERTSIMAS D,PERAKIS.Soving asymmetric variational inequalities via convex optimization[J].Operations Research Letters,2006,34(5):481-490.

[2]CHEN X D,SUN D,SUN J.Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems[J].Computational Optimization and Applications,2003,25(1-3):39-56.

[3]FACCHINIEI F,PANG J S.Finite-dimensional variational inequalities and complementarity problems,Volume II[M].New York:Springer-Verlag,2003.

[4]FUKUSHIMA M.Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems[J].Mathematical Programming,1992,53(1):99-110.

[5]SUN J H，WANG L.A smoothing Newton method based on the generalized Fischer-Burmeister function for variational inequality problem[J].Journal of Convergence Information Technology，2013,8(1):151-160.

[6]PANG J S,GABRIEL S A.NE/SQP:A robust algorithm for the nonlinear complementarity problem[J].Mathematical Programming,1993,60(3):295-337.

[7]MANGASARIAN D L,SOLODOV M V.Nonlinear complementarity as unconstrained and constrained minimization[J].Mathematical Programming,1993,62(1):277-297.

[8]SUN D,SUN J.Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions.Mathematical Programming,2005,103(3):575-581.

[9]PAN S,CHEN J.A semismooth Newton method for the SOCCP based on a one-parametric class of SOC complementarity functions[J].Computational Optimization and Applications,2010,45(1):59-88.

[10]PAN S,KUM S,LIM Y,et al.On the generalized Fischer-Burmeister merit function for the second-order cone complementarity problem[J].Mathematics of Computation,2014,83(83):1143-1171.

[11]HAO Z,WAN Z,CHI X,et al.A power penalty method for second-order cone nonlinear complementarity problems[J].Operations Research Letters,2015,290(2):136-149.

[12]SUN J H,ZHANG L W.A globally convergent method based on Fischer-Burmeister operators for solving second-order-cone constrained variational inequality problems[J].Computers and Mathematics with Applications,2009,58(10):1936-1946.

[13]SUN J H,CHEN J S,KO C H.Neural networks for solving second-order cone constrained variational inequality problem[J].Computational Optimization and Applications,2012,51(2):623-648.

[14]QI L,SUN D,ZHOU G.A new look at smoothing Newton method for nonlinear complementarity problems and box constrained variational inequalities[J].Mathematical Programming,2000,87(1):1-35.

[15]FUKUSHIMA M,LUO Z Q,TSENG P.Smoothing functions for second-order-cone complementarity problem[J].SIAM Journal on Optimization,2002,12(2):436-460.

(責(zé)任編輯：吳萍 英文審校：劉勇進(jìn))

A Class of smoothing newton methods for solving nonlinear complementarity problem

SUN Ju-he，JI Dong-chen,WANG Qi

(College of Science,Shenyang Aerospace University,Shenyang 110136,China)

We study a class of smoothing function methods for solving nonlinear complementarity problem in this paper.Based on the well-known Fischer-Burmeister function,we transform the nonlinear complementarity problem into a system of nonlinear smooth equations.For solving the system of nonlinear smooth equations,we construct a class of smoothing Newton methods and prove its global convergence,while discussing the nonsingularity of Jacobian matrix of the equation operator.An illustrative example is given to show the performance of the smoothing Newton method.

nonlinear complementarity problem;complementary function;smoothing Newton method;non-smooth;convergence

2016-01-21

國(guó)家自然科學(xué)基金(項(xiàng)目編號(hào)：11301348)

孫菊賀(1980-)，女，遼寧沈陽(yáng)人，副教授，主要研究方向：變分分析理論與優(yōu)化算法，E-mail:juhesun@163.com。

2095-1248(2016)05-0074-08

O221.2

A

10.3969/j.issn.2095-1248.2016.05.014

基礎(chǔ)科學(xué)與工程