何嬋

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

一個求解非線性互補問題的光滑化全局收斂性算法

何嬋

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

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

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

§1引言

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

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

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

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

本文的結(jié)構(gòu)如下：§2主要介紹一個光滑函數(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)時，一般都以F isc h e r-B u rm e iste r函數(shù)(2.1)作為N C P函數(shù)(參見[5,6,7]),但它有一個明顯的不足，即F isc h e r-B u rm e iste r函數(shù)在(a,b)=(0,0)點是不可微的，因此給算法的收斂性分析帶來了困難，于是各種光滑化方法應運而生。

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

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

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

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

通過簡單的計算，可得

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

其中

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

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

其中

這里，指標集

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

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

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

§3光滑化牛頓算法

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

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

算法3.1（光滑牛頓法）

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

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

步2解下面方程組得dk

置tk：=δm，z軇=（μ軌k，x軇k）:=zk+tkdk,這里m為使下式成立的最小非負整數(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是使下式成立的最小非負整數(shù)，

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

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

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

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

引理3.1{μk}單調(diào)下降，且μk>0對所有的k成立。證明:由(3.5)可得又由可知△μk>-μk.同時我們知道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ù)。我們有

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

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

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

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

kk

§4全局收斂性分析

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

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

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

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

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

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

因此對于所有的k,｛dk｝都有界。

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

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

兩邊同時除以tk,且取極限，有

λ

§5數(shù)值例子

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

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

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

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

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

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

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

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

§6結(jié)論

基于光滑牛頓法思想，本文通過引進一個新的光滑N C P-函數(shù)，建立了求解非線性互補問題光滑牛頓法，并在適當?shù)臈l件下證明了算法的全局收斂性。此外，可以證明在一定的條件下，算法產(chǎ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年武夷學院科研基金資助項目（項目編號：x q 0927)。

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