一個(gè)求解非線性互補(bǔ)問題的光滑化全局收斂性算法

何嬋

(武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)系,福建武夷山3543 00)

一個(gè)求解非線性互補(bǔ)問題的光滑化全局收斂性算法

何嬋

(武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)系,福建武夷山3543 00)

求解非線性互補(bǔ)問題的一種方法是將其轉(zhuǎn)化為非光滑方程組。本文通過引進(jìn)一個(gè)基于F isc h e r-B u rm e iste r函數(shù)的光滑N C P函數(shù)[8]，建立了求解P0函數(shù)非線性互補(bǔ)問題的一個(gè)新的光滑牛頓算法。這個(gè)算法在每步迭代中只需要解一個(gè)光滑方程且不要求給出具體光滑因子下降的過程。在一定的條件下，證明了該算法的全局收斂性。數(shù)值試驗(yàn)表明該算法是有效的.

非線性互補(bǔ)問題；光滑牛頓算法；全局收斂性.

§1引言

考慮如下的P0函數(shù)非線性互補(bǔ)問題(簡(jiǎn)記為N C P(F))：求一個(gè)向量x∈Rn,使得

這里F(x):Rn→Rn是一個(gè)連續(xù)可微P0函數(shù)(見文[1])。

非線性互補(bǔ)問題是數(shù)學(xué)規(guī)劃的一個(gè)基本問題，在工程和經(jīng)濟(jì)等領(lǐng)域都有非常重要的應(yīng)用，感興趣的讀者可以參考文獻(xiàn)[2,3]。

目前，求解非線性互補(bǔ)問題的一類重要方法是利用所謂的互補(bǔ)函數(shù)將N C P(F)轉(zhuǎn)換成非線性方程組或非線性最優(yōu)化問題來求解。本文將通過引進(jìn)一個(gè)光滑N C P函數(shù)來建立求解N C P(F)的光滑牛頓法。并證明了所提出的算法是適定的。同時(shí)證明了在一定的條件下該算法是全局收斂的。

本文的結(jié)構(gòu)如下：§2主要介紹一個(gè)光滑函數(shù)及其性質(zhì)；§3介紹算法并證明算法是適定的；§4討論算法的總體收斂性；§5為小結(jié)。

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

首先,給出F isc h e r-B u rm e iste r函數(shù)[4]:

F isc h e r-B u rm e iste r函數(shù)有很多好的性質(zhì)，在求解N C P(1.1)時(shí)，一般都以F isc h e r-B u rm e iste r函數(shù)(2.1)作為N C P函數(shù)(參見[5,6,7]),但它有一個(gè)明顯的不足，即F isc h e r-B u rm e iste r函數(shù)在(a,b)=(0,0)點(diǎn)是不可微的，因此給算法的收斂性分析帶來了困難，于是各種光滑化方法應(yīng)運(yùn)而生。

本文討論了一個(gè)光滑N C P-函數(shù)[8]如下

其中μ>0為光滑參數(shù)。這個(gè)光滑的N C P-函數(shù)有很好的性質(zhì)，下面列出了其中的兩個(gè)基本性質(zhì)。

性質(zhì)2.1(1)對(duì)任意的(μ，a，b)∈R++×R2,我們

(2)對(duì)任意的μ1，μ2∈R++,我們有

通過簡(jiǎn)單的計(jì)算，可得

顯然對(duì)于任意的μ>0,準(zhǔn)'μ，準(zhǔn)'a，準(zhǔn)'b都是連續(xù)的，且有

其中

不難證明，求解(1.1)等價(jià)于求解下面的非線性方程組

引理2.1設(shè)H:R++×Rn→Rn+1由(2.9)定義。那么H在R++×Rn連續(xù)可微，且其Ja c o b i矩陣為

其中

這里，指標(biāo)集

若F是P0-函數(shù)，則H'在R++×Rn非奇異。

證明:矩陣(2.11)可通過具體計(jì)算得到。由(2.8)不難發(fā)現(xiàn)

