混合互補問題的光滑算法及收斂性

摘 要 利用Fischer-Burmeister函數將混合互補問題轉化為非線性方程組，由光滑函數逼近FB函數來求解非線性方程組.文中將信賴域方法和梯度法相結合，提出了Jacobian光滑化方法.算法在一定條件下的全局收斂性得到了證明，數值試驗表明算法切實有效，有一定的優越性.

關鍵詞 混合互補問題;Jacobian光滑算法;信賴域方法;梯度步;全局收斂;二階收斂

中圖分類號 O178 文獻標識碼:A

1 引 言

互補問題是運籌學與數學的一個交叉研究領域，許多經濟、金融、控制等方面的問題都可以轉化為互補問題來求解，其中混合互補問題MCP(a，b，F)是求x*∈[a，b]，使得對任意x∈[a，b]滿足

F(x*)T(x-x*)≥0，MCP(a，b，F)，

式中，a，b∈Rn，F為連續可微的向量函數.這類問題也稱作箱形約束的變分不等式問題(BVI).引入松弛變量后，MCP(a，b，F)系統的解x*滿足KKT系統

F(x)+y-z=0，x-a≥0，z≥0，(x-a)Tz=0，

b-x≥0，y≥0，(b-x)Ty=0.(1)

文獻[1]中采用了將信賴域方法和線搜索技巧相結合的光滑化方法來求解非線性互補問題，該方法推廣了Yang和Qi的方法^[2].Ma和Kang在^[3]中也采用兩種下降方向相結合的方法求解變分不等式.

基于這種思想，本文推廣文^[2]的算法，針對混合互補問題，采用將信賴域和梯度方法相結合的方法，提出了逐次逼近光滑近似算法.

2 輔助函數及性質

問題(1)等價于系統

x-a≥0，F(x)+y≥0，(x-a)T(F(x)+y)=0，b-x≥0，y≥0，(b-x)Ty=0.(2)

由NCP函數φ(a，b)=a2+b2-a-b的性質知，問題(2)等價于求解非線性方程組

H(x，y):=φ(x1-a1，F1(x)+y1)φ(xn-an，Fn(x)+yn)φ(b1-x1，y1)φ(bn-xn，yn)=0.(3)

相應于方程組(3)的效益函數定義為Ψ(x，y)=12‖H(x，y)‖2.形如問題(3)的非光滑方程組，研究得最多的是構造光滑逼近函數的方法，這些方法基本上每迭代一次，需求解廣義牛頓方程，增加運算量.第2節我們將通過引入光滑函數，并介紹光滑逼近函數.

構造帶參數的光滑函數

φμ(a，b)=φ(a，b)，a2+b2>μ，

a(a-2μ)2μ+b(b-2μ)2μ+μ2，a2+b2≤μ，

式中，μ>0為光滑因子.可以證明，φμ:R2→R是光滑函數，而且是以Fischer-Burmeister函數為極限函數，即lim μ→0φμ(a，b)=φ(a，b)，則問題(3)的光滑逼近方程組為

Hμ(x，y):=φμ(x1-a1，F1(x)+y1)φμ(xn-an，Fn(x)+yn)φμ(b1-x1，y1)φμ(bn-xn，yn)=0.(4)

對應于方程組(4)的效益函數為Ψμ(x，y)=12‖Hμ(x，y)‖2.經 濟 數 學第 27 卷

第3期何郁波等:混合互補問題的光滑算法及收斂性

3 算法與基本假設

記z=xy∈R2n，則本文所針對的目標函數為

H(z)=0min z∈R2nΨ(z).(5)

根據所引進的光滑函數，將利用下面光滑非線性方程組來逼近問題(5)，

Hμ(z)=0min z∈R2nΨμ(z)，μ↓0.(6)

給出關于問題(6)的信賴域法和梯度方向相結合的光滑化方法.令

Qk(d):=12‖Hμk(zk)+H′μk(zk)Td‖2

=Ψμk(zk)+Hμk(zk)TH′μk(zk)Td+12dTH′μk(zk)TH′μk(zk)Td.

算法2.1 (光滑逼近算法)

步0 選取初始點z0=(x0)T，(y0)TT∈R2n，Δ0，Δmin ，λ，η，α，ε，ρ∈(0，1)，γ>0，σ∈(0，12(1-α))，0

