非線性互補(bǔ)問題的光滑算法

朱紅焰，岳靖，鞏成艷

（安徽理工大學(xué) 理學(xué)院，淮南 232001）

非線性互補(bǔ)問題的光滑算法

朱紅焰，岳靖，鞏成艷

（安徽理工大學(xué) 理學(xué)院，淮南 232001）

基于非線性互補(bǔ)問題（NCP（F））的等價(jià)變形，利用Fischer-Burmeister函數(shù)的光滑逼近函數(shù)將非線性互補(bǔ)問題轉(zhuǎn)化為優(yōu)化問題。提出了一種求解非線性互補(bǔ)問題的光滑逼近算法，通過構(gòu)造非線性互補(bǔ)問題的一個(gè)新的光滑逼近函數(shù)，將非線性互補(bǔ)問題等價(jià)地轉(zhuǎn)化為求解光滑方程組問題。在一定條件下證明了該算法的全局收斂性。數(shù)值實(shí)驗(yàn)結(jié)果說明了算法的有效性。

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

考慮以下非線性互補(bǔ)問題NCP(F):求向量x∈Rn使得

其中F∶Rn→Rn連續(xù)可微的P0-函數(shù)。

由于其在理論和實(shí)際應(yīng)用上的重要性，近年來，非線性互補(bǔ)問題已經(jīng)受到了許多研究者的關(guān)注。

首先，給出Fischer-Burmeister函數(shù):

求非線性互補(bǔ)問題（1）等價(jià)轉(zhuǎn)化為求解以下非線性方程組:

且Φ∶Rn→Rn，它的第i個(gè)分量由下面的表達(dá)式給出:

Fischer-burmeister函數(shù)有很多好的性質(zhì)，在求解NCP（1）時(shí)，一般都以Fischer-Burmeister函數(shù)作為 NCP函數(shù)，但是Fischer-burmeister函數(shù)在(a,b)=(0,0)點(diǎn)是不可微的，給算法的收斂性分析帶來困難，于是光滑算法應(yīng)運(yùn)而生。

本文構(gòu)造一個(gè)新的光滑NCP函數(shù)如下:

對于任意的μ1＞μ≥0，有:

引理1:若Φ(x,μ)，Φ(x)是如上所定義的，則Φμ是Φ的一致光滑逼近函數(shù)。通過簡單計(jì)算得

利用光滑逼近函數(shù)，問題可以轉(zhuǎn)化為下面帶約束的非線性方程組

顯然，當(dāng)μ＞0時(shí)，Φμ(x)是光滑的，且其Jacobi矩陣?Φμ(x)T為:

其中，Jacobi矩陣的第i個(gè)分量為

1 算法

算法1:

其中，η＞0，選取初始點(diǎn) x0∈Rn和正常數(shù)置k∶=0，

若式（13）成立，置λk∶=1，轉(zhuǎn)step5；

Step4 若m是滿足下屬不等式的最小非負(fù)整數(shù)

置λk∶=ρ1m；

Step5 置xk+1∶=xk+λkdk；

否則，置μk+1∶=μk；

Step7 置k∶=k+1，轉(zhuǎn)Step2

注1:由于 ηk＞0，總可以選取充分小的λ=ρ1i＞0，使得不等式（14）成立，從而算法是可行的。

注2:若是{xk}是由于算法產(chǎn)生的無窮數(shù)列，則對于任意的k滿足Φ(xk,μk)≠0，且正數(shù)序列{μk}是非增的，并且滿足式（16）:

則由于式（6）和式（16）可以得到證明如下:

從而可以得到式（19）:

2 全局收斂性

假設(shè)

（b）對于任意的μ＞0，Φ'(x,μ)非奇異，且x∈Ω。

引理2:設(shè)序列{xk}是由算法產(chǎn)生的，那么對于任意的k，有{xk}?Ω,

證明:對于算法1中步3中的式（13），結(jié)論顯然成立，對于步4中的式（14），有:

引理3:設(shè)序列{xk}由算法產(chǎn)生，定義指標(biāo)集其中:

若指標(biāo)集K為無限集，那么:

且序列{xk}的任意聚點(diǎn)是問題（1）的解。

證:由題中K為無限集，又因K={0}?K1?K2，故只需要考慮以下兩種情況:

情形1:K2是無限集.此即意味著（21）式無限次成立，而ρ2∈(0,1)，故由引理即可得（22）成立。

