用離散化方法證明半定規(guī)劃的拉格朗日強(qiáng)對(duì)偶定理

羅 丹,羅洪林

(重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 重慶 401331)

1 背景

(P) mincTx

s.t.F(x)≥0

半定規(guī)劃也稱為帶有半正定錐約束的線性規(guī)劃,其退化情形包括線性規(guī)劃和凸二次規(guī)劃。半定規(guī)劃廣泛地存在于系統(tǒng)與控制理論[1]、金融工程[2]、量子化學(xué)[3]、信號(hào)處理[4]等諸多領(lǐng)域。 半定規(guī)劃的多項(xiàng)式內(nèi)點(diǎn)算法為求解組合優(yōu)化領(lǐng)域的某些中小規(guī)模的NP難問(wèn)題(如著名的旅行商問(wèn)題[5]和最大割問(wèn)題[6])提供了有效的解決途徑。 自20世紀(jì)90年代初期至今,半定規(guī)劃一直是優(yōu)化領(lǐng)域的一個(gè)熱門的研究課題。

半定規(guī)劃的對(duì)偶理論在半定規(guī)劃的理論研究和算法設(shè)計(jì)中都扮演著十分重要的角色。半定規(guī)劃的對(duì)偶理論研究除了常見的拉格朗日對(duì)偶和共軛對(duì)偶理論外,具有代表性的包括Ramana等提出的廣義拉格朗日slater對(duì)偶理論[7]和極小錐對(duì)偶理論[8]。 本文主要從算法的角度重新考察半定規(guī)劃的拉格朗日對(duì)偶理論。

原始半定規(guī)劃問(wèn)題(P)的拉格朗日對(duì)偶模型為:

(D) max -TrF0Z

s.t.TrFiZ=ci,i=1,…,m

Z≥0

記val(D)為(D)的最優(yōu)目標(biāo)函數(shù)值， 稱(D)可行是指其可行域非空,即：存在Z≥0使得TrFiZ=ci,i=1,…,m; 稱(D)嚴(yán)格可行是指存在Z>0使得TrFiZ=ci,i=1,…,m成立。

內(nèi)點(diǎn)算法是求解中小規(guī)模的半定規(guī)劃的十分有效的求解算法。內(nèi)點(diǎn)算法利用半定規(guī)劃的原始對(duì)偶模型的1階最優(yōu)性條件(KKT條件)建立可行或不可行中心路徑的方式提出了各種可行內(nèi)點(diǎn)算法和不可行內(nèi)點(diǎn)算法。 最近,楊洋等[9]利用不可行中心路徑給出了一種寬領(lǐng)域不可行內(nèi)點(diǎn)算法。 內(nèi)點(diǎn)算法由于需要儲(chǔ)存和分解牛頓矩陣,這將占用大量的內(nèi)存空間且十分耗時(shí)，在2002年,Helmberg[10]指出:在一般的計(jì)算機(jī)處理系統(tǒng)上通過(guò)合理的等待時(shí)間,用內(nèi)點(diǎn)算法能有效計(jì)算的半定規(guī)劃問(wèn)題,其矩陣變量n≤200,約束的個(gè)數(shù)m≤3 000。 截至2013年,Huang等[11]指出,目前的內(nèi)點(diǎn)算法一般可以有效求解的中小規(guī)模的半定規(guī)劃的矩陣變量n≤1 000,約束的個(gè)數(shù)m≤10 000。

如何為大規(guī)模的半定規(guī)劃問(wèn)題設(shè)計(jì)有效的求解算法是一個(gè)有待解決的問(wèn)題。 為了擺脫牛頓矩陣的儲(chǔ)存和分解,受Yang[12]的啟發(fā),本文將從強(qiáng)對(duì)偶定理的一種新的證明方法來(lái)闡述半定規(guī)劃的一種新的求解算法。

本文的第1部分利用離散化方法將半定規(guī)劃問(wèn)題近似地轉(zhuǎn)換為一個(gè)線性規(guī)劃問(wèn)題并給出了2個(gè)問(wèn)題的最優(yōu)解的近似程度的刻畫。本文的第2部分給出了強(qiáng)對(duì)偶定理的一個(gè)新的證明方法以及半定規(guī)劃的一種新的離散化求解算法及其收斂性證明。 針對(duì)本文提出的半定規(guī)劃的一種新的理論算法,在第3部分提出了該算法數(shù)值實(shí)現(xiàn)時(shí)可能面臨的幾個(gè)待解決的問(wèn)題。 附錄部分呈現(xiàn)了半定規(guī)劃的強(qiáng)對(duì)偶定理的經(jīng)典證明過(guò)程以方便讀者比較它與離散化證明方法之間的異同。

