求解非線性加權互補問題的光滑算法

湯京永，劉子玉，范 增

(信陽師范學院 數學與統計學院,河南 信陽 464000)

0 引言

2012年,國際著名優化專家POTRA教授提出了加權互補問題(Weighted Complementarity Problem)[1],其數學模型如下:

求(x,s,y)∈Rn×Rn×Rm,使得

x≥0,s≥0,F(x,s,y)=0,xs=w,

(1)

其中F(x,s,y):Rn+n+m→Rn+m是一個連續可微的函數,w≥0為給定的權重向量。

加權互補問題是一個非常廣泛的互補系統,其包含并將許多優化問題作為特例。比如,如果

這里T∈Rn×n,A∈Rm×n,b∈Rm,d∈Rn,則加權互補問題即為二次規劃

擾動的KKT條件。再比如,如果w=0,m=0并且F(x,s,y)=s-f(x),其中f:Rn→Rn是一個連續可微函數,則加權互補問題就變為標準的非線性互補問題[2-3]：

x≥0,s≥0,s=f(x),〈x,s〉=0。

此外,經濟、管理等領域中的許多均衡問題都可以轉化成加權互補問題模型，然后進行求解[1]。有些均衡問題可以轉化成互補問題(如著名的Fisher均衡問題),將其轉化成加權互補問題可以更有效地進行求解[1]。POTRA教授雖然提出了加權互補問題的數學模型(1),但他只研究了線性加權互補問題,即求(x,s,y)∈Rn×Rn×Rm,使得

x≥0,s≥0,Px+Qs+Ry=a,xs=w,

(2)

這里P∈R(n+m)×n、Q∈R(n+m)×n、R∈R(n+m)×m為給定矩陣,a∈Rn+m是給定向量。在文獻[1]中,POTRA教授給出了求解問題(2)的兩個內點算法,分析了算法的多項式迭代復雜性。2016年,POTRA教授在文獻[4]中研究了充分線性加權互補問題,給出了一個預估校正內點算法,證明了算法的迭代復雜性與求解充分線性互補問題內點算法的最好結果相同。最近，ASADI等[5]給出了第一個求解線性加權互補問題的全牛頓步內點法,分析了算法的迭代復雜性。

光滑算法是近年來求解優化問題的一類新方法,其基本思想是利用光滑函數將優化問題等價轉化成一個光滑方程組,然后利用牛頓法求解該方程組。與內點法不同,光滑算法可以選取任意初始點,并且在算法實施的過程中不需要迭代點嚴格可行。因此,光滑算法成為求解優化問題的一類頗受青睞的方法。最近,文獻[6-7]分別研究了求解線性加權互補問題(2)的光滑算法,證明了算法具有全局和二階收斂性質。

本文研究一個求解非線性加權互補問題(1)的光滑算法。具體而言,首先給出一個帶有權重的光滑函數,分析函數的性質。利用此光滑函數,將非線性加權互補問題(1)等價轉化成一個光滑方程組,然后提出一個新的光滑算法來進行求解。證明了算法生成的迭代點列的任意聚點都是非線性加權互補問題(1)的解,并在非奇異假設條件下證明了算法具有局部二階收斂性質。不同于文獻[6-7]中的光滑算法,本文算法采用了一種非常簡單的線搜索技術。數值實驗結果表明新算法是非常有效的。

1 一個帶有權重的光滑函數

本節給出一個帶有權重的光滑函數φc:R3→R,其定義如下:

φc(μ,a,b)=(1+μ)(a+b)-

(3)

其中c≥0是給定的非負整數。

引理1 設φc由式(3)定義,則

φc(μ,a,b)=0?a+μb≥0,μa+b≥0,

2(a+μb)(μa+b)=2c+μ2。

(4)

引理2 設φc由式(3)定義,則φc在任意的點(μ,a,b)∈R++×R×R處是連續可微的,并且

(5)

(6)

證明由φc的定義易知φc在任意的點(μ,a,b)∈R++×R×R處是連續可微的,并且

(7)

