第3章 對偶理論

第3章對偶理論§3.1線性規(guī)劃的對偶理論3.1.1對偶問題的表述對稱形式的對偶:(L)mincx(D)(L)mincx(D)maxwbs.t.Ax>bs.t.wA<c其中c為n維行向量，A為mXn矩陣，b為m維列向量，x表示n維列向量，w表示m維行向量。稱(D)為線性規(guī)劃(L)的對偶規(guī)劃問題。定理1(L)與(D)互為對偶規(guī)劃問題。(對合性)設(shè)原問題對偶問題s.t.定理1(L)與(D)互為對偶規(guī)劃問題。(對合性)設(shè)原問題對偶問題s.t.minx—xx+x>5x—2x>1x,x>0max5w+ws.t.w+w<1w—2w<—1w,w>0非對稱形式的對偶:(LP)mincx(DP)maxwbs.t.Ax=bs.t.s.t.Ax=bs.t.wA<cx>0設(shè)原問題對偶問題s.t.min5s.t.min5x+4x+3xx+x+x=43x+2x+x=5x,x,x>01 2 3max4w1+5w2s.t. w+3w<5w+2w<4w+w<3一般線性規(guī)劃問題:可化為上述二者之一討論其對偶問題，也可直接寫出對偶問題，詳細(xì)的對應(yīng)法則見教材(陳寶林)124頁。

直接寫出對偶的弊端之一是對偶最優(yōu)解不易確定，而對稱形式和非對稱形式對偶的最優(yōu)解都可由原問題的單純形乘子確定出來。3.1.2對偶定理(強(qiáng)對偶定理和弱對偶定理)定理2(弱對偶定理)：設(shè)x和刀分別是(L)mincx和(D)maxwbs.t.Ax>b s.t.wA<cx>0 w>0的可行解，則有下列不等式成立：cx>wb證明：由于Ax>b和w>0，則有wAx>wb。由于c>wA和x>0，則有cx>wAx。因此有cx>wb推論1設(shè)x和w分別是(L)和(D)的可行解，且有cx=wb，則x和w分別是(L)和(D)的最優(yōu)解。推論2如果(L)的目標(biāo)函數(shù)在可行集上無下界，則對偶規(guī)劃(D)無可行解。推論3如果(D)的目標(biāo)函數(shù)在可行集上無上界，則原始規(guī)劃(L)無可行解。定理3(強(qiáng)對偶定理)：如果互為對偶規(guī)劃的兩個問題之一有最優(yōu)解，則另一個問題也有最優(yōu)解，并且二者的目標(biāo)值相等。證明：設(shè)原問題(L)存在最優(yōu)解，引進(jìn)松弛變量，寫成等價形式:mincx(1)s.t.Ax-v=b(1)x>0v>0由于(1)存在最優(yōu)解，因此可以用單純形方法求出它的一個最優(yōu)基本可行解，不妨設(shè)-x該最優(yōu)解是y= ，相應(yīng)的最優(yōu)基是b。此時所有判別數(shù)均非正，即v(2)wp.一c<0,V;(2)w=cBB-1為單純形乘子?？紤]所有原來變量（不包括松弛變量）在基B下的判別數(shù)，把它們所滿足的條件（2）用矩陣形式寫出：wA-c<0或wA<c （3）把所有松弛變量在基B下的判別數(shù)所滿足的條件（2）用矩陣形式寫出：w（—I）<0 或w>0 （4）由（3）和（4）可知，w是對偶問題（D）的可行解。由于非基變量的取值為0，以及目標(biāo)函數(shù)中松弛變量的系數(shù)為0，因此有wb=cB-ib=cy=cx根據(jù)定理2的推論1，w是對偶問題（D）的最優(yōu)解，且原問題和對偶問題目標(biāo)函數(shù)最優(yōu)值相等。類似地可以證明，如果對偶問題存在最優(yōu)解，則原問題也存在最優(yōu)解，并且二者的目標(biāo)值相等。注：也可用凸集分離定理證明該結(jié)論。但運(yùn)用單純形法證明該定理屬于構(gòu)造性證明，也適用于求解對偶問題。3.1.3互補(bǔ)松弛定理利用對偶定理可以證明原問題和對偶問題的最優(yōu)解滿足重要的互補(bǔ)松弛性質(zhì)。對于互為對偶的一對線性規(guī)劃問題，已知一個問題的最優(yōu)解時，可以利用互補(bǔ)松弛定理求出另一個問題的最優(yōu)解。定理4（對稱形式的互補(bǔ)松弛定理）：設(shè)X和w分別是（L）和（。）的可行解，則二者分別為最優(yōu)解的充分必要條件是：w（Ax一b）=0, （wA一c）X=0用A.表示矩陣A的第i行，用Pj表示矩陣A的第j列。推論1設(shè)X和而分別是（L）和（D）的可行解，則二者分別為最優(yōu)解的充分必要條件是：（i） 對j=1,…,n，若X.〉0，就有wp=c；若wp<c.,就有X.=0。（ii） 對i=1,…,m，若嗎>0，就有A.X=%；若A.X>%，就有嗎=0。推論2設(shè)X是（L）的最優(yōu)解，則w是（D）的最優(yōu)解的充要條件是：（i）對j=L，,,,n，若X.>0，就有wp.=c.；