2 半定規(guī)劃的離散化方法

本節(jié)主要介紹對(duì)偶半定規(guī)劃(D)的離散化方法以及(D)的最優(yōu)解與離散化問(wèn)題的最優(yōu)解之間的誤差刻畫。為了半定規(guī)劃的離散化方法的描述完整性,首先引入Yang[12]關(guān)于原始半定規(guī)劃問(wèn)題(P)的離散化過(guò)程:

第1步利用{x∈Rm|F(x)≥0}與{x∈Rm|yTF(x)y≥0,?y∈Rn}的等價(jià)性,將(P)等價(jià)地轉(zhuǎn)化為如下形式的優(yōu)化問(wèn)題:

mincTx

s.t.yTF(x)y≥0

y∈Rn

(1)

第2步將集合{y∈Rn|yTF(x)y≥0}正則化為{y∈Rn|yTF(x)y≥0,yTy=1},則問(wèn)題(1)可等價(jià)地表示為如下的線性半無(wú)限規(guī)劃問(wèn)題:

mincTx

s.t.aT(y)x+b(y)≥0

y∈Y

(2)

其中Y={y∈Rn|yTy=1},aT(y)=(yTF1y,yTF2y,…,yTFmy),bT(y)=yTF0y

記

問(wèn)題(2)關(guān)于κ∈R的下水平集定義為:

第3步選取有限網(wǎng)格Yd?Y離散化問(wèn)題(2),得到一個(gè)線性規(guī)劃問(wèn)題:

mincTx

s.t.aT(y)x+b(y)≥0

y∈Yd

(3)

網(wǎng)格Yd與集合Y的Hausdorff距離定義為

記

通過(guò)上述離散化方法可將(P)近似地轉(zhuǎn)換為一列線性規(guī)劃問(wèn)題進(jìn)行近似求解,求解的精度取決于網(wǎng)格Yd的取法,具體參見文獻(xiàn)[12]中的引理2。

眾所周知,不論是半定規(guī)劃還是線性規(guī)劃,研究其對(duì)偶理論的主要目的之一就是化解問(wèn)題求解的難度,即:相較于原問(wèn)題,當(dāng)對(duì)偶問(wèn)題的求解更加容易時(shí),在強(qiáng)對(duì)偶定理的理論支撐下,可以通過(guò)求解其對(duì)偶問(wèn)題而獲得原問(wèn)題的解?；诖?利用Dattorro[13]中的:

(4)

給出對(duì)偶半定規(guī)劃問(wèn)題(D)的離散化過(guò)程:

第1步利用等式(4)將對(duì)偶半定規(guī)劃問(wèn)題(D)等價(jià)地轉(zhuǎn)化成如下形式的優(yōu)化問(wèn)題:

(5)

第2步通過(guò)bj≥0,j=1,2,…的適當(dāng)選取(仍然記為bj≥0,j=1,2,…),將向量zj∈Rn,j=1,2,…單位化,則式(5)可等價(jià)地轉(zhuǎn)換為:

(6)

記

i=1,…,m,zj∈Z′}

問(wèn)題(6)關(guān)于λ∈R的下水平集定義為:

第3步選取有限網(wǎng)格Zk?Z′,不妨設(shè)Zk含有k個(gè)向量z1,z2,…,zk,則與之對(duì)應(yīng)的k個(gè)非負(fù)實(shí)數(shù)為b1,b2,…,bk,現(xiàn)通過(guò)該網(wǎng)格離散化問(wèn)題(6)得到一個(gè)線性規(guī)劃問(wèn)題:

(7)

網(wǎng)格Zk與集合Z的Hausdorff距離定義為:

記

i=1,…,m,z∈Zk}

為了利用離散化方法證明半定規(guī)劃的強(qiáng)對(duì)偶定理,需要建立以下幾個(gè)結(jié)論：

定理1 如果(P)嚴(yán)格可行,(D)可行,那么對(duì)任意給定的λ∈R,水平集

有界。

證明假設(shè)存在一個(gè)λ0∈R使得水平集

無(wú)界,則存在非負(fù)數(shù)列{bj}?L≥(BD(Z),F0,λ0)滿足:

(8)

(9)

且

zj∈Z′={z∈Rn|||z||=1}=Y

對(duì)任意給定的y∈Y,則存在序列{vj}滿足

(10)

(11)

由級(jí)數(shù)收斂的必要條件和式(9)可得:

再結(jié)合式(10)以及式(11)可推得:

