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

1、最优化方法最优化方法 OptimizationOptimization第七讲第七讲第四章第四章 对偶实际对偶实际 窗含西岭千秋雪，门泊东吴万里船。 -(唐)杜甫 对偶是一种普遍景象主要内容主要内容 对偶问题的方式对偶问题的方式普遍存在普遍存在 L P 对偶方式及定理对偶方式及定理 对偶问题经济解释对偶问题经济解释 对偶单纯形法对偶单纯形法 原原-对偶算法对偶算法对偶及鞍点问题对偶及鞍点问题Lagrange 对偶问题对偶问题Dxljxhmixgtsxfji, 1, 0)(, 1, 0)(. .)(min(1)定义定义(1)的对偶问题的对偶问题:0. .),(maxwtsvw(2)集约束集约束Dx

2、xhvxgwxfvwljjjmiii11)()()(inf),(其中0. .),(maxwtsvw11( , ):( )( )( )mliijjijL x w vf xw g xv h xLagrange函数函数( , , ),( , )xDLagrangrL x w vw vw v对于任意的，函数是的线性函数，于是对偶函数作为线性函数的逐点下确界，必然是一个凹函数，所以，对偶问题是一个凸规划问题。例：思索线性规划问题例：思索线性规划问题1122min. .0cxstAxbA xbx假设取集合约束假设取集合约束D=x|x0，那么该，那么该线性规划问题的线性规划问题的Lagrange函数为函数为

3、11221212121212( , )inf()()|inf()|00.TTTTTTTTTTTTw vcxwAxbvA xbxDcw Av A xw bv bxDw bv bcw Av Acw Av A若若线性规划的对偶问题为：线性规划的对偶问题为：1212max. .0TTTTw bv bstw Av Acw0,04. .min21212221xxxxtsxx求以下非线性规划问题的对偶问题求以下非线性规划问题的对偶问题:11222212120,0 ,( )inf(4)|.xxDxxxwxxw xxxD解：把变量的非负限制作为集约束，即则.42444)(.4220|inf.4220|inf,0

4、40|inf0|inf0, 0|4inf| )4(inf)(2222222222211212222112121222121212221wwwwwwwwwwxwxxwwwwxwxxwwxwxxxwxxxxwwxxwxxDxxxwxxw时当对偶问题为对偶问题为:0. .42max2wtsww对偶定理对偶定理TlTmxhxhxhxgxgxgDxxhxgtsxf)(,),()()(,),()(0)(0)(. .)(min110. .),(maxwtsvw( , )inf( )( )( )|TTw vf xw g xv h xxD定理定理1(弱对偶定理弱对偶定理)。题的可行解，则分别是原问题和对偶问和设

5、),()(),(vwxfvwx).()()()(| )()()(inf),(0, 0)(, 0)(),(xfxhvxgwxfDxxhvxgwxfvwwxhxgvwxTTTT是可行解，和证明： 推论推论1:.0| ),(sup, 0)(, 0)(| )(infwvwDxxhxgxf，必有对于原问题和对偶问题推论推论2:题的最优解。分别是原问题和对偶问和，则为原问题的可行解，其中若),(0),()(vwxwxvwxf推论推论3:。，有则对若),(0, 0)(, 0)(| )(infvwwDxxhxgxf推论推论4:sup( , )|0w vw 如果，则原问题没有可行解。对偶间隙：对偶间隙：minm

6、axinf( )| ( )0, ( )0,=sup( , )|0f xg xh xxDfw vw记记minmax0f问题：问题：0. 成立的条件LP 对偶问题的表达对偶问题的表达1 1对称对称LPLP问题的定义问题的定义m in. .0Tcxs tA xbx2对称对称LP问题的对偶问问题的对偶问题题(P)(D)max. .0TTb ws tA wcw例：写出以下例：写出以下LPLP问题的对偶问题问题的对偶问题12121212max2328416. . 412,0wwwwws twww1231213123min8161242. 243,0 xxxxxstxxx x x对偶例：写出对偶问题例：写出

7、对偶问题(D)(D)的对偶的对偶变形(D)min. .0TTb ws tA wcw max. .0TTb ws tA wcw对偶max. .()0TTTc xs tAxbx m in. .0Tc xs tAxbx变形结论：对偶问题结论：对偶问题(D)的对偶的对偶 为原问题为原问题(P) 。(DD)minmin变成变成max max 价值系数与右端向量互换价值系数与右端向量互换系数矩阵转置系数矩阵转置 变变 原问题中约束条件的个数原问题中约束条件的个数= =对偶问题中变量的个数对偶问题中变量的个数原问题中变量的个数原问题中变量的个数= =对偶问题中约束条件的个数对偶问题中约束条件的个数写出对称方

8、式的对偶规划的要点写出对称方式的对偶规划的要点非对称方式的对偶非对称方式的对偶min. .0Tc xs tAxbx对称方式对称方式m in. . 0Tcxs tA xbA xbx 对偶对偶max.,0TTTTb u b vstA uA vcu vmax. .TTb ws tA wcw无 限 制wuv令(P)(D)例例 min 5x1+4x2+3x3 s.t. x1+x2+x3=4 3x1+2x2+x3 =5 x1 0, x2 0, x3 0 对偶问题为对偶问题为 max 4w1+5w2 s.t. w1+3w25 w1+2w2 4 w1+w2 3112233min.0where ,1,2,3.i

9、iTmm nniic xstAx bAx bAx bxc R bRARi31112233min. . ,0where , are slack variables.Tststmmstc xstA xxbA xbA xxbx x xxRxR普通情形普通情形LPLP问题的对偶问题问题的对偶问题规范形规范形对偶对偶112233112233123max . . , 0, free, 0. TTTTTTb wb wb wstA wA wA wcwww变量变量约束约束约束约束变量变量123123123123123min 22 2 1 2. . 1 0, 0 xxxxxxxxxs txxxxxx无约束123m

10、ax2www. st123www123www1232www21210w 20w 3w 无约束123123123123123max2 2 1:2 20,0,xxxxxxxxxSTxxxxxx无约束123min 22www123www1232www123www1210w 2w 无约束30w 1. st123123123123132min 22212. . 10,0,xxxxxxxxxstxxxxxx无约束练习题练习题LP对偶问题的根本性质对偶问题的根本性质原问题原问题(P)对偶问题对偶问题(D)m in. .0Tcxs tA xbxm a x. . 0TTbws tAwcw定理定理1(1(弱对偶定

11、理弱对偶定理) )(0)(0)(0)(0),( ),( ).TTxwPDc xb w若分别为的可行解，则(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(),0.(),0,().TTTTPAbDcAb证明：因x是的可行解，故xx因w是的可行解，故A ww从而c xxww例：123412341234max 234 . 22320 ( 1)23220 0,1,2,3,4 jwwwwstwwwwwwwwwjD1212min2020. 21xxstxx1222xx121212233324,0 xxxxx x1原问题原问题(P1)一可行解一可行解 x=(1, 1)T(P1)目的值目的值 =4

12、040是是(D1)最优目的值的上界最优目的值的上界.2对偶问题对偶问题(D1)一可行解一可行解 w=1 1 1 1 目的值目的值 =10 10是是(P1)最优目的值的下界最优目的值的下界. *61 28550 0 4 4 28Txw最优值最优值推论推论1推论推论2 2极大化问题的任何一个可行解所对应的目的极大化问题的任何一个可行解所对应的目的函数值都是其对偶问题的目的函数值的下界。函数值都是其对偶问题的目的函数值的下界。极小化问题的任何一个可行解所对应的目的极小化问题的任何一个可行解所对应的目的函数值都是其对偶问题的目的函数值的上界。函数值都是其对偶问题的目的函数值的上界。推论推论3 3假设问

13、题假设问题(P)(P)或或(D)(D)有无界解，那么其对偶问题有无界解，那么其对偶问题(D)(D)或或(P)(P)无可行解；无可行解； 假设问题假设问题(P)(P)或或(D)(D)无可行解，那么其对偶问题无可行解，那么其对偶问题(D)(D)或或(P)(P)或者无可行解或者无可行解, ,或者目的函数值趋于无穷。或者目的函数值趋于无穷。定理定理2(2(最优性准那最优性准那么么) )(0 )(0 )(0 )(0 )00,(), ()(P) (D)xwPDcxwbxw（ ）（ ）若分 别 为的 可 行 解 且，则，分 别 为,问 题 的 最 优 解 .(0)(0)(0)(0),1,(),TTTTxc

14、xbPwc xb wx对原问题(P)的任意可行解由定理 可则为的知而最优解.证明：证明：(0),()wD同理为的最优解1234123412341234max 23422320. . 23220,0Zxxxxxxxxs txxxxx xxx121212121212min 20202122. . 233324,0Wyyyyyys tyyyyyy( )P()D例例(0)(0)(0)(0)(0,0,4,4) ,6 1,(),()5 528TTTTxyPDc xb y由于是的可行解且(0)(0),( ),( )xyPD所以，分别是的最优解定理定理3(3(强对偶定理强对偶定理) )假设假设(P),(D)(

15、P),(D)均有可行解均有可行解, ,那么那么(P),(D)(P),(D)均有最优解均有最优解, ,且且(P),(D)(P),(D)的的最优目的函数值相等最优目的函数值相等. .证明：由于证明：由于(P),(D)(P),(D)均有可行解均有可行解, ,由推论由推论2,2,推论推论3 3知知,(P),(P)的目的的目的函数值在其可行域内有下界函数值在其可行域内有下界, (D), (D)的目的函数值在其可行域内的目的函数值在其可行域内有上界有上界, , 故那么故那么(P),(D)(P),(D)均有最优解均有最优解. .引入剩余变量，把引入剩余变量，把(P)(P)化为规范形化为规范形: :m in

16、(, 0 ). .(,)0 ,0Tsssxcxxs tAIbxxx(0)().PxB设的最优解为，所对应的最优基为(0)1(0)(0)(0)0BNxBbxxx可以表示为1(,)()( ,0)0TTBAIBcc则(0)1),(TBwBc令由上式得(0)(0)(0),0,()TA wc wwD故是的可行解.(0)(0)(01)()BTTTTTBBb wbcc xcBx又因为(0 )(0 )(0 )()m inm ax.TTTTwDcxcxb wb w故是的 最 优 解 ， 且推论推论在用单纯形法求解在用单纯形法求解LPLP问题问题P P的最优单纯的最优单纯形表中松弛变量的检验数的相反数形表中松弛变

17、量的检验数的相反数( (单纯形单纯形乘子乘子w=(B-1)TcB)w=(B-1)TcB)就是其对偶问题就是其对偶问题D D的最优的最优解解. .由于由于(P)(P)化成规范方式时化成规范方式时, ,松弛变量松弛变量xn+j xn+j 对应的列为对应的列为-ej-ej，它在目的函数中的价钱系数，它在目的函数中的价钱系数，所以，判别数为所以，判别数为 (B-1)TcB(-ej)-0=-wj (B-1)TcB(-ej)-0=-wj那么松弛变量对应的判别数均乘以那么松弛变量对应的判别数均乘以(-1)(-1)，便得到单，便得到单纯形乘子纯形乘子w=(w1,wm).w=(w1,wm). 当原问题达最优时当

18、原问题达最优时, ,单纯形乘子即为对偶问题的单纯形乘子即为对偶问题的最优解最优解. .解：化为规范形121231425max 23284164120,1,2,3,4,5jxxxxxxxxxxj例例: : 求以下问题之对偶问题的最优解求以下问题之对偶问题的最优解12121212max2328416. .412,0 xxxxxs txx xx1 x2 x3 x4 x5 1 2 1 0 04 0 0 1 00 4 0 0 1-2 -3 0 0 0 x3x4x58161201 0 1 0 -1/24 0 0 1 00 1 0 0 1/4-2 0 0 0 3/4x3x4x22163941x1 x2 x3

19、 x4 x5 1 0 1 0 -1/20 0 -4 1 20 1 0 0 1/40 0 2 0 -1/4x1x4x22831321 0 0 1/4 00 0 -2 1/2 10 1 1/2 -1/8 00 0 3/2 1/8 0 x1x5x244214此时到达最优解。此时到达最优解。x x* *=(4,2), MaxZ=14=(4,2), MaxZ=14。12121212max2328416. .412,0 xxxxxs txxx1231213123min81612. .42243,0wwws twwwww ww(P)(D)31, 0 ,14.28w(D)最优解为：最优值小结小结原问题原问题(

20、min) 对应关系对应关系 对偶问题对偶问题(max) 有最优解有最优解无界解不可行不可行无界解1212112212 max . . 1 (D) -1 ,0ywwstwwlwwlw w 无可行解无可行解1212112212min . . 1 (P) -1 ,0zxxstxxlxxlx x 例1:无可行解无可行解w1w2l2l1x1x2l1l21212112212 max . . 1 (P) 1 ,02zxxstxxlxxlx x例 ： 无界解1212112212 min . . 1 (D) 1 ,0wyystyylyyly y 无可行解无可行解l2x1x2l1zy1y2l1l2定理定理4 4互

21、补松驰定理互补松驰定理0000 xwPDxwPD（ ）（ ）（ ）（ ）设，分别为（ ），（）问题的可行解则，分别为（ ），（）的最优解的充要条件是(0)(0)0,jjjxwPc若则(1)(2)(0)(0),0jjjwPcx若则(3)()(0)0,iiiwAxb若则(4)(0)(0),0iiiAxbw若则, (1,1),i jimjn 有.jiPAjAAi其中 是 的第 列， 是 的第 行(0)(0)()0cwA x(0)(0)()0wAxb11( )*,*,* 0;(1)0,0,0;(2)(*) 0,*ker()0.(3)mnTTTTLxwrAxbxcA w rwrw AKarush Kuh

22、n TucKKTxbr x （）对于线性规划来说， 是其最优解，当且仅当存在向最优性条件定理量条件，使得证明：必要性证明：必要性(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)( )()0,0,()0,() 0.xwPDAxbxwA cwwAxwbwAxcxcxwAxwbxwcxwb cxwAxwbc wA xwAxb 设和分别是和的最优解，则且故有即因为是最有解 所以有所以，即，且 证明：充分性证明：充分性(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(

23、0)(0)(0)()0,() 02,( )().c wA xcxwAxwAxbwAxwbcxwbxwPD 由得由， 得因此有由定理 知，为和的最优解定理定理4 4：互补松驰定理：互补松驰定理( (非对称方式非对称方式(0)(0)TT(0)(0)(0)(0)(0)(0)minmax. . .0(1)0,(2)0.Tjjjjjjxwc xb wstAxbstA wcxxwjxwPcwPcx设和分别是和的可行解，则和是最优解的充要条件时，对任意的 ，下列关系成立：若则；若，则12341234123412342342232 0. .2322 0,0M a xZxxxxxxxxs txxxxxxxx12

24、121212121220202122. .233324,0M inWyyyyyys tyyyyyy( )P()D例例: : 思索下面问题思索下面问题*6 1(),5 5( )DyP已知的最优解为用互补松弛定理求出的最优解解解:*120 ,0yy由 于4由 定 理知*123422320(1)xxxx*12342322 0(2 )xxxx*11yy*12yy*342320 xx*343220 xx*344xx则( )P所以问题的最优解为*(0, 0, 4, 4)x*1201xx ，代入（），（2）12121212121220202122: 233324,

25、0MinWyyyyyySTyyyyyy1 1、定义、定义对偶问题的经济学解释：影子价钱对偶问题的经济学解释：影子价钱(自学自学)影 子 价 格 是 最 优 配 置 下 资 源 的 理 想 价 格*1122mmfcxw bw bw bw b由 于12,mb bb假设是变化的，则2 2、含义、含义*1212,mmfffwwwbbb*1( )iiwbP可以理解成当资源 变化 单位时，极小化问题的目标函数值的变化量思索在最优解处思索在最优解处,右端项右端项bi的微小变动对目的函数值的影响的微小变动对目的函数值的影响. 假设把原问题的约束条件看成是广义的资源约束假设把原问题的约束条件看成是广义的资源约束

26、, ,那么那么右端项的值表示每种资源的可用量右端项的值表示每种资源的可用量. . 对偶解的经济含义对偶解的经济含义: :资源的单位改动量引起目的函数值资源的单位改动量引起目的函数值的添加量的添加量. . 通常称对偶解为影子价钱通常称对偶解为影子价钱. . 影子价钱的大小客观地反映了资源在系统内的稀缺程度影子价钱的大小客观地反映了资源在系统内的稀缺程度. .资源的影子价钱越高资源的影子价钱越高, ,阐明资源在系统内越稀缺阐明资源在系统内越稀缺, ,而添加而添加该资源的供应量对系统目的函数值奉献越大该资源的供应量对系统目的函数值奉献越大. . 木门 木窗木工 4小时 3小时 120小时/日油漆工

27、2小时 1小时 50小时/日收入 56 30解：设该车间每日安排 x1 x2 x3 x4消费木门x1扇，木窗x2 x3 4 3 1 0 120max z=56 x1 +30 x2 x4 2 1 0 1 50 s.t. 4 x1 +3 x2120 -56 -30 0 0 0 2 x1 + x2 50 x3 0 1 1 -2 20 x1 x2 0 x1 1 1/2 0 1/2 25 0 -2 0 28 1400 x2 0 1 1 -2 20 x1 0 0 -1/2 -1/2 15 0 0 2 24 1440对偶问题的解为对偶问题的解为:w*=(2, 24) 2通知管理者花多大代价购买进资源或卖出资

28、源是适宜的 3 3、影子价钱的作用、影子价钱的作用1 1通知管理者添加何种资源对企业更有利通知管理者添加何种资源对企业更有利 3为新产品定价提供根据为新产品定价提供根据对偶单纯形法对偶单纯形法 定义：设定义：设x(0)是是(P)的一个根本解不一定是可行的一个根本解不一定是可行解，它对应的矩阵为解，它对应的矩阵为B，记，记w=cBB-1，假设，假设w是是(P)的对偶问题的可行解，即对恣意的的对偶问题的可行解，即对恣意的j, wPj-cj 0，那么称，那么称x(0)为原问题的对偶可行的基解。为原问题的对偶可行的基解。 结论：当对偶可行的基解是原问题的可行解时，结论：当对偶可行的基解是原问题的可行解

29、时，由于判别数由于判别数0，因此，它就是原问题的最优解。，因此，它就是原问题的最优解。1231234123512345min. .3142,0 xxxs txxxxxxxxxxxxx1212121212m ax2. .3141111wws twwwwwwww 000012Tx1111000Bc BAc 所以，所以，x(0)为对偶可行的基解。为对偶可行的基解。根本思想：根本思想：从原问题的一个对偶可行的基解出发；从原问题的一个对偶可行的基解出发；求改良的对偶可行的基解：每个对偶可求改良的对偶可行的基解：每个对偶可行的基解行的基解x=(xBT,0)T对应一个对偶问对应一个对偶问题的可行解题的可行解

30、w=cBB-1，相应的对偶问，相应的对偶问题的目的函数值为题的目的函数值为wb=cBB-1b，所谓，所谓改良的对偶可行的基解，是指对于原改良的对偶可行的基解，是指对于原问题的这个基解，相应的对偶问题的问题的这个基解，相应的对偶问题的目的函数值目的函数值wb有改良选择离基变量有改良选择离基变量和进基变量，进展主元消去；和进基变量，进展主元消去；当得到的对偶可行的基解是原问题的可当得到的对偶可行的基解是原问题的可行解时，就到达最优解。行解时，就到达最优解。与原单纯形法的区别：原单纯形法坚持原问题的可行性，对偶单纯形法坚持一切检验数wPj-cj 0，即坚持对偶问题的可行性。特点：先选择出基变量，再选择进基变 量。120B b、判断，若，则已得到最优解3、换基迭代、换基迭代 1min0,riribbx）确定换出变量，为换出变量.1、 化规范型化规范型,建立初始单纯形表建立初始单纯形表2min0,jjkkrjkjrjrkzczcyxyy）确定换入变量，为换入变量.3rky）换基迭代，为主元.4、回到第、回到第2