(2.11)可通過計(jì)算可以得到。由于eμ>0，因此，只需證明D1（z）+D2（z）F'（x）是對(duì)稱正定的。事實(shí)上，注意到對(duì)角矩陣D1（z）和D2（z）的對(duì)角元素都恒為正數(shù)，而Ja c o b i矩陣F'（x）是P0-矩陣(因F是P0-函數(shù))，根據(jù)P0-矩陣的性質(zhì)可以推得對(duì)稱矩陣D2（z）F'（x）的所有主子式是非負(fù)的，從而D1（z）+D2（z）F'（x）是對(duì)稱正定的，因而是非奇異的。由此可得，H'（z）也是非奇異的。證畢。

§3光滑化牛頓算法

基于上面的光滑函數(shù)，我們提出一種新的牛頓算法：令dk=（△μk，△xk），定義模函數(shù)θ:R++×Rn→R+：

我們現(xiàn)在提出求解問題(1.1)的一個(gè)光滑牛頓法。

算法3.1（光滑牛頓法）

步0選取參數(shù)δ∈(0,1),η>0,σ∈(0,1/2)，置z0：=（μ0，x0）∈R++×Rn為任意點(diǎn).

步1如果‖Φ（xk）‖=0，停算；

步2解下面方程組得dk

置tk：=δm，z軇=（μ軌k，x軇k）:=zk+tkdk,這里m為使下式成立的最小非負(fù)整數(shù)，

如果tk=1，則令zk+1：=z軇k，k：=k+1轉(zhuǎn)到步驟1.否則轉(zhuǎn)到步驟3

步3如果‖Φ（μ軌k，x軇k）‖燮η μ軌k成立，則令zk+1：＝z軇k，k:=k+1轉(zhuǎn)到步驟1.

步4否則，求△x軇k滿足

置x軇k:=x軇k+δl△x軇k轉(zhuǎn)到步驟3，這里l是使下式成立的最小非負(fù)整數(shù)，

注3.1由式（2.9）、（2.11）的形式知，由式（3.1）求dk的方法可以分成兩步：第一步是求△μk使得下式成立：

第二步是解n維線性方程得到△xk.

下面我們來證明這個(gè)算法是適定的。為此，我們引出如下假設(shè)：

假設(shè)3.1水平集D0={z∈R+×Rn|θ（z）燮θ（z0）}有界。

引理3.1{μk}單調(diào)下降，且μk>0對(duì)所有的k成立。證明:由(3.5)可得又由可知△μk>-μk.同時(shí)我們知道0μk(1-tk)>0,因此μk大于0.由△μk<0可知序列μk+1<μk單調(diào)下降.證畢。

如下的定理表明算法3.1中的步驟2和步驟4是有限終止的。

證明:只需要證步驟2是有限終止的，步驟4同理可證。

由于f，ek-1均是光滑的知H在μ>0時(shí)是光滑的。因此θ是光滑函數(shù)。我們有

用反證法證明。假設(shè)步驟2中的線搜索不是有限終止的，則由(3.2)有

對(duì)于任意mk都成立。上式兩邊除以δmk且令mk→∞，就可以得到由(3.1)，(3.7)，(3.8)可得也即是但是≠0且

定理3.2算法3.1中的步驟3和4的迭代有限終止。

k調(diào)下降且趨于0.因此，對(duì)于充分大的l有不等式‖Φ（μ軌，~xki）‖燮η μ軌成立。

kk

§4全局收斂性分析

下面證明算法3.1的全局收斂性。由定理1知算法3.1產(chǎn)生無限序列我們將證明迭代序列的任一聚點(diǎn)都是非線性方程組(2.10)的解。

定理4.1設(shè)H:R+×Rn→Rn+1是由(2.9)定義的函數(shù)。假設(shè)假設(shè)條件3.1成立。則算法3.1要么有限終止于‖Φ(x)‖=0的一個(gè)解，要么生成一個(gè)無限數(shù)列這個(gè)序列的任意一個(gè)收斂點(diǎn)中的x*都滿足