yTF0y=0,?y∈Y

(12)

(13)

(14)

(15)

由級(jí)數(shù)收斂的必要條件和(ref{eq7})可得:

再結(jié)合式(14)與(15)可推得:

yTFiy=0,?y∈Y,i=1,2,…,m

(16)

故,由式(12)和(16)可得:

?y∈Y

由于(P)與式(2)等價(jià),不難發(fā)現(xiàn)上式與半定規(guī)劃問(wèn)題(P)的嚴(yán)格可行性假設(shè)矛盾。

由于(D)的嚴(yán)格可行性必蘊(yùn)含其可行性,則由定理1可得如下推論：

推論1 問(wèn)題(P)和(D)都嚴(yán)格可行,則對(duì)λ∈R,水平集

有界。

命題1 若問(wèn)題(P)和(D)都嚴(yán)格可行,則對(duì)κ∈R,水平集

有界。

證明由Yang[12]中的引理1和半定規(guī)劃(P)嚴(yán)格可行性蘊(yùn)含問(wèn)題的可行性得結(jié)論成立。

如下2個(gè)命題揭示了:用離散化方法可以求得半定規(guī)劃問(wèn)題(P)和(D)滿足任意精度的近似解。

證明因?yàn)?P)與式(2)等價(jià),(D)與式(6)等價(jià),由定理1及文獻(xiàn)[14]中的定理4.4可以證得。

類似地,可以利用推論2和命題1以及文獻(xiàn)[14]中的定理4.4可以證明下面這個(gè)命題：

命題3 若問(wèn)題(P)和(D)都嚴(yán)格可行,那么,

3 強(qiáng)對(duì)偶定理的離散化證明方法及其在算法設(shè)計(jì)中的應(yīng)用

當(dāng)半定規(guī)劃問(wèn)題(P)和(D)滿足一定的條件時(shí),若能推出對(duì)偶間隙:

val(P)-val(D)=0

則稱為半定規(guī)劃的強(qiáng)對(duì)偶定理。 關(guān)于半定規(guī)劃的強(qiáng)對(duì)偶定理的經(jīng)典證明方法請(qǐng)參見附錄。2005年,Yang[12]通過(guò)原始半定規(guī)劃(P)的離散化方法證明了在原始半定規(guī)劃(P)可行和對(duì)偶半定規(guī)劃(D)嚴(yán)格可行的假設(shè)條件下的強(qiáng)對(duì)偶定理。 值得指出的是,可以利用Yang[12]關(guān)于原始半定規(guī)劃(P)的離散化方法為(P)的求解設(shè)計(jì)一種新的求解算法:利用文獻(xiàn)[14-15]中關(guān)于半無(wú)限規(guī)劃的離散化算法近似地求解(P)。

下面利用對(duì)偶半定規(guī)劃問(wèn)題(D)的離散化方法重新給出半定規(guī)劃的另外2個(gè)強(qiáng)對(duì)偶定理的證明,進(jìn)而為對(duì)偶半定規(guī)劃問(wèn)題(D)設(shè)計(jì)一種新的求解算法。

3.1 強(qiáng)對(duì)偶定理的證明

定理2 如果(P)嚴(yán)格可行,(D)可行,則val(P)=val(D),且(D)的最優(yōu)解Z*最優(yōu)可達(dá)。

證明定理1可知,對(duì)任意給定的λ∈R,水平集L≥(BD(Z),F0,λ)是有界閉的,則L≥(BD(Z),F0,λ)是緊集且當(dāng)λ充分大時(shí)非空。 因此,(D)的最優(yōu)解可以在可行域中取到。

現(xiàn)定義網(wǎng)格Zk={z1,z2,…,zk},則式(7)可以等價(jià)地表示成如下形式的線性規(guī)劃問(wèn)題:

(17)

maxcTx

s.t.aT(yj)x+b(yj)≥0

yj∈Yk,j=1,…,k

(18)

由半定規(guī)劃的弱對(duì)偶定理有:

val(P)≥val(D)

(19)

(20)

因此,對(duì)于充分小的dZk,val(Zk)有界。故由線性規(guī)劃的強(qiáng)對(duì)偶定理,有

val(Zk)=val(xk)

(21)

由于(P)的可行解包含式(18)的可行解,則有

val(P)≤val(xk)

(22)

結(jié)合式(20)、(21)和(22),令dYk→0可得:

val(P)≤val(D)

(23)

綜合式(19)和(23)得: val(P)=val(D)

定理3 如果(P)和(D)都嚴(yán)格可行,則 val(P)=val(D),且(P)的最優(yōu)解x*和(D)的最優(yōu)解Z*都最優(yōu)可達(dá)。