(ii)對i=1,…,m，若Ax>b，就有w=0。推論3設(shè)巧是(D)的最優(yōu)解，則x是(L)的最優(yōu)解的充要條件是:(i)對j=1,…，n(i)對j=1,…，n，若叫<匕，就有七=0；(ii)對i=1,…,m例:若嗎>0，就有A’x=b。設(shè)原問題s.t.min2x+3x+x3x—x+x>1x+2x—3x>2x,x,x>01 2 3對偶問題maxw+2ws.t.3w+w<2—w+2w<3w—3w<1w,w>0設(shè)用圖解法求得對偶問題的最優(yōu)解為, 、，111、w=(w,w)=(7,—)則可用互補(bǔ)松弛定理求原問題的最優(yōu)解。由于在最優(yōu)解w處，對偶問題的第3個約束成立嚴(yán)格不等式，因此原問題第3個變量x=00又由于w的兩個分量均大于0，因此在原問題中前兩個約束在最優(yōu)解處成立等式，即3x—x+x=1x+2x-3x=2把x=0代入上述方程組，可解得x=§，x=|"03 17 27原問題的最優(yōu)解為x=(x,x,x)=(~,了,0)丁0123 77§3.2非線性規(guī)劃的對偶理論3.2.1非線性規(guī)劃的Lagrange對偶問題的表述非線性規(guī)劃的對偶理論不像線性規(guī)劃的對偶理論簡單漂亮?？梢酝ㄟ^多種不同的方式來構(gòu)造非線性規(guī)劃對偶問題，如基于Lagrange函數(shù)，凸函數(shù)的共軛函數(shù)及K-T最優(yōu)性條件等。

