第3章--对偶理论

第3章 对偶理论3.1 线性规划的对偶理论3.1.1 对偶问题的表述对称形式的对偶： （L） (D) s.t. s.t. 其中为维行向量，为矩阵，为维列向量，表示维列向量，表示维行向量。 称(D)为线性规划(L)的对偶规划问题。定理1 (L)与(D)互为对偶规划问题。（对合性）例 设原问题 对偶问题 非对称形式的对偶： （LP） (DP) s.t. s.t. 例 设原问题 对偶问题 一般线性规划问题：可化为上述二者之一讨论其对偶问题，也可直接写出对偶问题，详细的对应法则见教材（陈宝林）124页。直接写出对偶的弊端之一是对偶最优解不易确定，而对称形式和非对称形式对偶的最优解都可由原问题的单纯形乘子确定出来。3.1.2 对偶定理(强对偶定理和弱对偶定理)定理2 (弱对偶定理)：设和分别是 （L） 和 (D) s.t. s.t. 的可行解，则有下列不等式成立： 证明：由于和，则有。由于和，则有。因此有推论1 设和分别是(L)和(D)的可行解，且有，则和分别是(L)和(D)的最优解。推论2 如果(L)的目标函数在可行集上无下界，则对偶规划(D)无可行解。推论3 如果(D)的目标函数在可行集上无上界，则原始规划(L)无可行解。定理3 (强对偶定理)：如果互为对偶规划的两个问题之一有最优解，则另一个问题也有最优解，并且二者的目标值相等。证明：设原问题（L）存在最优解，引进松弛变量，写成等价形式： （1）由于（1）存在最优解，因此可以用单纯形方法求出它的一个最优基本可行解，不妨设该最优解是，相应的最优基是B。此时所有判别数均非正，即 （2）为单纯形乘子。考虑所有原来变量（不包括松弛变量）在基B下的判别数，把它们所满足的条件（2）用矩阵形式写出： 或 （3）把所有松弛变量在基B下的判别数所满足的条件（2）用矩阵形式写出： 或 （4）由（3）和（4）可知，是对偶问题（D）的可行解。由于非基变量的取值为0，以及目标函数中松弛变量的系数为0，因此有根据定理2的推论1，是对偶问题（D）的最优解，且原问题和对偶问题目标函数最优值相等。类似地可以证明，如果对偶问题存在最优解，则原问题也存在最优解，并且二者的目标值相等。注：也可用凸集分离定理证明该结论。但运用单纯形法证明该定理属于构造性证明，也适用于求解对偶问题。3.1.3 互补松弛定理利用对偶定理可以证明原问题和对偶问题的最优解满足重要的互补松弛性质。对于互为对偶的一对线性规划问题，已知一个问题的最优解时，可以利用互补松弛定理求出另一个问题的最优解。 定理4 (对称形式的互补松弛定理)：设和分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是：用表示矩阵的第行，用表示矩阵的第列。 推论1 设和分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是： (i) 对，若，就有；若，就有。 (ii) 对，若，就有；若，就有。 推论2 设是(L)的最优解，则是(D)的最优解的充要条件是： (i) 对，若，就有； (ii) 对，若，就有。 推论3 设是(D)的最优解，则是(L)的最优解的充要条件是： (i) 对，若，就有; (ii) 对，若，就有。 例： 设原问题 对偶问题 设用图解法求得对偶问题的最优解为则可用互补松弛定理求原问题的最优解。由于在最优解处，对偶问题的第3个约束成立严格不等式，因此原问题第3个变量。又由于的两个分量均大于0，因此在原问题中前两个约束在最优解处成立等式，即把代入上述方程组，可解得，。原问题的最优解为。3.2 非线性规划的对偶理论3.2.1 非线性规划的Lagrange对偶问题的表述非线性规划的对偶理论不像线性规划的对偶理论简单漂亮。可以通过多种不同的方式来构造非线性规划对偶问题，如基于Lagrange函数，凸函数的共轭函数及K-T最优性条件等。不同构造方式基于的条件不同，所得结论亦有区别，从而应用场合不同。此节以Lagrange对偶为例，介绍非线性规划的对偶理论。 原问题： (5)D为的子集，它的选择影响到计算和修正对偶目标函数的计算量。令对偶目标函数（Lagrange对偶函数）为： 对偶问题： （6） 例：求下列问题的Lagrange对偶问题。将变量的非负限制作为集约束：对偶函数：由上式可知，当时，有当时，由于，则有因此当时，得到极小值综上分析，得到对偶函数：本例的对偶问题为问题的最优解和最优值为： 对偶问题的最优解和最优值为： 问题：原问题与对偶问题解之间的关系？线性规划的弱对偶定理是否成立？线性规划的强对偶定理是否成立？原问题： 其中 令对偶问题： 其中，原问题的可行集：对偶问题的可行集：3.2.2 对偶定理定理5（弱对偶定理）：原问题（inf）在可行集上的目标值不小于对偶问题（sup）在可行集上的目标值，即推论1 推论2 如果存在使得 则和分别是原问题和对偶问题的最优解。推论3 如果 则有推论4 如果 则原问题不可行。 对偶间隙：由推论1知，若，则原问题与对偶问题无对偶间隙；若，则原问题与对偶问题有对偶间隙。 下面的强对偶定理表明：对凸规划，在适当的约束规格下，原问题与对偶问题不会出现对偶间隙。定理6（强对偶定理）：设在（5）中下列条件满足：非空凸，是凸函数；是线性函数。则有下列结论成立：(i) (ii) 若有限，则存在(iii) 若有限，且存在，则有。定理的解释：条件(i)要求原问题(5)为凸规划，条件(ii)要求原问题(5)满足约束规范；结论(i)说明原问题(5)和对偶问题(6)无对偶间隙；结论(ii)说明原问题的目标函数在可行集上有下界时，其对偶问题有有限最优解，即上确界可以取到；结论(iii)说明若原问题有有限最优解时，则原问题和对偶问题在该最优解和对偶问题最优解满足互补松弛条件。习题1 给定下列线性规划问题（1） 写出上述原