證明由命題1和推論1可知,對(duì)任意給定的λ∈R,水平集L≥(XP(Y),c,κ)和L≥(BD(Z),F0,λ)是有界閉的,則L≥(XP(Y),c,κ),L≥(BD(Z),F0,λ)是緊集且分別當(dāng)κ、λ充分大時(shí)非空。 因此,(P)和(D)的最優(yōu)解可以在其各自的可行域中取到。

現(xiàn)定義網(wǎng)格Zk={z1,z2,…,zk},則式(7)可以等價(jià)地表示成如下形式的線性規(guī)劃問(wèn)題:

(24)

maxcTx

s.t.aT(yj)x+b(yj)≥0

yj∈Yk,j=1,…,k

(25)

(26)

(27)

因此,對(duì)于充分小的dYk, val(xk)有界；對(duì)于充分小的dZk, val(Zk)有界。 故由線性規(guī)劃的強(qiáng)對(duì)偶定理,有

val(Zk)=val(xk)

(28)

結(jié)合式(26)、(17)和(28),令dYk→0,dZk→0可得:

val(P)=val(D)

(29)

3.2 半定規(guī)劃的離散化算法

求解一般的中小規(guī)模的半定規(guī)劃問(wèn)題時(shí)可以用CVX[16]中的SDPT3或SeDuMi求得滿足任意精度的近似解。 不論是SDPT3還是SeDuMi,其求解原理都是利用原始對(duì)偶內(nèi)點(diǎn)算法,需要儲(chǔ)存和分解牛頓矩陣,這將占用大量的內(nèi)存空間且十分耗時(shí)。

根據(jù)文獻(xiàn)[14]對(duì)半無(wú)限規(guī)劃問(wèn)題的離散化算法的描述,當(dāng)(P)嚴(yán)格可行,(D)可行,針對(duì)對(duì)偶半定規(guī)劃問(wèn)題(D),設(shè)計(jì)如下算法：

算法1 首先將半定規(guī)劃對(duì)偶問(wèn)題(D)轉(zhuǎn)換為等價(jià)的線性半無(wú)限規(guī)劃問(wèn)題(16)，然后,給定一個(gè)步長(zhǎng)向量h∈Rm,其中hj>0,j=1,…,m,并且固定一個(gè)z0∈Rm,定義網(wǎng)格

Gh={z|(z-z0)j=αjhj,αj∈N,j=1,…,m}

并且

Zh=Z∩Gh

具體步驟如下:

① 設(shè)hi+1=(1/ni)hi,ni∈N,ni≥2。

④ 如果i>i0(預(yù)先規(guī)定步數(shù))則停止,否則繼續(xù)第(i+1)步。

注：1) 該離散化方法在求解對(duì)偶半定規(guī)劃問(wèn)題(D)時(shí),無(wú)需儲(chǔ)存和分解牛頓矩陣;

下面簡(jiǎn)單地給出該算法的收斂性證明。

4 結(jié)論和展望

利用離散化方法,本文給出了強(qiáng)對(duì)偶定理的一種新的證明方法,并利用該方法設(shè)計(jì)了一種半定規(guī)劃的求解算法。 本文僅從理論上給出了半定規(guī)劃的求解算法及其收斂性分析,值得指出的是，雖然該算法擺脫了傳統(tǒng)的內(nèi)點(diǎn)算法對(duì)于牛頓矩陣的儲(chǔ)存和分解,但是在算法步驟中涉及隨機(jī)變量,這可能會(huì)導(dǎo)致數(shù)值實(shí)驗(yàn)結(jié)果的不穩(wěn)定性。若讓算法中的隨機(jī)變量滿足一定的概率分布,對(duì)于滿足均勻分布或標(biāo)準(zhǔn)正態(tài)分布等是否可以使得數(shù)值實(shí)驗(yàn)結(jié)果更加穩(wěn)定， 如何改進(jìn)該算法以適用于有效地求解大規(guī)模的半定規(guī)劃問(wèn)題， 這些是接下來(lái)準(zhǔn)備研究的問(wèn)題。

參考文獻(xiàn)：

[1] YAO D,ZHANG S Z,ZHOU X Y.Control theory stochastic linear-quadratic control via semidefinite programming [J].Society for Industrial and Applied Mathematics,2001,40:1-23.

[2] DALAKOURAS G V,KWON R H,PARDALOS P M.Semidefinite programming approaches for bounding asian option prices [J].Computational Methods in Financial Engineering,2008,103-116.