由算法3.1的更新規(guī)則知{θ（zk）}是單調(diào)下降的。因此由假設(shè)3.1，{zk}存在一個(gè)收斂點(diǎn)

當(dāng)tk=1時(shí)，由(3.2)有因此，如果步驟2中tk=1無限次發(fā)生，則有=0,也即是

下面討論tk≠1發(fā)生有限次的情況。

由引理2.1知對(duì)于任意的k有犖H(zk)是非奇異的。同時(shí)由假設(shè)3.1及θ(zk)是單調(diào)下降的可知，存在

因此對(duì)于所有的k,｛dk｝都有界。

由引理3.1知{μk}單調(diào)下降。所以有μk叟μ*.所以有如果則由步驟3中μk的更新規(guī)則可以推出μk→-∞.因此，必須有l(wèi)im in fk→∞tk=0。

令K0是使得序列收斂到0的指標(biāo)集。不失一般性，我們可以假設(shè)序列收斂到z*。由(3.2)有

兩邊同時(shí)除以tk,且取極限，有

λ

§5數(shù)值例子

為了驗(yàn)證算法3.1的有效性,我們對(duì)幾個(gè)問題進(jìn)行了數(shù)值實(shí)驗(yàn)，并就迭代次數(shù)與非精確N e w to n型信賴域算法(以下簡(jiǎn)稱算法N T)和非精確L e v e n b e rg-M a rq u rt型信賴域算法(簡(jiǎn)稱算法L-M)進(jìn)行了比較(參見[12])，數(shù)值結(jié)果如以下諸表。在下列各實(shí)驗(yàn)中，迭代次數(shù)右上角打*號(hào)的表示收斂到退化解，迭代次數(shù)打*號(hào)的表示算法的迭代次數(shù)超過100次。

算例1[8]試驗(yàn)函數(shù)為

這個(gè)例子有一個(gè)非退化解(1,0,3,0)T和一個(gè)退化解試驗(yàn)中，我們?nèi)ˇ?0.95,σ

=0.25,α=0.5,λ=0.4，終止值取為θ(xk)<10-12.對(duì)于不同的初始值，數(shù)值結(jié)果如表1.

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

算例2[11]試驗(yàn)函數(shù)為

這個(gè)例子有無窮多個(gè)解x*=(λ,0,0,0)T,其中λ∈[0,3],λ=1,3時(shí)為退化解.試驗(yàn)中,我們發(fā)現(xiàn)參數(shù)ρ的取值對(duì)迭代次數(shù)較為敏感,對(duì)于不同的初始點(diǎn),我們選取合適的ρ值,其它參數(shù)和終止準(zhǔn)則值同算例1,數(shù)值結(jié)果如表2.

表2算例2的數(shù)值結(jié)果

§6結(jié)論

基于光滑牛頓法思想，本文通過引進(jìn)一個(gè)新的光滑N C P-函數(shù)，建立了求解非線性互補(bǔ)問題光滑牛頓法，并在適當(dāng)?shù)臈l件下證明了算法的全局收斂性。此外，可以證明在一定的條件下，算法產(chǎn)生的迭代序列至少存在一個(gè)聚點(diǎn)，并具有局部二階收斂速度，這將是我們進(jìn)一步的工作。

[1]Z h a n g L ip in g,G a o Z iy o u，S u p e rlin e a r/q u a d ra tic o n e-ste p sm o o th in gN e w to nm e th o dfo rP 0-N C Pw ith o u tstric t c o m p le m e n ta rity[J],M a th e m a tic a lM e th o d so fO p e ra tio n R e se a rc h,p p.231-241(2002).

[2]H a rk e r,P.T.,P a n g,J.S.,F in ite-d im e n sio n a l v a ria tio n a l in e q u a litya n dn o n lin e a rc o m p le m e n ta rityp ro b-le m s:A su rv e yo fth e o ry,a lg o rith m sa n da p p lic a tio n s[J], M a th e m a tic a l P ro g ra m m in g 48:161-220(1990).

