一般線性錐優(yōu)化問題強錐對偶定理的新證明

(長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023) (湖北省洪湖市第一高級中學(xué)，湖北 洪湖 433200)

線性錐優(yōu)化是決策變量取自錐，約束函數(shù)和目標(biāo)函數(shù)均為線性函數(shù)的一類優(yōu)化問題的總稱。作為凸優(yōu)化的特例， 它始于Nesterov和Nemirovskii[1]的工作，主要包括線性規(guī)劃、二階錐優(yōu)化和半定規(guī)劃3種類型。后兩種類型是線性規(guī)劃在非線性優(yōu)化領(lǐng)域的擴展，具有許多類似于線性規(guī)劃的結(jié)構(gòu)，實際應(yīng)用非常廣泛，例如線性錐優(yōu)化在電氣工程中的應(yīng)用[2,3]、二階錐規(guī)劃在電氣工程中的應(yīng)用[4]、二階錐規(guī)劃在地質(zhì)研究中的應(yīng)用[5]、半定規(guī)劃在信息與計算科學(xué)中的研究[6]。

對于一個已知的線性規(guī)劃，總是可以求出它的對偶線性規(guī)劃。當(dāng)原問題不易求解時，尋找等價的對偶問題進(jìn)行求解是一個不錯的選擇，這種選擇的理論基礎(chǔ)就是強對偶定理。近年來許多人對強對偶定理的研究做出了貢獻(xiàn)；如余維等[7]研究了廣義弧式連通凸錐優(yōu)化問題的最優(yōu)性條件及其對偶問題；羅丹和羅洪林[8]采用離散化方法證明了Lagrange強對偶定理。

一般線性錐優(yōu)化問題和其對偶問題如下：

(1)

(2)

其中，A∈Rm×q；b∈Rm；c∈Rq；K和K*是Rq內(nèi)一對互為對偶的正則錐。引用凸分析的一些基本概念和結(jié)果見文獻(xiàn)[9～11]。

定理1[1]錐對偶問題(2)的目標(biāo)最優(yōu)值不超過原問題(1)的目標(biāo)最優(yōu)值。

1 預(yù)備知識

引理1[10,11](凸集分離定理)設(shè)S,T是Rq中2個具有非空相對內(nèi)點的凸集，則S和T正常分離的充要條件是它們的相對內(nèi)點的交為空，即:

ri(S)∩ri(T)=?

引理2(線性不等式組的選擇定理)設(shè)A∈Rm×q,b∈Rm和c,λ∈Rq，μ,p∈R。如果存在點x0∈Rq滿足Ax0=b和cTx0≤p，那么不等式組:

Ax=b

cTx≤p

λTx>0x∈Rq

(3)

無解的充分必要條件是不等式組:

ATy-μc+λ=0

(4)

bTy-μp≥0y∈Rmμ≥0

(5)

有解。

證明假定不等式組(3)有解，可證不等式組(4)、(5)無解。若不然，則存在y∈Rm和μ≥0滿足式(4)和式(5)。在式(4)兩邊同時左乘xT，并利用不等式組(3)得到:

0=xT(ATy-μc+λ)

=(Ax)Ty-μcTx+λTx

≥bTy-μp+λTx

>bTy-μp

與式(5)矛盾。

若不等式組(3)無解， 則線性規(guī)劃問題:

maxλTx

s.t.Ax=b

cTx≤p

是可行的且有上界0。應(yīng)用線性規(guī)劃強對偶定理[12,13]，該問題的對偶問題是可解的，且對偶目標(biāo)最優(yōu)值小于或者等于0。

綜上，引理2成立。

引理3[1]線性函數(shù)f(x)=cTx在凸集S的相對內(nèi)點x*∈ri(S)取得最大值或者最小值當(dāng)且僅當(dāng)f(x)在S上恒為常數(shù)。

引理4是凸優(yōu)化強對偶定理，即凸優(yōu)化的Lagrange對偶無對偶間隙。