步1 若 ‖

步2 求解信賴域子問題得解dk∈R2n

min ‖d‖≤ΔkQk(d)，(7)

步3 若

Hμk(zk)TH′μk(zk)Td<-max {ρ‖dk‖Ψμk(zk)，ρ‖dk‖2}，(8)

則轉步5;

步4 令

dk:=-

在{0，1，2，...}中求滿足

Ψ(zk+λmkdk)≤Ψ(zk)-σλmk‖dk‖2(10)

的最小非負整數mk，令tk=λmk，zk+1=zk+tkdk，Δk+1=Δk，轉步6;

步5 令

rk=Ψμk(zk)-Ψμk(zk+dk)Ψμk(zk)-Qk(dk)，(11)

zk+1=zk+dk，rk>c2zk，rk≤c2(12)

Δk+1=c3Δk，rk≤c2，max {Δmin ，Δk}，c2

步6 若

‖H(zk+1)‖≤max {η βk，α-1‖H(zk+1)-Hμk(zk+1)‖}，(14)

則令βk+1=‖H(zk+1)‖，并取μk+1滿足

0<μk+1≤min {α2nβk+1，μk2，μ-(zk+1，γβk+1)};(15)

若式(14)不成立，dk由式(9)確定，則令βk+1=βk，取μk+1滿足

0<μk+1≤min {α2n‖H(zk+1)‖，μk2，‖H(zk)‖-‖H(zk+1)‖2n};(16)

否則，令βk+1=βk，μk+1=μk;

步7 令k:=k+1，轉步1.

記K={0}∪{k∈N|‖H(zk)‖≤max {ηβk-1，α-1‖H(zk)-Hμk-1(zk)‖}}.

由于在算法2.1的梯度步中，使用了標準Armijo搜索準則，而在信賴域步中根據信賴域算法的特點可知算法2.1是適定的.

假設2.1 令{zk=(xk)T，(yk)TT}R2n是算法2.1產生的序列，假設

{zk}L0:={z∈R2n|Ψ(zk)≤(1+α)2Ψ(z0)}.(17)

4 收斂性分析

本節將證明算法2.1的全局和局部收斂性.下面引理來自文獻[4].

引理3.1 令zk是算法2.1產生的序列，假定zk的聚點z*是問題(4)的解，則K是無限集且{μk}↓0^[4].

引理3.2 設zk由算法2.1產生的序列，假定指標集K是無限集，則序列zk的每個聚點是方程組(4)的一個解^[4].

引理3.3 設序列zk由算法2.1產生，zkL是收斂于z*的子序列，若對于所有k∈L，都有dk=-

定理3.1 設zk由算法2.1產生的序列，則zk的每個聚點都是Ψ(z)的一個穩定點.

證明 若K是無限集，則由引理3.2可知，zk的每個聚點都是Ψ(z)的一個穩定點.下面假設K是有限集.若zk中有無限多步由梯度步產生，則由引理3.3知，zk的聚點z*是Ψ(z)的穩定點.因此下面考慮梯度步有限的情形.

設是K中最大整數，則對所有k>，有，

μk≤μ，βk≤β

及

‖H(zk+1)‖>ηβk=η‖H(z)‖>0.

由于μk單調遞減且有下界，因此收斂.設{μk}→μ*.下面證明μ*=0.若不然，假設μ*>0，則k充分大時，μk=μ*且k∈:={k|Hμk(zk)TH′μk(zk)Tdk<-max {ρ‖dk‖Ψμk(zk)，ρ‖dk‖2}}.假設zk的任何聚點都不是Ψ(z)的穩定點，則有lim k

令K1:=k|k∈，rk>c2，由Ψμ*(zk)單調遞減有下界，且當k充分大時k∈，由式(11)，式(12)及式(18)得∑k∈K1‖

從而Hμ*(z*)=0，根據文獻[4]的引理3.1可得H(z*)=0，即z*是混合互補問題的解.由引理3.1知，這與K是有限集的假設矛盾.

若Hμ*(z*)≠0，則

Hμk(zk)TH′μk(zk)Tdk<-max {ρ‖dk‖Ψμk(zk)，ρ‖dk‖2}<-ρ‖dk‖Ψμk(zk).

