第3章对偶理论

37第3章对偶理论§3.1线性规划的对偶理论3.1.1对偶问题的表述对称形式的对偶：（L）cxmin(D)wbmaxs.t.bAxs.t.cwA0x0w其中c为n维行向量，A为nm矩阵，b为m维列向量，x表示n维列向量，w表示m维行向量。称(D)为线性规划(L)的对偶规划问题。定理1(L)与(D)互为对偶规划问题。――（对合性）例设原问题对偶问题0,125s.t.min21212121xxxxxxxx0,121s.t.5max21212121非对称形式的对偶：（LP）cxmin(DP)wbmaxs.t.bAxs.t.cwA0x例设原问题对偶问题0,,5234s.t.345min321321321321xxxxxxxxxxxx34253s.t.54max21212121一般线性规划问题：可化为上述二者之一讨论其对偶问题，也可直接写出对偶问题，详细的对应法则见教材（陈宝林）124页。38直接写出对偶的弊端之一是对偶最优解不易确定，而对称形式和非对称形式对偶的最优解都可由原问题的单纯形乘子确定出来。3.1.2对偶定理(强对偶定理和弱对偶定理)定理2(弱对偶定理)：设x和w分别是（L）cxmin和(D)wbmaxs.t.bAxs.t.cwA0x0w的可行解，则有下列不等式成立：bwxc证明：由于bxA和0w，则有bwxAw。由于Awc和0x，则有xAwxc。因此有bwxc推论1设x和w分别是(L)和(D)的可行解，且有bwxc，则x和w分别是(L)和(D)的最优解。推论2如果(L)的目标函数在可行集上无下界，则对偶规划(D)无可行解。推论3如果(D)的目标函数在可行集上无上界，则原始规划(L)无可行解。定理3(强对偶定理)：如果互为对偶规划的两个问题之一有最优解，则另一个问题也有最优解，并且二者的目标值相等。证明：设原问题（L）存在最优解，引进松弛变量，写成等价形式：00s.t.minvxbvAxcx（1）由于（1）存在最优解，因此可以用单纯形方法求出它的一个最优基本可行解，不妨设该最优解是vxy，相应的最优基是B。此时所有判别数均非正，即jcpwjj,0（2）1BcwB为单纯形乘子。39考虑所有原来变量（不包括松弛变量）在基B下的判别数，把它们所满足的条件（2）用矩阵形式写出：0cAw或cAw（3）把所有松弛变量在基B下的判别数所满足的条件（2）用矩阵形式写出：0)(Iw或0w（4）由（3）和（4）可知，w是对偶问题（D）的可行解。由于非基变量的取值为0，以及目标函数中松弛变量的系数为0，因此有xcycbBcbwBBB1根据定理2的推论1，w是对偶问题（D）的最优解，且原问题和对偶问题目标函数最优值相等。类似地可以证明，如果对偶问题存在最优解，则原问题也存在最优解，并且二者的目标值相等。注：也可用凸集分离定理证明该结论。但运用单纯形法证明该定理属于构造性证明，也适用于求解对偶问题。3.1.3互补松弛定理利用对偶定理可以证明原问题和对偶问题的最优解满足重要的互补松弛性质。对于互为对偶的一对线性规划问题，已知一个问题的最优解时，可以利用互补松弛定理求出另一个问题的最优解。定理4(对称形式的互补松弛定理)：设x和w分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是：0)(,0)(xcAwbxAw用iA表示矩阵A的第i行，用jp表示矩阵A的第j列。推论1设x和w分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是：(i)对nj,,1，若0jx，就有jjcpw；若jjcpw，就有0jx。(ii)对mi,,1，若0iw，就有iibxA；若iibxA，就有0iw。推论2设x是(L)的最优解，则w是(D)的最优解的充要条件是：(i)对nj,,1，若0jx，就有jjcpw；40(ii)对mi,,1，若iibxA，就有0iw。推论3设w是(D)的最优解，则x是(L)的最优解的充要条件是：(i)对nj,,1，若jjcpw，就有0jx;(ii)对mi,,1，若0iw，就有iibxA。例：设原问题对偶问题0,,23213s.t.32min321321321321xxxxxxxxxxxx0,133223s.t.2max2121212121设用图解法求得对偶问题的最优解为)711,71(),(21则可用互补松弛定理求原问题的最优解。由于在最优解w处，对偶问题的第3个约束成立严格不等式，因此原问题第3个变量03x。又由于w的两个分量均大于0，因此在原问题中前两个约束在最优解处成立等式，即23213321321xxxxxx把03x代入上述方程组，可解得741x，752x。原问题的最优解为Txxxx)0,75,74(),,(321。§3.2非线性规划的对偶理论3.2.1非线性规划的Lagrange对偶问题的表述非线性规划的对偶理论不像线性规划的对偶理论简单漂亮。可以通过多种不同的方式来构造非线性规划对偶问题，如基于Lagrange函数，凸函数的共轭函数及K-T最优性条件等。41不同构造方式基于的条件不同，所得结论亦有区别，从而应用场合不同。此节以Lagrange对偶为例，介绍非线性规划的对偶理论。原问题：.,,1,0)(,,1,0)(s.t.)(minDxljxhmixgxfji(5)D为nR的子集，它的选择影响到计算和修正对偶目标函数的计算量。令对偶目标函数（Lagrange对偶函数）为：Dxxhvxgwxfvwljjjmiii|)()()(inf),(11对偶问题：0s.t.),(maxwvw（6）例：求下列问题的Lagrange对偶问题。2221minxx,04s.t.21xx.0,021xx将变量的非负限制作为集约束：0,0|2121xxxxDx对偶函数：wxwxxxwxxxxxxwxxw40|inf0|inf0,|)4(inf)(2222112121212221由上式可知，当0w时，有)(2当0w时，由于0,21xx，则有4200222121wxxwxx因此当021xx时，得到极小值ww4)(综上分析，得到对偶函数：0,40,421)(2本例的对偶问题为0s.t.421)(max2问题的最优解和最优值为：8,)2,2(minfxT对偶问题的最优解和最优值为：8,4maxw问题：原问题与对偶问题解之间的关系？线性规划的弱对偶定理是否成立？线性规划的强对偶定理是否成立？原问题：.,0)(,0)(s.t.)(minDxxhxgxf其中,))(,),(()(1TmxgxgxgTlxhxhxh))(,),(()(1令TlTmvvv),,(,),,(11对偶问题：0s.t.),(maxwvw其中，DxxhvxgwxfvwTT|)()()(inf),(原问题的可行集：DxxhxgRxSn,0)(,0)(|对偶问题的可行集：0|),(wRvwSDlm433.2.2对偶定理定理5（弱对偶定理）：原问题（inf）在可行集上的目标值不小于对偶问题（sup）在可行集上的目标值，即SDvwSxvwxf),(,),,()(推论1;),(|),(sup|)(infSDvwvwSxxf推论2如果存在SDvwSx),(,使得),()(vwxf则x和),(vw分别是原问题和对偶问题的最优解。推论3如果,|)(infSxxf则有SDvwvw),(,),(推论4如果,),(|),(supSDvwvw则原问题不可行。对偶间隙：由推论1知supinff，若supinff，则原问题与对偶问题无对偶间隙；若supinff，则原问题与对偶问题有对偶间隙。下面的强对偶定理表明：对凸规划，在适当的约束规格下，原问题与对偶问题不会出现对偶间隙。定理6（强对偶定理）：设在（5）中下列条件满足：nRD)i(非空凸，mixgxfi,,1),(),(是凸函数；ljxhj,,1),(是线性函数。}.|)(int{0,0)ˆ(,0)ˆ(s.t.ˆ)ii(DxxhxhxgDx则有下列结论成立：(i);),(|),(sup|)(infSDvwvwSxxf(ii)若Sxxf|)(inf有限，则存在s.t.,),(SDvw;),(|),(sup),(SDvwvwvw(iii)若Sxxf|)(inf有限，且存在SxxfxfSx|)(inf)(s.t.,，则有0)(xgw。定理的解释：条件(i)要求原问题(5)为凸规划，条件(ii)要求原问题(5)满足约束规范；结论(i)说明原问题(5)和对偶问题(6)无对偶间隙；44结论(ii)说明原问题的目标函数)(xf在可行集上有下界时，其对偶问题有有限最优解，即上确界可以取到；结论(iii)说明若原问题有有限最优解时，则原问题和对偶问题在该最优解和对偶问题最优解满足互补松弛条件。习题1给定下列线性规划问题0,,7526s.t.230710max43243214314321xxxxxxxxxxxxxx（1）写出上述原问题的对偶问题；（2）用图解法求对偶问题的最优解；（3）利用对偶性质求解原问题的最优解和目标函数的最优值。2考虑下列原问题：01s.t.)1()1(min212221xxxx（1）用图解法求解原问题；（2）写出和求解对偶问题；（3）用对偶理论说明对偶规划的最优值是否等于原问题的最优值。