引理4[11]設(shè)f:Rq→(-∞,+∞]是正常凸函數(shù)，A∈Rm×q，b∈Rm。假定存在點x0∈ri(dom(f))使得Ax0≤b。如果優(yōu)化問題:

(6)

有下界，那么相應(yīng)的Lagrange對偶問題:

是可解的且對偶間隙為0。

證明設(shè)τ*代表問題(6)的最優(yōu)目標(biāo)值，定義2個集合S和T：

T={(z,τ*)∈Rm×R|z≤0}

M={(Ax-b,τ)∈Rm×R|(x,τ)∈Epi(f)}

由引理1，存在非零向量(λ,β)∈Rm×R使得:

βτ*+λTz≤βτ+λTw?(w,τ)∈S,?(z,τ*)∈T

(7)

(8)

因為(0,1)∈Rm×R是集合S的回收方向，所以β≥0。此外,由x0是dom(f)的相對內(nèi)點得到w0=Ax0-b是凸集D的相對內(nèi)點，其中：

D={w∈Rm|?τ∈Rs.t. (w,τ)∈S}

={Ax-b∈Rm|x∈dom(f)}

=A·dom{f}-b

如果β=0，在式(7)中令z=w0，可以得到:

由引理3 知，線性函數(shù)λTw在凸集D上取常數(shù)值，這與嚴(yán)格不等式(8)矛盾，因此β>0。

不妨設(shè)β=1，由式(7)得：

(9)

這里z≤0。容易驗證λ≥0。若不然，則存在λ的某個分量λi<0，這時令zi→-∞(z的其余分量為0)，則與式(9)矛盾。此外由式(9)還有:

=d(λ)

≤d*

此外，注意到弱對偶關(guān)系τ*≥d*總是滿足，因此有d(λ)=d*=τ*。于是對偶問題有解λ，從而結(jié)論成立。

值得注意的是，引理4的條件并不能保證問題(6)是可解的。如：

min ex

s.t.x≤0

是不可解的，但滿足引理4的條件。

2 利用選擇性定理改進(jìn)的證明

與線性規(guī)劃對偶理論不同的是，強錐對偶定理要求線性錐優(yōu)化問題滿足嚴(yán)格可行性，也稱Slater條件。對于原問題(1)嚴(yán)格可行性要求存在x∈int(K)滿足Ax=b；對于對偶問題(2)則要求存在y∈Rm滿足c-ATy∈int(K*)。

下面是Nesterov和Nemirovskii[1]給出的強錐對偶定理，其證明過程也可以參見文獻(xiàn)[14]。

定理2對于錐問題(CP)和它的對偶問題(D)：

(1)如果錐問題(CP)下有界且嚴(yán)格可行，則對偶問題(D)可解，且p*=d*；

(2)如果對偶問題(D)上有界且嚴(yán)格可行，則錐問題(CP)可解，且p*=d*。

證明(1)假設(shè)錐問題(CP)下有界且嚴(yán)格可行，先考慮c≠0的情形。由假設(shè)，存在x0∈int(K)?Rq滿足Ax0=b。定義集合：

U={x∈Rq|Ax=b,cTx≤p*}

其次證明U∩int(K)=? 。若U∩int(K)≠? ，則存在點x1∈U∩int(K)使得cTx1≤p*。對于充分接近x1的點x，當(dāng)然滿足x∈int(K)。當(dāng)c≠0時， 存在點x∈U使得cTx

由引理1，存在非零向量λ∈Rq使得:

(10)

由此，線性不等式組:

Ax=b

cTx≤p*

λTx>0

無解。由引理2知，存在y∈Rm和μ≥0使得:

ATy+λ=μc

(11)

bTy-μp*≥0

(12)

下面用反證法證明μ≠0。若不然，則由式(12)得到bTy≥0。另一方面，將x0與式(11)兩邊作內(nèi)積后可以得到:

〈λ,x0〉=-〈ATy,x0〉=-〈y,Ax0〉=-bTy

因為0≠λ∈K*和x0∈int(K) ，所以〈λ,x0〉>0，從而產(chǎn)生矛盾。于是有μ>0。

λ*∈K*