而

-‖

TH′μ*(zk)Tdk<-ρ‖dk‖Ψμk(zk)，

即‖

0，這與式(19)矛盾.

綜合以上可知μ*=0，即由梯度步dk=-

3.2，引理3.3立即得本定理.

證畢

定理3.2 設序列zk由算法2.1產生且收斂于方程組(4)的解，若J(z*)=H′μ(z*)非奇異且在z*點附近Lipchitz連續，則當k充分大時，問題(7)的信賴域半徑有正下界，牛頓步dkN=-J-1kHμk(zk)為其最優解，其中Jk=H′μk(zk)，從而算法是局部二階收斂的.

根據牛頓收斂定理即可證明本定理.

5 數值試驗

本節就低維混合互補問題進行數值試驗，比較文中算法2.1與文獻[6]中的算法.算法中，終止準則為ε=10-6，參數選取為ρ=10-10，α=0.4，η=0.5，λ=0.8，γ=0.6，σ=0.01，Δmin =0.01.用Matlab程序實現.

算例1 考慮下面非線性互補問題

F(x)=3x21+2x1x2+2x22+x3+3x4-62x21+x1+x22+10x3+2x4-23x21+x1x2+2x22+2x3+9x4-9x21+3x22+2x3+3x4-3.，

考慮約束集Ω=[a，b]，其中a=(0，0，0，0)T.b=(105，105，105，105)T，這個問題在區間[0，+

算例2 考慮下面混合互補問題

F(x)=400x31+2x1-400x1x2-2-200x21+220.2x2+19.8x4-40360x21+2x3-360x3x4-219.8x2-180x23+220x4-40.，

考慮約束集Ω=[a，b]，其中a=(-10，-10，-10，-10)T.b=(10，10，10，10)T.這個問題在區間(-

根據上面2個算例的兩種算法比較，對于算例1，文獻[6]中算法具有一定的優勢，主要是迭代次數較少.對于算例2，目標函數非線性程度較高，本文算法具有較為明顯的優勢，主要表現在迭代次數較少.但是筆者在試驗過程中發現文中算法2.1穩定性受初始點的影響較大，如何改進算法的穩定性將是我們今后的任務.同時，如何利用混合互補問題本身的特性來構造算法將是以后更加深入研究的方向.

參考文獻

[1] 陳為民. 求解非線性互補問題的光滑化方法[D]. 長沙:湖南大學，2004.

[2] YANG Yu-fei，QILi-qun. Smoothing trust region methods for nonlinear complementarity problems with P0-functions [J]. Annals of Operations Research， 2005，133(1):99-117.

[3] MA Chang-feng， KANG Tong. A Jacobian smoothing method for box constrained variational inequality problems [J]. ApplMathand Comput， 2005， 162(3):1397-1429.

[4] 何郁波. 混合互補問題的光滑化方法[D].桂林:桂林電子科技大學計算科學與數學學院，2006.

[5] POWELLM J D. Convergence properties of a class of minimization algorithms， in: Nonlinear programming [M]. New York: Academic Press， 1975.

[6] MA Chang-feng. Quadratic convergence of damped newton’s method for bi-obstacle problems[J]， Mathematics in Economics， 1998，15(1):88-94.

The Convergence of a Smoothing Method

for the Mixed Complementarity Problem

HE Yu-bo1，MA Chang-feng2，DONG Xiao-liang3

(1.Department of Mathematics and applied mathematics， Huaihua University，Huaihua，Huna 418008，China;

2. School of mathematics and computer science， Fujian Normal University， Fuzhou，Fujia 350007，China;

3. School of Information and computation science， the North University

for Ethnics， Yinchuan，Ningxia 750021，China)

Abstract We convertedthe mixed complementarity problem into a system of nonsmooth nonlinear equations by using Fischer-Burmeister function，and we used a smooth function to approximate the Fischer-Burmeister function. By combining trust region method with gradient method， a Jacobian smoothing method was proposed. Under some conditions， we provedthe global convergence and local convergence of the algorithm. Numerical result indicates that the algorithm is quite promising.

Keywords mixed complementarity problem; Jacobian smoothing method; trust region method; gradient step; global convergence; quadratic convergence