[3]F e rris,M.C.,P a n g,J.S.，E n g in e e rin ga n de c o n o m ic a p p lic a tio n s o f c o m p le m e n ta rity p ro b le m s[J],S IA M R e v ie w 39:669-713(1997).

[4]F isc h e r,A.,A sp e c ia l N e w to n-ty p e o p tim iza tio n m e th o d[J], O p tim iza tio n 24,269–284(1992).

[5]C h e n,B.,a n d H a rk e r,P.T.,S m o o th in g a p p ro x im a tio n s to n o n lin e a rc o m p le m e n ta rityp ro b le m s[J],S IA M Jo u rn a lo n O p tim iza tio n,7(1):403-420(1997).

[6]Q i,H.,Are g u la rize dsm o o th in gN e w to nm e th o dfo r b o x c o n stra in e d v a ria tio n a l in e q u a lity p ro b le m s w ith P 0-fu n c tio n s [J],S IA M Jo u rn a l o n O p tim iza tio n,10(1):315-330(2000).

[7]Q i,L.,S u n,D.,a n dZ h o u,G.,An e wlo o ka t sm o o th in g N e w to n m e th o d s fo r n o n lin e a r c o m p le m e n ta rity p ro b le m s a n d b o xc o n stra in e dv a ria tio n a lin e q u a lityp ro b le m s[J], M a th e m a tic a l P ro g ra m m in g,87(1):1-35(2000).

[8]M a,C.,C h e n,X.,T h e c o n v e rg e n c e o f a o n e-ste p sm o o th in g N e w to n m e th o d fo r P 0-N C P b a se d o n a n e w sm o o th in g N C P-fu n c tio n[J],Jo u rn a lo fC o m p u ta tio n a la n dA p p lie d M a th e m a tic s,216(1):1-13(2008)8.

A G lo b a lly C o n v e r g e n t S m o o th in g M e th o d fo r S o lv in g N o n lin e a r c o m p le m e n ta r ity P r o b le m

H E C h a n
（M a th e m a tic s a n d C o m p u te r D e p a rtm e n t o f W u y i U n iv e rsity,W u y ish a n,F u jia n 3543 00）

T h e n o n lin e a r c o m p le m e n ta rity p ro b le m(d e n o te b y N C P(F))c a n b e re fo r-m u la te d a s th e so lu tio n o f a n o n sm o o th sy ste m o f eq u a tio n s.B y in tro d u c in g a sm o o th in g N C P-fu n c tio n[8]b a se d o n F isc h e r-B u rm e iste r fu n c tio n,th e p ro b le m is a p p ro x im a te d b y a fa m ily o f p a ra m e te rize d sm o o th e q u a tio n s.An e w sm o o th in g N e w to n m e th o d is p ro p o se d fo r so lv in g th e n o n lin e a r c o m p le m e n ta rity p ro b le mw ith P 0 fu n c tio n b a se d o n th e sm o o th in g N C P-fu n c tio n，a n d it n e v e r re q u ire s a p ro c e d u re to d e c re a se a n a p p ro x im a tio n p a ra m e te r.T h e p ro p o se d a lg o rith m is p ro v e d to b e c o n v e rg e n t g lo b a lly.S o m e n u m e ric a l e x p e rim e n ts a re re p o rte d.

n o n lin e a r c o m p le m e n ta rity p ro b le m;sm o o th in g N e w to n m e th o d;g lo b a l c o n v e r-g e n c e

book=2,ebook=1

O 224.2

A

1674－2109(2011)02－0035－05

2011-02-10

2009年武夷學(xué)院科研基金資助項(xiàng)目（項(xiàng)目編號(hào)：x q 0927)。

何嬋（1984-），女，漢族，助教，主要研究方向：性互補(bǔ)問題的算法。