LP 对偶：从内层优化到强对偶
推导对偶的关键有两步：先构造一个关于乘子的界，再把定义这个界的内层优化算出来。对于线性规划（LP），第二步尤其干净：内层是非负正交锥上的线性函数，其下确界只有“零”或“负无穷”两种可能。排除负无穷的条件，恰好就是对偶约束。
本文统一以最小化原问题为主，因此对偶提供下界。先讲定义，再推导，再解释 LP 为什么具有比一般非线性问题更强的对偶性质。
1 对偶的起点：把可行性写成一个极大化问题
考虑一般约束优化问题
\[ \begin{aligned} p^\star=\inf_{x\in X}\quad & f(x)\\ \text{s.t.}\quad & g_i(x)\le 0,\quad i=1,\ldots,m,\\ & h_k(x)=0,\quad k=1,\ldots,r. \end{aligned} \]
\(X\) 表示我们决定保留在内层的定义域，例如非负约束或盒约束。定义拉格朗日函数
\[ L(x,\lambda,\nu) =f(x)+\sum_{i=1}^{m}\lambda_i g_i(x) +\sum_{k=1}^{r}\nu_k h_k(x), \]
其中 \(\lambda\ge 0\)，\(\nu\in\mathbb R^r\) 自由取值。
1.1 乘子的符号为什么这样选？
固定一个原可行点 \(x\)，因为 \(g_i(x)\le 0\)，所以 \(\lambda_i g_i(x)\le 0\)；等式项则为零。因此
\[ L(x,\lambda,\nu)\le f(x). \]
这保证我们在构造最小化问题的下界。符号来自这个不等式，而不是约定俗成的口诀。
还可以更进一步。对固定的 \(x\)，
\[ \sup_{\lambda\ge0,\,\nu}L(x,\lambda,\nu) =\begin{cases} f(x),&x\text{ 满足所有约束},\\ +\infty,&x\text{ 至少违反一条约束}. \end{cases} \]
理由是：如果某个 \(g_i(x)>0\)，令对应 \(\lambda_i\to+\infty\)；如果某个 \(h_k(x)\ne0\)，令自由乘子沿相应符号无限增大。对可行点，取 \(\lambda=0,\nu=0\) 就达到上确界 \(f(x)\)。
因此原问题可以精确地写成
\[ p^\star=\inf_{x\in X}\sup_{\lambda\ge0,\,\nu}L(x,\lambda,\nu). \tag{1} \]
1.2 对调优化顺序，得到最好的拉格朗日下界
先固定乘子，定义对偶函数
\[ q(\lambda,\nu)=\inf_{x\in X}L(x,\lambda,\nu). \]
对于任意原可行点 \(\bar x\)，
\[ q(\lambda,\nu) \le L(\bar x,\lambda,\nu) \le f(\bar x). \]
所以每一组合法乘子都给出一个下界。尽量提高这个下界，得到拉格朗日对偶问题：
\[ d^\star=\sup_{\lambda\ge0,\,\nu}q(\lambda,\nu) \le p^\star. \tag{2} \]
式 (1) 和式 (2) 的差别，正是 \(\inf\sup\) 与 \(\sup\inf\) 的顺序。一般只能证明后者不超过前者；若两者相等，才叫强对偶。不能在推导中无条件交换这两个运算。
2 LP 的内层问题：究竟是怎样被精确算出来的？
取一种明确的 LP 形式：
\[ \begin{aligned} \text{(P)}\qquad \min_{x\in\mathbb R^n}\quad &c^\top x\\ \text{s.t.}\quad &Ax\ge b,\\ &x\ge0, \end{aligned} \]
其中 \(A\in\mathbb R^{m\times n}\)。把 \(Ax\ge b\) 写成 \(b-Ax\le0\)，引入 \(y\ge0\)；保留 \(X=\mathbb R_+^n\)，不把 \(x\ge0\) 再拉格朗日化。于是
\[ \begin{aligned} L(x,y)&=c^\top x+y^\top(b-Ax)\\ &=b^\top y+(c-A^\top y)^\top x. \end{aligned} \]
固定 \(y\)，记
\[ r(y)=c-A^\top y. \]
这个向量通常称为与该乘子对应的约化成本（reduced costs）。内层问题变成
\[ q(y)=b^\top y+\inf_{x\ge0}\sum_{j=1}^n r_j(y)x_j. \tag{3} \]
2.1 第一步：说明为什么可以逐分量处理
定义域是笛卡尔积 \(\mathbb R_+\times\cdots\times\mathbb R_+\)，目标也是各坐标的和，没有任何跨坐标的耦合约束。因此
\[ \inf_{x\ge0}\sum_jr_jx_j =\sum_j\inf_{t\ge0}r_jt. \]
这里每个分量的下确界只能是 \(0\) 或 \(-\infty\)，不会出现不定的 \(+\infty-\infty\)。这一步依赖可分离结构；若保留了耦合约束，就不能这样拆。
2.2 第二步：把一维问题完整分类
对 \(\phi(r)=\inf_{t\ge0}rt\)：
- \(r>0\)：\(rt\ge0\)，唯一极小点为 \(t=0\)，最优值是 \(0\)。
- \(r=0\)：所有 \(t\ge0\) 都是极小点，最优值仍是 \(0\)。
- \(r<0\)：取 \(t_k=k\)，则 \(rt_k\to-\infty\)，问题无下界，没有有限极小点。
因此
\[ \phi(r)=\begin{cases} 0,&r\ge0,\\ -\infty,&r<0. \end{cases} \]
代回式 (3)：
\[ q(y)=\begin{cases} b^\top y,&c-A^\top y\ge0,\\ -\infty,&\text{否则}. \end{cases} \tag{4} \]
只要一个系数为负，沿对应的坐标射线就能把内层值降到负无穷；全部非负时，\(x=0\) 就达到零。我们精确确定的是内层最优值；内层最优解未必唯一。
2.3 第三步：把有效定义域写成对偶约束
原可行集非空时，产生 \(-\infty\) 的乘子无法给出有用下界；即使原问题不可行，对偶函数式 (4) 仍然成立。将有效定义域显式写出，得到
\[ \boxed{ \begin{aligned} \text{(D)}\qquad \max_y\quad &b^\top y\\ \text{s.t.}\quad &A^\top y\le c,\\ &y\ge0. \end{aligned}} \]
严格来说，对偶首先由 \(\sup q(y)\) 定义；写作这个 LP 后，若最优值有限且可行，则最优值可以达到。
每一条原约束对应一个乘子；每一个原变量对应一次内层有界性检查。\(A^\top\) 出现，是因为第 \(j\) 个原变量的系数为 \(c_j-\sum_iA_{ij}y_i\)。
3 为什么“直接对内层求导等于零”有时是错的？
3.1 定义域决定有限性的条件
同样是线性项 \(rt\)，内层定义域一变，答案就变：
\[ \inf_{t\in\mathbb R}rt =\begin{cases}0,&r=0,\\-\infty,&r\ne0;\end{cases} \]
\[ \inf_{t\le0}rt =\begin{cases}0,&r\le0,\\-\infty,&r>0.\end{cases} \]
所以原变量自由时，对偶约束是等式；原变量非正时，不等式方向反过来。这些都来自同一个有限性计算。
若 \(t\) 被限制在有限区间 \([\ell,u]\)，则
\[ \inf_{\ell\le t\le u}rt =\begin{cases}r\ell,&r\ge0,\\ru,&r<0.\end{cases} \]
这时无论 \(r\) 的符号如何，下确界都有限。保留盒约束会得到分段线性的对偶函数，不必再强加 \(r\ge0\)。“对偶约束来自内层有界性”必须连同具体定义域一起理解。
3.2 边界最优不能套用无约束驻点条件
对于 \(\min_{x\ge0}r^\top x\)，正确的最优性条件是
\[ x\ge0,\qquad r\ge0,\qquad x_jr_j=0\quad\forall j. \]
并不是所有分量都要满足 \(r_j=0\)。当 \(r_j>0\) 时，\(x_j=0\) 是合法的边界最优解。
在几何上，有限性要求 \(r\) 属于非负锥的对偶锥：
\[ (\mathbb R_+^n)^* =\{r:r^\top x\ge0\ \forall x\ge0\} =\mathbb R_+^n. \]
更一般地，若保留的定义域是锥 \(K\)，则 \(\inf_{x\in K}r^\top x\) 在 \(r\in K^*\) 时为零，否则沿某条锥内射线降到负无穷。这说明 LP 的符号条件也是锥对偶的一个特例。
4 LP 对偶有什么特别好的性质？
4.1 弱对偶：一个可检查的下界证书
对任意原可行 \(x\) 和对偶可行 \(y\)，
\[ b^\top y\le y^\top Ax =x^\top A^\top y\le c^\top x. \tag{5} \]
因此，原可行解给出最小化问题的上界，对偶可行解给出下界。只要上下界相等，就得到了最优性证书，无需知道求解器如何找到这些解。
这是精确算法中非常实用的性质：一个启发式方法可以产生好解，但要证明“已经足够好”或“就是最优”，还需要一个有效的界。
4.2 对偶函数总是凹的，但不一定容易优化
对一般拉格朗日函数，固定 \(x\) 后，\(L\) 关于乘子是仿射函数。仿射函数族的逐点下确界是凹函数。因此 \(q\) 总是凹的，即使原问题非凸。
这不意味着非凸原问题突然变容易了：计算 \(q\) 的内层问题可能很难，也可能有严格的对偶间隙。LP 的优势是我们能显式计算内层，最后的对偶仍然是一个 LP。
4.3 强对偶与最优值可达
对于有限维 LP，只要 (P) 可行且 \(p^\star\) 有限，则 (P)、(D) 都有最优解，并且
\[ p^\star=d^\star. \]
这里不额外要求存在严格满足全部不等式的点。LP 的可行域是多面体，有限生成锥的闭性使分离论证能够给出精确的乘子证书。一般凸规划的常见充分条件是 Slater 条件，不能把它误写成所有 LP 都必须满足的前提。
例如约束 \(x\ge1\)、\(-x\ge-1\) 把可行集压成 \(\{1\}\)，不存在同时严格满足这两条不等式的点，但有限目标下 LP 强对偶仍成立。
下面给出这一结论中“为什么存在精确乘子”的证明。
5 强对偶的一个几何证明
使用一个标准的多面体结论：非空多面体上的线性目标如果有有限下确界，就可以达到它。取原最优解 \(x^\star\)，定义活跃集
\[ I=\{i:a_i^\top x^\star=b_i\}, \qquad J=\{j:x_j^\star=0\}, \]
其中 \(a_i^\top\) 是 \(A\) 的第 \(i\) 行。考虑有限生成锥
\[ C=\operatorname{cone}\bigl(\{a_i:i\in I\}\cup\{e_j:j\in J\}\bigr), \]
\(e_j\) 是第 \(j\) 个单位向量。我们要证明 \(c\in C\)。
5.1 如果目标方向不在这个锥里，就能找到下降方向
反设 \(c\notin C\)。因为有限生成锥闭且凸，锥分离定理给出方向 \(d\)，使得
\[ a_i^\top d\ge0\ (i\in I),\qquad d_j\ge0\ (j\in J),\qquad c^\top d<0. \]
前两组条件保证：从 \(x^\star\) 沿 \(d\) 走一小步，不会破坏已经取等号的约束。其他约束具有正的松弛，且数量有限，所以存在充分小的 \(\varepsilon>0\)，使 \(x^\star+\varepsilon d\) 仍然可行。
但它的目标值为
\[ c^\top(x^\star+\varepsilon d) =c^\top x^\star+\varepsilon c^\top d <c^\top x^\star, \]
与最优性矛盾。因此 \(c\in C\)。
5.2 锥表示直接给出对偶解
于是存在 \(y\ge0\) 和 \(s\ge0\)，分别只在 \(I\)、\(J\) 上可能非零，使得
\[ c=A^\top y+s. \]
因此 \(A^\top y\le c\)，\(y\) 对偶可行。根据乘子支撑的位置，还有
\[ y^\top(Ax^\star-b)=0,\qquad s^\top x^\star=0. \]
所以
\[ \begin{aligned} c^\top x^\star &=(A^\top y+s)^\top x^\star\\ &=y^\top Ax^\star+s^\top x^\star\\ &=y^\top b. \end{aligned} \]
我们不仅证明值相等，还构造性地证明了某个对偶最优乘子的存在。这里的逻辑是多面体最优性 → 锥分离 → 乘子表示 → 零间隙，没有把最小化和最大化顺序直接交换。MIT 一阶最优性讲义 也从法锥与最优性条件讨论这一联系。
6 互补松弛：把“零间隙”拆成逐项条件
对原、对偶可行的 \(x,y\)，记 \(r=c-A^\top y\ge0\)。目标差可以精确分解为
\[ \begin{aligned} c^\top x-b^\top y &=x^\top(c-A^\top y)+y^\top(Ax-b)\\ &=\sum_jx_jr_j+\sum_i y_i(a_i^\top x-b_i). \end{aligned} \tag{6} \]
每一项都非负，因此差为零，当且仅当
\[ x_jr_j=0\quad\forall j,\qquad y_i(a_i^\top x-b_i)=0\quad\forall i. \]
结合原可行性、对偶可行性，这些条件对 LP 的原、对偶最优性既必要又充分。它们就是 LP 的 KKT 条件。
两种条件分别表达两件事：
- \(x_jr_j=0\)：\(x\) 确实解决了固定 \(y\) 的内层最小化。
- \(y_i(a_i^\top x-b_i)=0\)：在该原可行点上，拉格朗日项没有把目标值进一步降低。
活跃约束不保证乘子严格为正，零约化成本也不保证原变量严格为正。 退化情形完全可能出现，普通互补松弛不等于严格互补。
7 一个完整算例：内层选了零，为什么原最优解不是零？
考虑
\[ \begin{aligned} \min\quad &3x_1+2x_2\\ \text{s.t.}\quad &x_1+x_2\ge4,\\ &2x_1+x_2\ge5,\\ &x_1,x_2\ge0. \end{aligned} \]
拉格朗日函数展开为
\[ \begin{aligned} L(x,y)=4y_1+5y_2 &+(3-y_1-2y_2)x_1\\ &+(2-y_1-y_2)x_2. \end{aligned} \]
内层有限恰好要求
\[ y_1+2y_2\le3,\qquad y_1+y_2\le2. \]
于是对偶为
\[ \begin{aligned} \max\quad &4y_1+5y_2\\ \text{s.t.}\quad &y_1+2y_2\le3,\\ &y_1+y_2\le2,\\ &y_1,y_2\ge0. \end{aligned} \]
取 \(y^\star=(1,1)\)，则两个约化成本都为零，\(L(x,y^\star)=9\) 对所有 \(x\ge0\) 成立。此时内层有无穷多个最优解，\(x=0\) 只是其中一个。
但是 \(x=0\) 不满足原约束。求内层时已经松弛了 \(Ax\ge b\)；不能把任意内层极小点当成原问题的解。
要恢复一个原最优解，还要施加原可行性和互补松弛。因为 \(y_1^\star,y_2^\star>0\)，两条原约束必须取等号：
\[ x_1+x_2=4,\qquad 2x_1+x_2=5. \]
解得 \(x^\star=(1,3)\)，并且
\[ c^\top x^\star=9=b^\top y^\star. \]
这也解释了一个常见误会：内层最优值可以显式、确定地计算，并不意味着它总能唯一确定原问题的最优解。
8 这些性质怎样用于算法与分析？
8.1 分支定界：用可行对偶乘子证明一个节点不值得继续
对于最小化整数规划，节点 LP 松弛的任意对偶可行解提供节点下界 \(L\)，当前整数可行解提供上界 \(U\)。若 \(L\ge U\)，该节点不可能改善当前最好目标值，可以剪枝。实际浮点求解还要结合可行性与最优性容差。
但零间隙只发生在 LP 原、对偶之间。例如整数问题
\[ \min\{x:2x\ge3,\ x\in\mathbb Z_{\ge0}\} \]
最优值为 \(2\)；它的 LP 松弛最优值为 \(1.5\)，对应对偶 \(\max\{3y:2y\le1,\ y\ge0\}\) 的最优值也是 \(1.5\)。LP 强对偶没有消除整数性间隙。
8.2 灵敏度：乘子是价值函数的次梯度
固定 \(A,c\)，把右端向量视为参数。对原、对偶可行且有限的情形，
\[ v(b)=\max_{y\ge0,\,A^\top y\le c}b^\top y. \]
因此 \(v\) 是关于 \(b\) 的凸分段线性函数。若 \(y^\star\) 在 \(b\) 处最优，那么对另一个有限可行的右端 \(b+\Delta b\)，
\[ v(b+\Delta b)\ge v(b)+(y^\star)^\top\Delta b. \]
若同一个 \(y^\star\) 在扰动后仍然最优，上式取等号。若 \(v\) 可微，乘子给出相应的梯度；若不可微，不能把某个乘子无条件当成唯一的边际价格。
8.3 对偶的对偶回到原 LP
把 (D) 视为标准的“最大化、\(\le\) 约束、非负变量”形式，再求一次对偶，就得到 \(\min c^\top x\)、\(Ax\ge b\)、\(x\ge0\)。这是形式上的对称性；它与强对偶是不同的陈述，后者还涉及可行性和最优值。
推导一个新问题时，最值得先写清楚的是：哪些约束进入乘子项、哪些留在定义域，内层是否真的可分，以及内层有限性的充要条件是什么。对 LP 而言，这些问题的答案共同决定了整个对偶模型。
9 参考资料
- MIT 6.854：LP Duality：弱对偶、强对偶及对偶的对偶。
- Gabriele Farina，MIT：First-order optimality conditions：多面体法锥与 LP 最优性。
- Boyd 与 Vandenberghe：Convex Optimization：第 5 章讨论一般拉格朗日对偶、间隙和灵敏度。