二階錐權(quán)互補(bǔ)問(wèn)題的一類含參數(shù)效益函數(shù)

遲曉妮， 崔然然， 楊綺麗， 趙 敏

(1.桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林 541004;2.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004;3.桂林電子科技大學(xué) 廣西自動(dòng)檢測(cè)技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

n維二階錐Kn定義為

Kn={x=(x1;x2)∈R×Rn-1:x1≥‖x2‖}，

考慮二階錐權(quán)互補(bǔ)問(wèn)題(WSOCCP)：尋找一向量ζ∈Rn，使得

(1)

其中F(ζ):Rn→Rn為連續(xù)可微函數(shù)，w∈Kn為給定的權(quán)向量。當(dāng)權(quán)向量w為零向量時(shí)，式(1)退化為二階錐互補(bǔ)問(wèn)題(SOCCP)[1]：

(2)

作為一類重要的錐優(yōu)化問(wèn)題，WSOCCP是Rn上的權(quán)互補(bǔ)問(wèn)題(WCP)在二階錐上的推廣，其在經(jīng)濟(jì)學(xué)、力學(xué)、工程設(shè)計(jì)等方面有著廣泛的應(yīng)用[2]。WCP中非零權(quán)向量的存在使得WCP[3-5]的理論和算法比互補(bǔ)問(wèn)題(CP)復(fù)雜得多，因此目前關(guān)于WCP的研究并不多見(jiàn)，如Zhang[6]運(yùn)用光滑牛頓法求解單調(diào)線性WCP，Tang[7]給出一種新的光滑算法求解大規(guī)模線性WCP。

下降算法是求解CP的有效算法[8-9]，其基本思想是基于效益函數(shù)將原問(wèn)題轉(zhuǎn)化為一個(gè)等價(jià)的無(wú)約束極小化問(wèn)題[10]，利用下降算法求解此極小化問(wèn)題，進(jìn)而得到原問(wèn)題的解。

鑒于此，提出一類含參數(shù)二階錐權(quán)互補(bǔ)函數(shù)，構(gòu)造WSOCCP的效益函數(shù)，討論其光滑性，并基于此效益函數(shù)將WSOCCP轉(zhuǎn)化為無(wú)約束極小化問(wèn)題，利用下降算法求解，從而得到原問(wèn)題的解。

1 預(yù)備知識(shí)

與二階錐相伴的歐幾里得約當(dāng)代數(shù)有如下性質(zhì)[11]。

對(duì)任意

x=(x1;x2)∈R×Rn-1,y=(y1;y2)∈R×Rn-1，

x和y的約當(dāng)積定義為

定義箭形矩陣

其中I為適當(dāng)維數(shù)的單位陣，易證

定義1(譜分解) 對(duì)任意

x=(x1;x2)∈R×Rn-1，

與二階錐相伴的譜分解定義為

x=λ1(x)u1(x)+λ2(x)u2(x)，

譜值λ1(x)、λ2(x)和譜向量u1(x)、u2(x)定義為

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

其中ω∈Rn-1為滿足‖ω‖=1的任意向量。對(duì)任意x∈Rn，有

2 一類含參數(shù)效益函數(shù)

定義函數(shù)φτ(x,y):Rn×Rn→Rn為

(x+y)，

(3)

其中：參數(shù)τ∈[0,4)；w∈Kn為給定的權(quán)向量。定義效益函數(shù)ψ(x,y):Rn×Rn→R為

(4)

則式(1)等價(jià)于無(wú)約束極小化問(wèn)題：

minf(ζ)=ψ(ζ,F(ζ))。

(5)

引理1令

(h1;h2)∈R×Rn-1，

(6)

h1=‖x‖2+‖y‖2+(τ-2)xTy+(4-τ)w1，

(7)

h2=2x1x2+2y1y2+(τ-2)(x1y2+

y1x2)+(4-τ)w2，

(8)

對(duì)任意

x=(x1;x2)，

y=(y1;y2)∈R×Rn-1，

w=(w1;w2)∈Kn，

若h2≠0，則

證明運(yùn)用Cauchy-Schwartz不等式可得

成立。將

(9)

U=λ1(h)‖h2‖2=(h1-‖h2‖)‖h2‖2=

[‖x‖2+‖y‖2+(τ-2)(x1y1+x2Ty2)+

(4-τ)w1]‖h2‖2-[4x12‖x2‖2+

4y12‖y2‖2+(τ-2)2(x12‖y2‖2+

y12‖x2‖2)+(4-τ)2‖w2‖2+8x1y1x2Ty2+

2(τ-2)2x1y1x2Ty2+4(τ-2)(x12x2Ty2+

x1y1‖x2‖2+x1y1‖y2‖2+y12x2Ty2)+

4(4-τ)(x1x2Tw2+y1y2Tw2)+

2(τ-2)(4-τ)(x1y2Tw2+y1x2Tw2)]‖h2‖，

x1x2Tw2+2(τ-2)(x12x2Ty2+x1y1‖x2‖2+

x1y1‖x2‖2+y12x2Ty2)+(τ-2)×

(4-τ)(y1x2Tw2+x1y2Tw2)+(τ-2)2×

(x1y1x2Ty2+y12‖y2‖2)+2(τ-2)×

(x12x2Ty2+x1y1‖y2‖2)+(τ-2)2×

(x12‖y2‖2+2x1y1x2Ty2+y12‖x2‖2)+

則由w=(w1;w2)∈Kn得，

y1y2Tw2+(τ-2)x1y2Tw2+(τ-2)×

因此，結(jié)合Cauchy-Schwartz不等式，τ∈[0,4)和w=(w1;w2)∈Kn得，

性質(zhì)1設(shè)φτ、ψ分別由式(3)、(4)定義，則

1)φτ(x,y)為二階錐權(quán)互補(bǔ)函數(shù)。

