非線性互補問題的光滑算法

朱紅焰，岳靖，鞏成艷

（安徽理工大學 理學院，淮南 232001）

非線性互補問題的光滑算法

朱紅焰，岳靖，鞏成艷

（安徽理工大學 理學院，淮南 232001）

基于非線性互補問題（NCP（F））的等價變形，利用Fischer-Burmeister函數的光滑逼近函數將非線性互補問題轉化為優化問題。提出了一種求解非線性互補問題的光滑逼近算法，通過構造非線性互補問題的一個新的光滑逼近函數，將非線性互補問題等價地轉化為求解光滑方程組問題。在一定條件下證明了該算法的全局收斂性。數值實驗結果說明了算法的有效性。

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

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

其中F∶Rn→Rn連續可微的P0-函數。

由于其在理論和實際應用上的重要性，近年來，非線性互補問題已經受到了許多研究者的關注。

首先，給出Fischer-Burmeister函數:

求非線性互補問題（1）等價轉化為求解以下非線性方程組:

且Φ∶Rn→Rn，它的第i個分量由下面的表達式給出:

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

本文構造一個新的光滑NCP函數如下:

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

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

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

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

其中，Jacobi矩陣的第i個分量為

1 算法

算法1:

其中，η＞0，選取初始點 x0∈Rn和正常數置k∶=0，

若式（13）成立，置λk∶=1，轉step5；

Step4 若m是滿足下屬不等式的最小非負整數

置λk∶=ρ1m；

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

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

Step7 置k∶=k+1，轉Step2

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

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

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

從而可以得到式（19）:

2 全局收斂性

假設

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

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

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

引理3:設序列{xk}由算法產生，定義指標集其中:

若指標集K為無限集，那么:

且序列{xk}的任意聚點是問題（1）的解。

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

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

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

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

由算法的step 6可知

以及

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

定理1:設假設成立，序列{xk}由算法產生，那么指標集K必是無限集，且

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

由假設（b），存在常數 M1＞0，使得

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

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

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

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

又由（26）式得

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

3 數值試驗

表1 數值結果

4 結論

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

［1］ 許小芳，馬昌風.基于一個新的NCP函數的光滑牛頓法求解非線性互補問題［J］.數學雜志，2011，31（4）: 750-755.

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

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

［4］ 陳爭，馬昌鳳.求解非線性互補問題的一個新的Jacobin光滑化方法［J］.計算數學，2010，32（4）:362-372.

［5］ 柴婧，馬昌鳳.求解廣義非線性互補問題的光滑擬牛頓算法［J］.高校應用數學學報，2011，26（4）:453-466.

［6］ 于一超，田志遠，劉相靜，等.非線性互補問題的一個數值解法［J］.青島大學學報，2014，27（3）:14-18.

［7］ 韓繼業，修乃華，戚厚鋒.非線性互補理論與算法［M］.上海:上海技術科學出版社，2003:248-296.

［8］ 馬昌鳳.最優化方法及其Matlab程序設計［M］.北京:科學出版社，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