遲曉妮, 崔然然, 張所濱, 朱 寧

(桂林電子科技大學(xué) a. 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院/廣西自動(dòng)檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室/廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室； b. 科學(xué)技術(shù)發(fā)展研究院；c. 信息科技學(xué)院, 廣西 桂林 541004)

0 引言

線性二階錐權(quán)互補(bǔ)問題(LSOCWCP)是指找到向量x∈Rn使得

(1)

其中連續(xù)可微函數(shù)F(x):Rn→Rn,K={x=(x1;x2)∈R×Rn-1:x1≥‖x2‖}為n維二階錐(SOC), 矩陣P∈Rn×n, 向量q∈Rn,w∈K為給定權(quán)向量。

線性二階錐互補(bǔ)問題(LSOCCP)是w=0時(shí)的LSOCWCP(1):

權(quán)互補(bǔ)問題(WCP)在工程設(shè)計(jì)、經(jīng)濟(jì)及魯棒優(yōu)化等諸多領(lǐng)域有著廣泛應(yīng)用[1-2], 是一類重要的優(yōu)化問題[3], 因此WCP[4-5]的算法研究引起廣泛關(guān)注。

1 預(yù)備知識

目前, 學(xué)者們常將互補(bǔ)問題(CP)[6-7]基于效益函數(shù)[8-9]轉(zhuǎn)化為極小化問題,運(yùn)用無導(dǎo)數(shù)下降算法[10-11]求解。 這類方法減少了計(jì)算工作量, 因?yàn)闊o須計(jì)算F的導(dǎo)數(shù)。 如GU等[12]利用無導(dǎo)數(shù)下降算法求解非線性CP, 討論算法的全局收斂性及收斂率。 CHEN等[13]分析SOC互補(bǔ)問題(SOCCP), 對SOCCP進(jìn)行極小化變形求解。

本文推廣CP的非單調(diào)無導(dǎo)數(shù)下降算法求解LSOCWCP,提出新的SOC權(quán)互補(bǔ)函數(shù),構(gòu)造其效益函數(shù), 利用該函數(shù)將LSOCWCP轉(zhuǎn)化為無約束極小化問題, 分析其水平集有界性。 為提高算法性能, 算法采用非單調(diào)線搜索計(jì)算步長, 且是全局收斂的。最后給出非單調(diào)無導(dǎo)數(shù)下降算法在不同條件下分別求解LSOCWCP和LSOCCP的數(shù)值結(jié)果。

下面給出一些相關(guān)定義。對任意x=(x1;x2),y=(y1;y2)∈R×Rn-1,x和y與SOC相伴的約當(dāng)積[14]定義為x°y=(xTy;x1y2+y1x2)。x+和x-分別是x在K和-K上的投影,x=x++x-。 對任意x=(x1;x2)∈R×Rn-1, SOC的內(nèi)部定義為intK={x=(x1;x2)∈R×Rn-1:x1>‖x2‖}。

定義箭形矩陣

其中I是適當(dāng)維數(shù)的單位陣。

定義1(譜分解)[14]對任意x=(x1;x2)∈R×Rn-1, 與SOC相伴的譜分解定義為

x=λ1(x)u(1)(x)+λ2(x)u(2)(x),

其中λi(x),u(i)(x) (i=1,2)分別是x的譜值和譜向量:

λi(x)=x1+(-1)i‖x2‖,

u(i)(x)=

這里?2∈Rn-1是滿足‖?2‖=1的任意向量。

定義2[15]對任意x,y∈Rn, 若存在某常數(shù)α>0使

〈F(x)-F(y)，x-y〉≥α‖x-y‖2,

(2)

則稱函數(shù)F(x):Rn→Rn強(qiáng)單調(diào)。

引理1[12]函數(shù)F強(qiáng)單調(diào)的充分條件為?F一致正定, 即存在某常數(shù)α>0, 對任意x∈Rn使

xT?Fx≥α‖x‖2。

2 效益函數(shù)

本節(jié)提出新SOC權(quán)互補(bǔ)函數(shù)構(gòu)造效益函數(shù)，并證明其水平集有界性等性質(zhì)。

首先構(gòu)造函數(shù)：

φτ(x,y)=(1+τ)(x+y)-

(3)

其中：τ∈[0,1),w∈K為給定權(quán)向量。 下證φτ(x,y)是SOC權(quán)互補(bǔ)函數(shù)。

定理1 對任意x,y∈Rn, 函數(shù)φτ(x,y)滿足

φτ(x,y)=0?x,y∈K,x°y=w。

證明(?) 若x,y∈K,x°y=w, 則

φτ(x,y)=(1+τ)(x+y)-

(?) 若φτ(x,y)=0, 則

(1+τ)(x+y)=

等式兩邊平方并化簡得

(1+τ)2(x2+y2+2x°y)=