(8)

(9)

(1+μ)2[(1-μ)2(a-b)2]-

[(1-μ)2(a-b)]2=

[(1+μ)2-(1-μ)2]

(1-μ)2(a-b)2=

4μ(1-μ)2(a-b)2>0,

所以有

從而由式(8)可知式(5)成立。利用同樣的方法,可以證明式(6)成立。證畢。

令z=(μ,x,s,y)∈R×Rn×Rn×Rm。定義函數

(10)

其中w=(w1,…,wn)T為權重向量,則由引理1可知H(z)=0當且僅當μ=0且(x,s,y)為非線性加權互補問題(1)的解。此外,由引理2可知,H(z)在任意的點z∈R++×Rn×Rn×Rm處連續可微,并且

其中

為確保雅克比矩陣H′(z)可逆,假設:

假設1已用于分析求解線性加權互補問題(2)的光滑型算法[6-7]和內點法[1,4-5]。

定理1 如果假設1成立,則對于任意的z∈R++×Rn×Rn×Rm,H′(z)可逆。

定理1的證明類似于文獻[8]中的定理1,在此省略。

2 算法

步驟1:如果‖H(zk)‖=0,則算法停止。

步驟2:計算搜索方向Δzk=(Δμk,Δxk,Δsk,Δyk)),使其滿足

H′(zk)Δzk=-H(zk)+γβ(zk)e,

(11)

其中β(zk)=min{1,Ψ(zk)}。

步驟3:計算步長αk=δmk,其中mk是滿足不等式

Ψ(zk+δmΔzk)≤(1-σδ2m)Ψ(zk)

(12)

的最小非負整數m。

步驟4:令zk+1=zk+αkΔzk和k=k+1,轉步驟1。

定理2 如果假設1成立,則算法1產生一個無窮點列{zk=(μk,xk,sk,yk)},并且對所有的k≥0有μk>0。

證明假設對于某個k有zk=(μk,xk,sk,yk)∈R++×Rn×Rn×Rm。由定理1可知H′(zk)可逆,故步驟2是可行的，并且有

Δzk=H′(zk)-1[-H(zk)+γβ(zk)e],

進而可知

Ψ′(zk)Δzk=H(zk)TH′(zk)Δzk=

-2Ψ(zk)+μkγβ(zk)≤

其中第一個不等式成立是由于

下面證明步驟3是可行的。用反證法,假設對所有的非負整數m,都有Ψ(zk+δmΔzk)>(1-σδ2m)Ψ(zk),即

(13)

因為μk>0,Ψ(z)在zk點連續可微。令式(13)兩邊m→∞,則可得Ψ′(z)Δzk≥0,這與Ψ′(z)Δzk<0矛盾,故至少存在一個非負整數m使得式(12)成立,即步驟3是可行的。因此,在步驟4可得到第k+1個迭代點zk+1=zk+αkΔzk。此外,由式(11)可知Δμk=-μk+γβ(zk),結合β(zk)>0可得

μk+1=μk+αkΔμk=

(1-αk)μk+αkγβ(zk)>0。

(14)

這表明zk+1∈R++×Rn×Rn×Rm。由此可得出結論,如果對于某個k有zk∈R++×Rn×Rn×Rm,則zk+1可由算法1產生,并滿足zk+1∈R++×Rn×Rn×Rm。因為z0∈R++×Rn×Rn×Rm,故由數學歸納法可知定理成立。證畢。

引理3 設{zk=(μk,xk,sk,yk)}為算法1所產生的迭代點列,則對任意的k≥0,有

μk≥γβ(zk)。

證明由步驟3和步驟4可知,對任意的k≥0,有Ψ(zk)≥Ψ(zk+1)。因此,如果對于某個k成立μk≥γβ(zk),則由式(14)可知

μk+1≥(1-αk)γβ(zk)+αkγβ(zk)=

γβ(zk)=γmin{1,Ψ(zk)}≥

γmin{1,Ψ(zk+1)}=γβ(zk+1)。