情形2:K2是有限集，但K1是無限集，不失一般性，設(shè)對任意的非負(fù)整數(shù)k，記即ki是 K中不大于k的最大指標(biāo)，則顯然有μk=μki。

由（17），對i≥0，有:

由算法的step 6可知

以及

綜上表明序列{xk}的每個(gè)聚點(diǎn)都是Φ(x)的一個(gè)零點(diǎn)，即問題（1）的一個(gè)解。

定理1:設(shè)假設(shè)成立，序列{xk}由算法產(chǎn)生，那么指標(biāo)集K必是無限集，且

證明:用反證法，假設(shè)K是有限集，K采用情形2的假設(shè)方式，則μk=μki=μ，且步長λk由（14）確定，即

由假設(shè)（b），存在常數(shù) M1＞0，使得

因此，對于充分大的K，有

（a）當(dāng) λ＞0時(shí)，有 d=0則由（12）式即得Φ(x)=0，矛盾。

對上式兩端同時(shí)除以λk'，且令k(∈K)→∞，得

由于-?Φ(xk,μ)dk=Φ(xk)，令k(∈K)→∞，得

又由（26）式得

因此式（25）與式（27）矛盾，從而K為無限集.

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

表1 數(shù)值結(jié)果

4 結(jié)論

論文將NCP問題轉(zhuǎn)化為光滑方程組來求解，構(gòu)造了相應(yīng)的光滑逼近算法，證明了在一定條件下該算法的全局收斂性，同時(shí)給出數(shù)值試驗(yàn)來驗(yàn)證算法的時(shí)效性，下一步工作的重點(diǎn)是證明算法的局部二次收斂和超線性收斂，以及算法產(chǎn)生的迭代序列至少存在一個(gè)聚點(diǎn)。

［1］ 許小芳，馬昌風(fēng).基于一個(gè)新的NCP函數(shù)的光滑牛頓法求解非線性互補(bǔ)問題［J］.數(shù)學(xué)雜志，2011，31（4）: 750-755.

［2］ 范斌，馬昌鳳.求解非線性互補(bǔ)問題的一個(gè)雅可比光滑化方法［J］.福建師范大學(xué)學(xué)報(bào)，2012，28（3）:27-31.

［3］ 張修梅，蔣利華.非線性互補(bǔ)問題的光滑逼近法［J］.安徽大學(xué)學(xué)報(bào)，2012，36（2）:24-28.

［4］ 陳爭，馬昌鳳.求解非線性互補(bǔ)問題的一個(gè)新的Jacobin光滑化方法［J］.計(jì)算數(shù)學(xué)，2010，32（4）:362-372.

［5］ 柴婧，馬昌鳳.求解廣義非線性互補(bǔ)問題的光滑擬牛頓算法［J］.高校應(yīng)用數(shù)學(xué)學(xué)報(bào)，2011，26（4）:453-466.

［6］ 于一超，田志遠(yuǎn)，劉相靜，等.非線性互補(bǔ)問題的一個(gè)數(shù)值解法［J］.青島大學(xué)學(xué)報(bào)，2014，27（3）:14-18.

［7］ 韓繼業(yè)，修乃華，戚厚鋒.非線性互補(bǔ)理論與算法［M］.上海:上海技術(shù)科學(xué)出版社，2003:248-296.

［8］ 馬昌鳳.最優(yōu)化方法及其Matlab程序設(shè)計(jì)［M］.北京:科學(xué)出版社，2010:53-68.

A Smoothing Algorithm for Nonlinear Complementarity Problems

ZHU Hongyan，YUE Jing，GONG Chengyan
（School of Science，Anhui University of Science and Technology，Huainan 232001）

Based on the equivalent deformation of nonlinear complementarity problems（NCP（F））and the use of smooth approximating functions of Fischer-Burmeister function，the problem is transformed into optimization problem.A smoothing approximation algorithm is proposed for solving the nonlinear complementarity problem.By introducing a new smoothing NCP-function，the problem is approximated by a family of parameterized smooth equations.The proposed algorithm has been proved to be globally convergent under certain conditions.Numerical experiment results demonstrate the effectiveness of the algorithm.

nonlinear complementarity problem；smoothing approximation algorithm；gobal convergence；

O224

A

1672-9870（2016）05-0127-04

2016-05-30

朱紅焰（1992-），女，碩士研究生，E-mail:1213096843@qq.com