(1+τ)2(x2+y2)+8τx°y+2(1-τ)2w,

即x°y=w。 因此

(1+τ)x=

(1+τ)yK|(1+τ)y|-(1+τ)y∈K。

類似可得

(1+τ)y=

(1+τ)xK|(1+τ)x|-(1+τ)x∈K,

故x,y∈K。證畢。

現(xiàn)基于權(quán)互補(bǔ)函數(shù)φτ(x,y), 構(gòu)造效益函數(shù)

(4)

則求解LSOCWCP(1)可轉(zhuǎn)化為找到無約束極小化問題

minΨ(x)=ψ(x,F(x))

(5)

的全局最小值。

性質(zhì)1 函數(shù)φτ、ψ分別由式(3)和式(4)定義, 令

h=(1+τ)2(x2+y2)+8τx°y+

2(1-τ)2w=(h1;h2)∈R×Rn-1,

(6)

其中:

h1=(1+τ)2(‖x‖2+‖y‖2)+

8τxTy+2(1-τ)2w1,

(7)

h2=2(1+τ)2(x1x2+y1y2)+8τ(x1y2+

y1x2)+2(1-τ)2w2。

(8)

(i) ?xψ(0,0)=?yψ(0,0)=0。

(ii) 若(x,y)≠(0,0)且h∈intK, 則

?xψ(x,y)=

?yψ(x,y)=

(iii) 若(x,y)≠(0,0)且h?intK,

(9)

2)?ψ全局Lipschitz連續(xù), 即對任意(x,y), (a,b)∈Rn×Rn, 存在常數(shù)C≥0使得

‖?ψ(x,y)-?ψ(a,b)‖≤

C‖(x,y)-(a,b)‖。

3)對任意x,y∈Rn,

〈?xψ(x,y),?yψ(x,y)〉≥0,

此等式成立當(dāng)且僅當(dāng)φτ(x,y)=0。

4)對任意x,y∈Rn,

?xψ(x,y)=0??yψ(x,y)=0?φτ(x,y)=0。

證明性質(zhì)2)～4)的證明可由文獻(xiàn)[13]中的引理6和文獻(xiàn)[16]中的定理3.1類似得出，這里省略，下證性質(zhì)1)。

由文獻(xiàn)[13]中的命題2知ψ處處連續(xù)可微。

(i) 當(dāng)(x,y)=(0,0)時(shí),

?xψ(0,0)=?yψ(0,0)=0。

(ii) 當(dāng)(x,y)≠(0,0),h∈intK時(shí), 設(shè)

λ1(h)=h1-‖h2‖,λ2(h)=h1+‖h2‖

是h的譜值。 對式(6)求導(dǎo)得

?xh=2L(1+τ)2x+4τy,?yh=2L(1+τ)2y+4τx,

(10)

故由式(3)、式(4)及式(10)可得結(jié)論。

(iii) 當(dāng)(x,y)≠(0,0)且h?intK時(shí), 由文獻(xiàn)[13]中的命題1類似可證式(9)。證畢。

引理2 設(shè)函數(shù)φτ(x,y)由式(3)定義, 則對任意x,y∈Rn有

‖φτ(x,y)‖≥

證明將SOC權(quán)互補(bǔ)函數(shù)φτ(x,y)與x-取內(nèi)積得

〈x-,(1+τ)(x+y)-z〉=

(1+τ)×[〈x-,x++x-〉+

〈x-,y++y-〉]+〈x-,-z〉=

(1+τ)[‖x-‖2+〈x-,y+〉+

〈x-,y-〉]+〈x-,-z〉。

(11)

因?yàn)閤-∈-K,y-∈-K, -z∈-K, 所以〈x-,y-〉≥0, 〈x-,-z〉≥0。 又因?yàn)閥+∈K, 所以〈x-,y+〉≤0。 因此結(jié)合式(11)和Cauchy-Schwarz不等式得

‖x-‖·‖φτ(x,y)‖≥

〈x-,(1+τ)(x+y)-z〉≥

(1+τ)[‖x-‖2+〈x-,y+〉]≥

(1+τ)[‖x-‖2-‖x-‖·‖y+‖],

即

‖φτ(x,y)‖≥(1+τ)[‖x-‖-‖y+‖]。

同理可證

‖φτ(x,y)‖≥(1+τ)[‖y-‖-‖x+‖]。

因此

‖y-‖-‖x+‖-‖y+‖)。

證畢。

性質(zhì)2 假設(shè)函數(shù)F:Rn→Rn強(qiáng)單調(diào),則對于任意c≥0,水平集Ω={x∈Rn|Ψ(x)≤c}有界。

證明假設(shè)存在一個(gè)無界序列{xk}?Ω。

‖φτ(xk,F(xk))‖→∞,Ψ(xk)→∞,