不同構(gòu)造方式基于的條件不同，所得結(jié)論亦有區(qū)別，從而應(yīng)用場合不同。此節(jié)以Lagrange對偶為例，介紹非線性規(guī)劃的對偶理論。原I可題：min/(x)s.t.g(x)>0,i=h(x)=0,j=，???,IjxeD.。為的子集，它的選擇影響到計算和修正對偶目標(biāo)函數(shù)的計算量。令對偶目標(biāo)函數(shù)（Lagrange對偶函數(shù)）為:9(w,v)=inf</(x)-Xwg(x)—2LZ=1對偶問題:max0(w,v)s.t.w>0(5)(6)例：求下列問題的Lagrange對偶問題。(5)(6)minx2+x2TOC\o"1-5"\h\z1 2s.t.x+x-4>0,1 2x>0,x>0.1 2xeD=xxeD=x>0,x>01 2：2：2+X2-w(x+x-4)IX,X>01 2 (1J2 1 2對偶函數(shù):9(w)=inf=inf%2-wx\x>0^+inf^2-wxI%>0^+4w

1 1 1 2 2 2由上式可知，當(dāng)時，有10(w)=-—w2+4w2當(dāng)w<°時，由于氣，頃,則有X2一WX>0X2-WX>0因此當(dāng)X1=X2=0時，得到極小值0(w)=4w綜上分析，得到對偶函數(shù)：r1 ―3\ 一一W2+4w,W>00(w)=j24w, w<0本例的對偶問題為1max0(w)=-—w2+4w2s.t.w>0問題的最優(yōu)解和最優(yōu)值為：x=(2,2)t,/m.n=8對偶問題的最優(yōu)解和最優(yōu)值為：w=4,0max=8問題:原問題與對偶問題解之間的關(guān)系？線性規(guī)劃的弱對偶定理是否成立？線性規(guī)劃的強(qiáng)對偶定理是否成立？原問題：minf(x)s.t.g(x)>0,h(x)=0,xeD.其中g(shù)(x)=(gjx),…,gm(x))T,h(x)=(hjx),...,%(x))T令w=(w,...,w)T,v=(v,...,v)T對偶問題：max0(w,v)s.t.w>0其中，0(w,v)=inff(x)—wTg(x)—vTh(x)IxeD原問題的可行集：S={eRnIg(x)>0,h(x)=0,xeD對偶問題的可行集：SD={w,v)eRm+i|w>。}

3.2.2對偶定理定理5(弱對偶定理)：原問題(inf)在可行集上的目標(biāo)值不小于對偶問題(sup)在可行集上的目標(biāo)值，即f(x)>0(w,v),VxgS,V(w,v)gSD推論1inff(x)IxgS}>sup^0(w,v)I(w,v)gSd}推論2如果存在xgS,(w,v)gSD使得f(x)<0(w,v)則x和(w,v)分別是原問題和對偶問題的最優(yōu)解。推論3如果inff(x)IxgS}=一8,則有0(w,v)=一8,V(w,v)gSD推論4如果sup*0(w,v)I(w,v)gSd}=8,則原問題不可行。對偶間隙：由推論1矢口ff>^sup，若fnf=9sup，則原問題與對偶問題無對偶間隙;若ff>3sup，則原問題與對偶問題有對偶間隙。下面的強(qiáng)對偶定理表明：對凸規(guī)劃，在適當(dāng)?shù)募s束規(guī)格下，原問題與對偶問題不會出現(xiàn)對偶間隙。定理6(強(qiáng)對偶定理)：設(shè)在(5)中下列條件滿足：⑴DuB非空凸，f(x),-gj(x),i=1,…,m是凸函數(shù)；七(x),j=1,…,l是線性函數(shù)。則有下列結(jié)論成立：inf{f(x)IxgS若inf{f(x)IxgS}有限，(ii)3xgDs.t.g(￡)>0,h則有下列結(jié)論成立：inf{f(x)IxgS若inf{f(x)IxgS}有限，}=sup*?(w,v)I(w,v)gSDJ;貝0存在(w,v)gSD,s.t.(iii)若inf{f(x)IxgS}有限，xgS,s.t.f(x)=inff(x(iii)若inf{f(x)IxgS}有限，xgS,s.t.f(x)=inff(x)Ixg且存在S}，則有wg(x)=0。定理的解釋：條件(i)要求原問題(5)為凸規(guī)劃，條件(ii)要求原問題(5)滿足約束規(guī)范;結(jié)論(i)說明原問題(5)和對偶問題(6)無對偶間隙；結(jié)論（ii）說明原問題的目標(biāo)函數(shù)f3）在可行集上有下界時，其對偶問題有有限最優(yōu)解，即上確界可以取到；結(jié)論（iii）說明若原問題有有限最優(yōu)解時，則原問題和對偶問題在該最優(yōu)解和對偶問題最優(yōu)解滿足互補(bǔ)松弛條件。習(xí)題1給定下列線性規(guī)劃問題max10x+7x+3