[3] DING Y,GE D,WOLKOWICZ H.On equivalence of Semidefinite relaxations for quadratic matrix programming [J].Mathematics of Operations Research,2011,36:8-104.

[4] BISWAS P,TOH K C,YE Y.A distributed Semidefinite approach for large-scale noisy anchor-free graph realization with applications to molecular conformation [J].Society for Industrial and Applied Mathematics,2008:1251-1277.

[5] KLERK E D,PASECHNIK D V,SOTIROV R.On semidefinite programming relaxations of the traveling salesman problem [J].Society for Industrial and Applied Mathematics,2008,19:1559-1573.

[6] GRIPPO L,PALAGI L,PICCIALLI V.An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem [J].Mathematical Programming,2011,126:119-146.

[7] RAMANA M V.An exact duality theory for semidefinite programming and its complexity implications [J].Mathematical Programming,1997,77:129-162.

[8] Ramana M V,Tuncxelz L,Wolkowicz H.Strong duality for semidefinite programming [J].Society for Industrial and Applied Mathematics,1997,7(3):641-662.

[9] 楊洋,羅洪林,羅慧林.關(guān)于半定規(guī)劃的一種寬鄰域不可行內(nèi)點(diǎn)算法的注記 [J].運(yùn)籌學(xué)學(xué)報(bào),2016,20(2):79-87.

[10] HELMBERG C.Invited Review,Semidefinite programming [J].European Journal of Operational Research,2002,137:461-482.

[11] HUANG A Q,XU C X.A trust region method for solving semidefinite programs [J].Computational Optimization and Applications,2013,55:49-71.

[12] YANG Q Z.A new proof of the strong duality theorem for semidefinite programming [J].it Mathematical analysis and applications,2005,303:622-626.

[13] DATTORRO J.Convex optimization and euclidean distance geometry[Z].Meboo Publishing USA,2005.

[14] HETTICH R,KORTANEK K O.Semi-infinite programming:Theory,methods,and application [J].Society for Industrial and Applied Mathematics,1993,35:380-429.

[15] HETTICH R.An implementation of a discretization method for semi-infinite programming [J].Math Programming,1986,34:354-361.

[16] GRANT M,BOYD S.The CVX Users’ Guide (Release 2.0 (Beta))[EB/OL].[2018-01-01].http://cvxr.com/cvx/(221) March 2013.

[17] ALIZADEH F.Interior point methods in semidefinite programming with applications to combinatorial optimization [J].Society for Industrial and Applied Mathematics,1995,5:13-51.

附錄A

定理4[17]令

z1=inf{C·X:Ai·X=bi,X≥0}

z2=sup{bTy:C-∑yiAi≥0}

如果存在一個(gè)m維向量y,使得ATy>0,那么z2=z1。

Mat(ATy1)≤0且bTy1>0

意味著對(duì)偶問(wèn)題是無(wú)界的。由于任意的對(duì)偶可行解y能增加一個(gè)任意大的正乘子在y1前,得到另一個(gè)可行解有巨大的目標(biāo)函數(shù)值。 因此,z2=z1=+∞。 可以假設(shè)z1和z2都是有限的， 假設(shè)z2

C·X=z2

AvecX=b

X≥0

是不可行的。 因此,通過(guò)推廣的Farkas引理2.3,存在一個(gè)標(biāo)量y0和m維向量y,使得

且z2y0+bTy<0

(19)

其中vecAi是A的第i行。 對(duì)y0,下列之一成立。

1) 若y0=0,式(19)等價(jià)于

Mat(ATy)≤0 且bTy>0

通過(guò)推廣的Farkas引理得AvecX=b且X≥0是不可行的， 因此z1=+∞。

2) 若y0=0,則式(19)除以y0得

C-Mat(AT(-y/y0))≥0且

z2-bT(y/y0)<0

意味著z2不是對(duì)偶問(wèn)題的最優(yōu)值。

3) 若y0<0,則式(19)除以-y0得

-C+Mat(AT(-y/y0))≥0且

-z2+bT(-y/y0)<0

事實(shí)上,由于是嚴(yán)格不等式,則存在ε>0,使得

-C+Mat(AT(-y/y0))≥0且

-z2+bT(-y/y0)<-ε

同樣地,通過(guò)z2的最優(yōu)性,存在一個(gè)y*,使得

C-Mat(ATy*)≥0且z2-bTy*<ε

最后2個(gè)式子相加得

Mat(AT(-y/y0-y*))≥0且

bT(-y/y0-y*)<0

再次通過(guò)推廣的Farkas引理得原問(wèn)題不可行且z1=∞，與假設(shè)z2