這與ψ(xk)≤c矛盾, 進(jìn)而結(jié)論成立。

(ii) 當(dāng)

時(shí), 由函數(shù)F強(qiáng)單調(diào)和引理3.2[17]知Ψ(xk)→∞, 這與Ψ(xk)≤c矛盾,故結(jié)論成立。證畢。

3 非單調(diào)無導(dǎo)數(shù)下降算法

本節(jié)給出求解LSOCWCP(1)的非單調(diào)無導(dǎo)數(shù)下降算法，并證明算法的搜索方向滿足下降條件，且全局收斂。

算法1 LSOCWCP的非單調(diào)無導(dǎo)數(shù)下降算法

步1 選取σ,ρ,β,δ∈(0,1),ε≥0,W0=Ψ(x0),G0=1。 設(shè)k=0。

步2 若Ψ(xk)≤ε, 停止。 否則轉(zhuǎn)步3。

步3 計(jì)算步長tk=ρmk, 其中mk是式(12)中非負(fù)整數(shù)m的最小值，

Ψ(xk+ρmdk(βm))≤(1-σρ2m)Wk-

σρ2m(1-βm)×(‖?xψ(xk,F(xk))‖+

‖?yψ(xk,F(xk))‖)2,

(12)

其中：

dk(βm)=dk(xk,βm)=

-β2m(1-βm)?xψ(xk,F(xk))-

(1-βm)?yψ(xk,F(xk)),

(13)

(14)

Gk=(1-δ)Gk-1+1。

(15)

步4 令xk+1=xk+tkdk(βmk), 置k=k+1。 轉(zhuǎn)步2。

注：本文將ZHU等[10]求解CP的非單調(diào)無導(dǎo)數(shù)下降算法推廣到求解LSOCWCP, 步3采用文獻(xiàn)[18]中的非單調(diào)線搜索方式計(jì)算步長tk, 以提高算法性能。

下證當(dāng)Ψ(xk)≠0時(shí), 即迭代過程中若xk不是LSOCWCP的解時(shí), 搜索方向dk(βm)滿足下降條件：

〈?Ψ(xk),dk(βm)〉<0。

〈?Ψ(xk),dk(βm)〉<0,

其中：

?Ψ(xk)=?xψ(xk,F(xk))+

?F(xk)×?yψ(xk,F(xk))。

證明由?F(xk)連續(xù)及xk∈Ω知,存在常數(shù)q>0使得‖?F(xk)‖≤q。 設(shè)

(16)

由式(13)、引理1和性質(zhì)1(3)得

〈?Ψ(xk),dk(βm)〉=-β2m(1-βm)·

〈?xψ(xk,F(xk)),?xψ(xk,F(xk))〉-

(1-βm)〈?xψ(xk,F(xk)),?yψ(xk,F(xk))〉-

β2m(1-βm)·

〈?F(xk)?yψ(xk,F(xk)),?xψ(xk,F(xk))〉-

(1-βm)〈?F(xk)?yψ(xk,F(xk)),?yψ(xk,F(xk))〉≤

-β2m(1-βm)‖?xψ(xk,F(xk))‖2+

qβ2m(1-βm)·

‖?xψ(xk,F(xk))‖·‖?yψ(xk,F(xk))‖-

α(1-βm)‖?yψ(xk,F(xk))‖2=

(‖?xψ(xk,F(xk))‖+‖?yψ(xk,F(xk))‖)2-

β2m(1-βm)(1+q)·

‖?xψ(xk,F(xk))‖·‖?yψ(xk,F(xk))‖=

(‖?xψ(xk,F(xk))‖+‖?yψ(xk,F(xk))‖)2-

‖?xψ(xk,F(xk))‖·‖?yψ(xk,F(xk))‖。

(17)

由式(16)知,式(17)中最后一項(xiàng)的系數(shù)為負(fù), 即

(18)

將式(18)代入式(17)得

〈?Ψ(xk),dk(βm)〉≤

‖?yψ(xk,F(xk))‖)2≤0。

(19)

又因?yàn)槭?19)中的等式成立當(dāng)且僅當(dāng)

‖?xψ(xk,F(xk))‖=‖?yψ(xk,F(xk))‖=0,

所以結(jié)合性質(zhì)1知,dk(βm)滿足下降條件，

〈?Ψ(xk),dk(βm)〉<0。

證畢。

定理3 設(shè)函數(shù)F強(qiáng)單調(diào),則Ψ(xk)≤Wk, 且算法1適定。

證明先用數(shù)學(xué)歸納法證明對任意k≥0, 有Ψ(xk)≤Wk。

當(dāng)k=0時(shí),Ψ(x0)=W0。 假設(shè)Ψ(xk)≤Wk, 則由式(12)得

Ψ(xk+1)≤(1-σρ2m)Wk-

