求解非線性加權(quán)互補問題的光滑算法

湯京永，劉子玉，范 增

(信陽師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,河南 信陽 464000)

0 引言

2012年,國際著名優(yōu)化專家POTRA教授提出了加權(quán)互補問題(Weighted Complementarity Problem)[1],其數(shù)學(xué)模型如下:

求(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是一個連續(xù)可微的函數(shù),w≥0為給定的權(quán)重向量。

加權(quán)互補問題是一個非常廣泛的互補系統(tǒng),其包含并將許多優(yōu)化問題作為特例。比如,如果

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

擾動的KKT條件。再比如,如果w=0,m=0并且F(x,s,y)=s-f(x),其中f:Rn→Rn是一個連續(xù)可微函數(shù),則加權(quán)互補問題就變?yōu)闃藴实姆蔷€性互補問題[2-3]：

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

此外,經(jīng)濟、管理等領(lǐng)域中的許多均衡問題都可以轉(zhuǎn)化成加權(quán)互補問題模型，然后進行求解[1]。有些均衡問題可以轉(zhuǎn)化成互補問題(如著名的Fisher均衡問題),將其轉(zhuǎn)化成加權(quán)互補問題可以更有效地進行求解[1]。POTRA教授雖然提出了加權(quán)互補問題的數(shù)學(xué)模型(1),但他只研究了線性加權(quán)互補問題,即求(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)的兩個內(nèi)點算法,分析了算法的多項式迭代復(fù)雜性。2016年,POTRA教授在文獻[4]中研究了充分線性加權(quán)互補問題,給出了一個預(yù)估校正內(nèi)點算法,證明了算法的迭代復(fù)雜性與求解充分線性互補問題內(nèi)點算法的最好結(jié)果相同。最近，ASADI等[5]給出了第一個求解線性加權(quán)互補問題的全牛頓步內(nèi)點法,分析了算法的迭代復(fù)雜性。

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

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

1 一個帶有權(quán)重的光滑函數(shù)

本節(jié)給出一個帶有權(quán)重的光滑函數(shù)φc:R3→R,其定義如下:

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

(3)

其中c≥0是給定的非負整數(shù)。

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

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

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

(4)

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

(5)

(6)

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

(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。定義函數(shù)

(10)

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

其中

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

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

定理1 如果假設(shè)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)

的最小非負整數(shù)m。

步驟4:令zk+1=zk+αkΔzk和k=k+1,轉(zhuǎn)步驟1。

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

證明假設(shè)對于某個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是可行的。用反證法,假設(shè)對所有的非負整數(shù)m,都有Ψ(zk+δmΔzk)>(1-σδ2m)Ψ(zk),即

(13)

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

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

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

(14)

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

引理3 設(shè){zk=(μk,xk,sk,yk)}為算法1所產(chǎn)生的迭代點列,則對任意的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),故由數(shù)學(xué)歸納法可知引理成立。證畢。

3 收斂性分析

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

H(z*)=0。

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

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

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

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

故有

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

(15)

根據(jù)引理3,有

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

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

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

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

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

這里Δz*為方程組

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

的解。另一方面,根據(jù)步驟3可得

(16)

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

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

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

由步驟2可知，

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

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

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

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

(17)

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

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

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

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

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

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

4 數(shù)值實驗

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

首先,應(yīng)用算法1求解如下非線性加權(quán)互補問題:

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

(18)

其中

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

的KKT條件。

在數(shù)值實驗中,選擇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作為初始點進行測試。數(shù)值實驗的結(jié)果列于表1,其中AIT和ACPU分別表示10次測試算法所需迭代次數(shù)和CPU時間(以秒為單位)的平均值。由表1可以看出,算法1對于求解非線性加權(quán)互補問題是非常有效的。

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

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

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

5 結(jié)束語

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