2)對(duì)任意(x,y)∈Rn×Rn，有ψ(x,y)≥0。

3)設(shè)h=(h1;h2)由式(6)～(8)定義，令

(z1;z2)∈R×Rn-1，

(10)

則ψ在Rn×Rn上處處光滑，且

b)若(x,y)≠(0,0)，h∈intKn，則

c)若(x,y)≠(0,0)，h?intKn，則

(11)

證明1)要證φτ(x,y)是二階錐權(quán)互補(bǔ)函數(shù)，即證

?假設(shè)φτ(x,y)=0，則

(x+y)=0。

2)由ψ(x,y)的定義可證。

3)先證ψ在Rn×Rn上處處可微。由文獻(xiàn)[9]引理3.1知，ψ在任意點(diǎn)(x,y)∈Rn×Rn處處可微。

a)若(x,y)=(0,0)，則

b)若(x,y)≠(0,0)，h?intKn，易證

(12)

設(shè)λ1(h)、λ2(h)是h的譜值，由定義1得，

(13)

則由式(10)、(12)、(13)可得，

(14)

(15)

其中，

若h2≠0，

c)由文獻(xiàn)[8]類似可證式(11)。

當(dāng)(a,b)=(0,0)或

φτ(x,y)。

(16)

因?yàn)棣?intKn，所以由式(11)得

φτ(a,b)=

φτ(a,b)。

(17)

又由引理1和文獻(xiàn)[8]的證明可得，

(18)

所以由式(16)～(18)可知，當(dāng)(x,y)→(a,b)時(shí)，

定理1設(shè)φτ、ψ分別由式(3)、(4)定義，對(duì)任意(x,y)∈Rn×Rn，有

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

類似文獻(xiàn)[1]可證，證明省略。

3 下降算法及數(shù)值算例

推廣CP的下降算法[9]求解式(1)，并給出數(shù)值算例。

f(ζk+ρmdk(ζk,γm))≤f(ζk)-

(19)

成立的非負(fù)整數(shù)m的最小值mk,其中σ,ρ,γ∈(0,1)，

式(19)無(wú)需通過(guò)求F的導(dǎo)數(shù)計(jì)算搜索方向和步長(zhǎng)，減少了算法的工作量。由文獻(xiàn)[9]可知，當(dāng)F單調(diào)時(shí)，總存在γm∈[0,1)，使得dk(ζk)滿足下降條件式(19)。

選取參數(shù)ρ=0.35,γ=0.5,σ=0.15，隨機(jī)生成矩陣N∈Rn×n及向量q∈Rn。令M=NTN，每次實(shí)驗(yàn)均隨機(jī)生成10個(gè)線性WSOCCP：

運(yùn)用下降算法進(jìn)行求解。令ζ0=(1,0,…,0)T，τ=1.5,w=(1,0,…,0)T，得到下降算法求解不同規(guī)模WSOCCPs的數(shù)值結(jié)果，如表1所示；令τ=1,w=(1,0,…,0)T，n=100，得到下降算法求解不同初始點(diǎn)WSOCCP的數(shù)值結(jié)果，如表2所示，其中AObj為ψ(ζ,F(ζ))的平均值，ACPU、AIter分別為算法終止迭代時(shí)的平均CPU運(yùn)行時(shí)間和平均迭代次數(shù)。從表1、2可看出，下降算法能有效地求解WSOCCP。

表1 下降算法求解不同規(guī)模WSOCCP的數(shù)值結(jié)果

表2 下降算法求解不同初始點(diǎn)WSOCCP的數(shù)值結(jié)果

4 結(jié)束語(yǔ)

基于一類新的含參數(shù)效益函數(shù)，本文將求解CP的下降算法推廣到WSOCCP中。討論含參數(shù)效益函數(shù)的光滑性，并給出其雅可比矩陣。算法無(wú)需利用F的導(dǎo)數(shù)計(jì)算迭代步長(zhǎng)，縮短了算法的運(yùn)行時(shí)間。數(shù)值結(jié)果驗(yàn)證了算法的有效性。