因μ0≥γ≥γβ(z0),故由數學歸納法可知引理成立。證畢。

3 收斂性分析

定理3(全局收斂性) 設{zk=(μk,xk,sk,yk)}是由算法1所產生的迭代點列,則{zk}的任意聚點z*=(μ*,x*,s*,y*)都滿足

H(z*)=0。

假設Ψ(z*)>0,將導出矛盾。證明分為如下兩個部分:

(i) 假設對所有的k≥0都有αk≥c,其中c>0是一個給定的常數,則根據步驟3和步驟4,可得

(1-σc2)Ψ(zk)≤(1-σc2)k+1Ψ(z0)。

Ψ(zk+δ-1αkΔzk)>(1-σ(δ-1αk)2Ψ(zk)),

故有

-σδ-1αkΨ(zk)。

(15)

根據引理3,有

μk≥γβ(zk)=γmin{1,Ψ(zk)}

對所有的k≥0成立,因此

μ*≥γmin{1,Ψ(z*)}>0,

進而可知Ψ(z)在z*=(μ*,x*,s*,y*)處是連續可微的,故在式(15)兩端令k→∞,可得

Ψ′(z*)Δz*≥0,

這里Δz*為方程組

H′(z*)Δz*=-H(z*)+γβ(z*)e

的解。另一方面,根據步驟3可得

(16)

在式(16)兩端令k→∞,可得

Ψ′(z*)Δz*≤0。

因此,綜合可知Ψ′(z*)Δz*=0。

由步驟2可知，

Ψ′(z*)Δz*=HT(z*)H′(z*)Δz*=

-2Ψ(z*)+μ*γmin{1,Ψ(z*)},

再結合Ψ′(z*)Δz*=0,可得

2Ψ(z*)=μ*γmin{1,Ψ(z*)}。

(17)

利用這些條件,可以從式(17)中推得

引理4 如果F′為Lipschitz連續,則函數H(z)是在R×Rn×Rn×Rm上是強半光滑的。

證明因為函數φc在R3上是強半光滑的,故由文獻[9]中的推論2.4可知結論成立。證畢。

定理4(局部二次收斂性) 假設z*是由算法1產生的迭代點列{zk}的任意聚點。如果所有的V∈?H(z*)都是非奇異的,并且F′在z*處局部Lipschitz連續,則有

‖zk+1-z*‖=O(‖zk-z*‖2)。

定理4的證明類似于文獻[10]中的定理8,在此省略。

4 數值實驗

參數取值為σ=0.5,δ=0.2,μ0=10-4,γ=10-5。終止準則為‖H(zk)‖≤10-6。

首先,應用算法1求解如下非線性加權互補問題:

x≥0,s≥0,F(x,s,y)=0,xs=w,

(18)

其中

這里T∈Rn×n,A∈Rm×n,b∈Rm,d∈Rn。注意到,如果w=0,則該互補問題即為二次規劃

的KKT條件。

在數值實驗中,選擇T=diag(rand(n,1)),d=rand(n,1),A=rand(m,n),b=A*rand(n,1),w=rand(n,1)。對于每個問題,隨機生成10個算例,使用x0=s0=(1,…,1)T和y0=(1,…,1)T作為初始點進行測試。數值實驗的結果列于表1,其中AIT和ACPU分別表示10次測試算法所需迭代次數和CPU時間(以秒為單位)的平均值。由表1可以看出,算法1對于求解非線性加權互補問題是非常有效的。

表1 求解問題(18)的數值結果Tab.1 Numerical results for solving problem (18)

下面應用算法1求解由式(2)定義的線性加權互補問題,其中矩陣P、Q、R和向量a定義如下:

表2 求解問題(2)的數值結果Tab. 2 Numerical results for solving problem (2)

5 結束語

基于帶有權重的光滑函數,研究了一個求解非線性加權互補問題的光滑算法。該算法在每次迭代時只需求解一個線性方程組和進行一次線搜索。在適當條件下,證明了算法具有全局和局部二次收斂性質。數值實驗結果表明算法是非常有效的。