σρ2m(1-βm)×(‖?xψ(xk,F(xk))‖+

‖?yψ(xk,F(xk))‖)2≤

(1-σρ2m)Wk

(20)

由式(14)、式(15)和式(20)得

綜上, 對任意k≥0有

Ψ(xk)≤Wk。

(21)

假設(shè)式(12)不成立,即對任意非負(fù)整數(shù)m有

Ψ(xk+ρmdk(βm))-Wk>

-σρ2mWk-

σρ2m(1-βm)(‖?xψ(xk,F(xk))‖+

‖?yψ(xk,F(xk))‖)2,

(22)

將式(22)兩邊分別除以ρm取極限, 并由式(21)得

σρm(1-βm)×(‖?xψ(xk,F(xk))‖+

‖?yψ(xk,F(xk))‖)2]=0。

這與

〈?Ψ(xk),dk(βm)〉<0,

矛盾。 因此算法1適定。證畢。

定理4 假設(shè)F強(qiáng)單調(diào), 則算法1的生成序列{xk}至少存在一個(gè)聚點(diǎn), 且任一聚點(diǎn)都是LSOCWCP(1)的解。

證明先證{xk}至少有一個(gè)聚點(diǎn)。 由式(14)、式(15)和式(20)得

因此{(lán)Wk}單調(diào)遞減。 又因?yàn)閃k≥0有下界, 所以{Wk}收斂。 結(jié)合0≤Ψ(xk)

下證{xk}的聚點(diǎn)x*是LSOCWCP(1)的一個(gè)解, 即證Ψ(x*)=0。 將式(15)代入式(14)得

(23)

化簡式(23)得

Ψ(xk+1)=Wk+1+(1-δ)Gk(Wk+1-Wk),

(24)

對式(24)兩邊分別取極限得

(25)

又由式(12)得

0≤σρ2m(1-βm)×(‖?xψ(xk,F(xk))‖+

‖?yψ(xk,F(xk))‖)2≤

(1-σρ2m)Wk-Ψ(xk+1)≤

Wk-Ψ(xk+1),

(26)

故由式(25)、式 (26)和夾逼準(zhǔn)則得

因此根據(jù)性質(zhì)1知，Ψ(x*)=0。證畢。

4 數(shù)值算例

運(yùn)用MATLAB R2014進(jìn)行數(shù)值實(shí)驗(yàn)。 在區(qū)間[0,10]內(nèi)隨機(jī)生成非零密度為10%的稀疏矩陣Q∈Rn×n, 令

P=QTQ+ζI,

其中常數(shù)ζ>0,I是維數(shù)為n的單位陣。 取向量q=-e, 其中e=(1,0,…,0)T∈Rn, 參數(shù)σ=0.1,ρ=0.95,β=0.2,δ=0.1,ζ=1,τ=0.1。

本文以Ψ(x)<10-8為終止準(zhǔn)則, 每次實(shí)驗(yàn)隨機(jī)產(chǎn)生10個(gè)問題進(jìn)行求解。 表1和表2中AObj表示效益函數(shù)Ψ(x)的平均值, AIter是算法所需迭代的平均次數(shù)，ACPU是算法CPU的平均時(shí)間。 表1給出維數(shù)n=100, 給定不同初始點(diǎn)時(shí), 算法1分別求解LSOCWCP和LSOCCP的數(shù)值結(jié)果。 表2給出初始點(diǎn)x0=(0;0;…;0)時(shí), 算法1求解不同規(guī)模的LSOCWCP和LSOCCP的數(shù)值結(jié)果。 從表1和表2中均可看出算法1求解LSOCWCP和LSOCCP所需的AIter和ACPU較少, 驗(yàn)證了算法1性能是有效且穩(wěn)定的。

表1 LSOCCP和LSOCWCP在初始點(diǎn)不同時(shí)的實(shí)驗(yàn)結(jié)果Tab. 1 Experimental results of LSOCCP and LSOCWCP with different starting points

表2 LSOCCP和LSOCWCP在規(guī)模不同時(shí)的實(shí)驗(yàn)結(jié)果Tab. 2 Experimental results of LSOCCP and LSOCWCP with different dimensions

5 結(jié)束語

本文提出非單調(diào)無導(dǎo)數(shù)下降算法求解LSOCWCP, 得到良好的數(shù)值效果。目前針對LSOCWCP的研究尚不多見, 關(guān)于此問題還有很多值得思考的地方, 例如: 如何在更弱的假設(shè)下使搜索方向滿足下降條件?在將LSOCWCP轉(zhuǎn)化為無約束極小化問題求解時(shí), 如何構(gòu)造新的效益函數(shù)? 此外, 效益函數(shù)法雖已應(yīng)用到一些優(yōu)化問題中, 但將其用于實(shí)際問題的求解還需進(jìn)一步研究。