ATy*+λ*=c

即(y*,λ*)是對偶可行的。另外由式(12)得到bTy*≥p*。結(jié)合定理1知，(y*,λ*)是對偶問題的最優(yōu)解且d*=p*。于是結(jié)論成立。

對于c=0的情形，證明是平凡的。

(2)假設(shè)對偶問題(D)上有界且嚴(yán)格可行。這里證明大部分類似于(1)，下面僅就不同的部分做簡要說明。定義集合：

V={c-ATy∈Rq|y∈Rm,bTy≥d*}

首先V≠? 和V∩int(K*)=?的證明完全類似(1)。

其次,由引理1，存在非零向量x∈Rq使得:

根據(jù)V的定義可得〈x，c-ATy〉≤0。于是對于半平面H={y∈Rm|bTy≥d*}的所有點y，有:

(Ax)Ty≥cTx

(13)

因為(Ax)Ty在半平面H內(nèi)有下界，所以Ax與b只能成比例，即存在μ≥0使得Ax=μb(注意這里也可以仿照上面利用線性不等式的選擇性定理)。

如果μ=0，那么由式(13)得到cTx≤0。另一方面， 由對偶問題(D)的嚴(yán)格可行性知存在y0∈Rm使得c-ATy0∈int(K*)。對充分接近y0的y∈Rm，也有c-ATy∈int(K*)。再由x∈K可以推得〈x,c-ATy〉>0，從而cTx>〈x,ATy〉=〈Ax,y〉=0。進(jìn)而得到矛盾不等式0≥cTx>0，因此有μ≠0，亦即μ>0。

x*∈K

Ax*=b

cTx*≤bTy

x*是原可行的且cTx≤d*。結(jié)合定理1知x*是原問題(CP)的最優(yōu)解且p*=d*。

綜上，定理2得證。

3 利用Fenchel對偶的證明

將錐對偶問題等價表示為Fenchel對偶形式，并以此為工具將凸優(yōu)化的強對偶定理應(yīng)用到錐上證明強錐對偶定理。

先考慮如下問題[15]:

(14)

和其Fenchel對偶問題[15]:

(15)

上述Fenchel對偶形式中，對偶函數(shù)仍然是采用Lagrange乘數(shù)法求得的，最終是利用共軛函數(shù)表示。

現(xiàn)在將一般線性錐優(yōu)化問題(1)和它的對偶問題(2)轉(zhuǎn)化為Fenchel對偶的形式，即:

(16)

和:

(17)

下面說明問題(16)、(17)與問題(1)、(2)等價的過程。

若x0∈Rq滿足Ax0=b，N(A)代表矩陣A的核空間，即：

N(A)={x∈Rq|Ax=0}

則問題(1)可以等價地改寫為問題(16):

定義函數(shù):

且假定E是q階單位矩陣。易知函數(shù)f1和f2是凸的，進(jìn)而求得:

因為c-λ∈R(AT)，所以存在y∈Rm使得c-λ=ATy。同時左乘x0的轉(zhuǎn)置后得到：

(c-λ)Tx0=(Ax0)Ty=bTy

從而問題(17)可以等價地寫成問題(2)。進(jìn)而獲得強錐對偶定理如下。

定理3如果問題(16)下有界，且存在x0∈int(K)滿足Ax0=b，那么Fenchel對偶問題(17)是可解的且對偶間隙為0。

證明令:

滿足引理4條件，于是相應(yīng)的結(jié)果成立。

4 結(jié)語

研究了一般的線性錐優(yōu)化問題強對偶定理的證明，用2種方法重新證明了強錐對偶定理：用線性不等式的選擇定理替代幾何直觀，克服了幾何直觀方法的特殊性；利用Fenchel對偶表示一般的線性錐優(yōu)化問題，再利用凸優(yōu)化的強對偶定理又一次證明強錐對偶定理。線性錐優(yōu)化的理論研究上已經(jīng)有了不少成果，但是半定規(guī)劃和二階錐優(yōu)化新的理論證明及算法研究上，還值得進(jìn)一步的探討。