最优化方法之 对偶理论讲解

最优化方法Optimization第七讲第四章对偶理论窗含西岭千秋雪，门泊东吴万里船。-----(唐)杜甫对偶是一种普遍现象主要内容•对偶问题的形式—普遍存在•LP对偶形式及定理•对偶问题经济解释•对偶单纯形法•原-对偶算法对偶及鞍点问题Lagrange对偶问题Dxljxhmixgtsxfji,,1,0)(,,1,0)(..)(min(1)定义(1)的对偶问题:0..),(maxwtsvw(2)集约束Dxxhvxgwxfvwljjjmiii11)()()(inf),(其中0..),(maxwtsvw11(,,):()()()mliijjijLxwvfxwgxvhxLagrange函数(,,),(,)xDLagrangrLxwvwvwv对于任意的，函数是的线性函数，于是对偶函数作为线性函数的逐点下确界，必然是一个凹函数，所以，对偶问题是一个凸规划问题。例：考虑线性规划问题1122min..0cxstAxbAxbx若取集合约束D={x|x≥0}，则该线性规划问题的Lagrange函数为11221212121212(,)inf()()|inf{()|}00.TTTTTTTTTTTTwvcxwAxbvAxbxDcwAvAxwbvbxDwbvbcwAvAcwAvA若若线性规划的对偶问题为：1212max..0TTTTwbvbstwAvAcw0,04..min21212221xxxxtsxx求下列非线性规划问题的对偶问题:11222212120,0,()inf(4)|.xxDxxxwxxwxxxD解：把变量的非负限制作为集约束，即则.42444)(.4220|inf.4220|inf,040|inf0|inf0,0|4inf|)4(inf)(2222222222211212222112121222121212221时当对偶问题为:0..42max2wtsww对偶定理TlTmxhxhxhxgxgxgDxxhxgtsxf)(,),()()(,),()(0)(0)(..)(min110..),(maxwtsvw(,)inf()()()|TTwvfxwgxvhxxD定理1(弱对偶定理)。题的可行解，则分别是原问题和对偶问和设),()(),(vwxfvwx).()()()(|)()()(inf),(0,0)(,0)(),(xfxhvxgwxfDxxhvxgwxfvwwxhxgvwxTTTT是可行解，和证明：推论1:.0|),(sup,0)(,0)(|)(infwvwDxxhxgxf，必有对于原问题和对偶问题推论2:题的最优解。分别是原问题和对偶问和，则为原问题的可行解，，其中若),(0),()(vwxwxvwxf推论3:。，有则对若),(0,,0)(,0)(|)(infvwwDxxhxgxf推论4:sup(,)|0wvw如果，则原问题没有可行解。对偶间隙：minmaxinf()|()0,()0,=sup(,)|0fxgxhxxDfwvw记记minmax0f问题：0.成立的条件LP对偶问题的表达（1）对称LP问题的定义min..0TcxstAxbx（2）对称LP问题的对偶问题(P)(D)max..0TTbwstAwcw例：写出下列LP问题的对偶问题12121212max2328416..412,01231213123min8161242..243,,0xxxxxstxxxxx对偶例：写出对偶问题(D)的对偶变形(D)min..0TTbwstAwcwmax..0TTbwstAwcw对偶max..()0TTTcxstAxbxmin..0TcxstAxbx变形结论：对偶问题(D)的对偶为原问题(P)。(DD)①min变成max②价值系数与右端向量互换③系数矩阵转置④≥变≤•原问题中约束条件的个数=对偶问题中变量的个数•原问题中变量的个数=对偶问题中约束条件的个数写出对称形式的对偶规划的要点非对称形式的对偶min..0TcxstAxbx对称形式min..0TcxstAxbAxbx对偶max..,0TTTTbubvstAuAvcuvmax..TTbwstAwcw无限制wuv令(P)(D)例min5x1+4x2+3x3s.t.x1+x2+x3=43x1+2x2+x3=5x1≥0,x2≥0,x3≥0对偶问题为max4w1+5w2s.t.w1+3w2≤5w1+2w2≤4w1+w2≤3112233min..0where,,,1,2,3.iiTmmnniicxstAxbAxbAxbxcRbRARi31112233min..,,0where,areslackvariables.TststmmstcxstAxxbAxbAxxbxxxxRxR一般情形LP问题的对偶问题标准形对偶112233112233123max..,0,free,0.TTTTTTbwbwbwstAwAwAwc变量约束约束变量123123123123123min22212..10,,0xxxxxxxxxstxxxxxx无约束123max2..st123123123221210w20w3w无约束123123123123123max221:220,0,xxxxxxxxxSTxxxxxx无约束123min2212312321231210w2w无约束30w1..st123123123123132min22212..10,0,xxxxxxxxxstxxxxxx无约束练习题LP对偶问题的基本性质原问题(P)对偶问题(D)min..0TcxstAxbxmax..0TTbwstAwcw定理1(弱对偶定理)(0)(0)(0)(0),(),().TTxwPDcxbw若分别为的可行解，则(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(),0.(),0,().TTTTPAbDcAb证明：因x是的可行解，故xx因w是的可行解，故Aww从而cxxww例：123412341234max234.22320(1)232200,1,2,3,4j1212min2020.21xxstxx1222xx121212233324,0xxxxxx1）原问题(P1)一可行解x=(1,1)T(P1)目标值=4040是(D1)最优目标值的上界.2）对偶问题(D1)一可行解w=（1111）目标值=1010是(P1)最优目标值的下界.**612855004428Txw最优值最优值推论1推论2极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。推论3若问题(P)或(D)有无界解，则其对偶问题(D)或(P)无可行解；若问题(P)或(D)无可行解，则其对偶问题(D)或(P)或者无可行解,或者目标函数值趋于无穷。定理2(最优性准则)(0)(0)(0)(0)00,(),()(P)(D)xwPDcxwbxw（）（）若分别为的可行解且，则，分别为,问题的最优解.(0)(0)(0)(0),1,,(),TTTTxcxbPwcxbwx对原问题(P)的任意可行解由定理可则为的知而最优解.证明：(0),()wD同理为的最优解1234123412341234max23422320..23220,,,0Zxxxxxxxxstxxxxxxxx121212121212min20202122..233324,0Wyyyyyystyyyyyy()P()D例(0)(0)(0)(0)(0,0,4,4),61,(),()5528TTTTxyPDcxby由于是的可行解且(0)(0),(),()xyPD所以，分别是的最优解定理3(强对偶定理)若(P),(D)均有可行解,则(P),(D)均有最优解,且(P),(D)的最优目标函数值相等.证明：因为(P),(D)均有可行解,由推论2,推论3知,(P)的目标函数值在其可行域内有下界,(D)的目标函数值在其可行域内有上界,故则(P),(D)均有最优解.引入剩余变量，把(P)化为标准形:min(,0)..(,)0,0TsssxcxxstAIbxxx(0)().PxB设的最优解为，所对应的最优基为(0)1(0)(0)(0)0BNxBbxxx可以表示为1(,)()(,0)0TTBAIBcc则(0)1),(TBwBc令由上式得(0)(0)(0),0,()TAwcwwD故是的可行解.(0)(0)(01)()BTTTTTBBbwbccxcBx又因为(0)(0)(0)()minmax.TTTTwDcxcxbwbw故是的最优解，且推论在用单纯形法求解LP问题（P）的最优单纯形表中松弛变量的检验数的相反数(单纯形乘子w=(B-1)TcB)就是其对偶问题（D）的最优解.由于(P)化成标准形式时,松弛变量xn+j对应的列为-ej，它在目标函数中的价格系数＝０，所以，判别数为(B-1)TcB(-ej)-0=-wj则松弛变量对应的判别数均乘以(-1)，便得到单纯形乘子w=(w1,…,wm).当原问题达最优时,单纯形乘子即为对偶问题的最优解.解：化为标准形121231425max23284164120,1,2,3,4,5jxxxxxxxxxxj例:求下列问题之对偶问题的最优解12121212max2328416..412,0xxxxxstxxxx1x2x3x4x5121004001004001-2-3000x3x4x58161201010-1/24001001001/4-20003/4x3x4x22163941x1x2x3x4x51010-1/200-41201001/40020-1/4x1x4x22831321001/4000-21/21011/2-1/80003/21/80x1x5x244214此时达到最优解。x*=(4,2),MaxZ=14。12121212max2328416..412,0xxxxxstxxx1231213123min81612..42243,,0(P)(D)31,,0,14.28w(D)最优解为：最优值小结原问题(min)对应关系对偶问题(max)有最优解有最优解无界解不可行不可行无界解1212112212max..1(D)-1,0ywwstwwlwwlww（无可行解）12121