OPT学习笔记-5：线性规划对偶

对偶理论把“求一个最小值”转化为“寻找尽可能大的下界”。在线性规划中，这些下界可以通过对原约束作非负加权得到。

从有效不等式出发

考虑原问题

$$ \begin{aligned} p^*=\min_x\quad&c^\top x\\ \text{s.t.}\quad&Ax\ge b. \end{aligned} \tag{P} $$

有效不等式¶若对集合 $S$ 中所有 $x$ 都有$$ \alpha^\top x\ge\beta, $$则称该不等式是 $S$ 的有效不等式。

把 $Ax\ge b$ 的各行乘以非负权重 $\lambda_i$ 后相加，得到

$$ (A^\top\lambda)^\top x\ge b^\top\lambda, \qquad\lambda\ge0. $$

如果进一步要求 $A^\top\lambda=c$，则对每个原问题可行点都有

$$ c^\top x\ge b^\top\lambda. $$

因此 $b^\top\lambda$ 是原问题最优值的下界。寻找这类下界中最大的一个，就得到对偶问题

$$ \begin{aligned} d^*=\max_\lambda\quad&b^\top\lambda\\ \text{s.t.}\quad&A^\top\lambda=c,\\ &\lambda\ge0. \end{aligned} \tag{D} $$

弱对偶定理¶若 $x$ 是原问题可行解，$\lambda$ 是对偶问题可行解，则$$ c^\top x\ge b^\top\lambda. $$因此 $p^*\ge d^*$。

证明. 由 $A^\top\lambda=c$、$Ax\ge b$ 和 $\lambda\ge0$，$$ c^\top x =(A^\top\lambda)^\top x =\lambda^\top Ax \ge\lambda^\top b =b^\top\lambda. $$ □

弱对偶立即给出：

$$ c^\top x-b^\top\lambda\ge0 $$

称为对偶间隙（duality gap）。

强对偶的关键是：如果目标下界在最优点处有效，那么它可以由紧约束的非负组合生成。

Farkas 引理的一种形式¶给定向量 $a_1,\ldots,a_m,c\in\mathbb{R}^n$，下列两者恰有一个成立：存在 $\lambda\ge0$ 使 $c=\sum_i\lambda_i a_i$；存在 $d\in\mathbb{R}^n$ 使 $a_i^\top d\ge0$ 对所有 $i$ 成立，但 $c^\top d<0$。

证明. 令$$ K=\left\{\sum_i\lambda_i a_i:\lambda_i\ge0\right\}. $$$K$ 是闭凸锥。若 $c\notin K$，由点与闭凸集的分离定理，存在 $d$ 将 $c$ 与 $K$ 严格分离。因为 $K$ 是锥且包含 $0$，分离关系可以归一化为$$ d^\top z\ge0,\quad\forall z\in K, \qquad d^\top c<0. $$特别地 $a_i\in K$，所以 $a_i^\top d\ge0$。反之，若两种情况同时成立，则$$ c^\top d=\sum_i\lambda_i a_i^\top d\ge0, $$与 $c^\top d<0$ 矛盾。□

线性规划强对偶定理 ¶ 若原问题 $(P)$ 存在最优解，则对偶问题 $(D)$ 也存在最优解，并且 $$ p^*=d^*. $$

证明. 设 $x^*$ 是原问题最优解，令紧约束指标集为$$ I=\{i:a_i^\top x^*=b_i\}. $$先证明 $c$ 属于紧约束法向量生成的锥。否则由 Farkas 引理，存在 $d$ 使$$ a_i^\top d\ge0\quad(i\in I), \qquad c^\top d<0. $$对 $i\notin I$，约束在 $x^*$ 处有严格余量，因此取足够小的 $\varepsilon>0$ 后，$x^*+\varepsilon d$ 仍满足所有约束；而$$ c^\top(x^*+\varepsilon d)与 $x^*$ 最优矛盾。因此存在 $\lambda_i^*\ge0$（$i\in I$）使 $c=\sum_{i\in I}\lambda_i^*a_i$。对 $i\notin I$ 令 $\lambda_i^*=0$，则 $\lambda^*$ 对偶可行，且$$ \begin{aligned} b^\top\lambda^* &=\sum_{i\in I}b_i\lambda_i^*\\ &=\sum_{i\in I}(a_i^\top x^*)\lambda_i^*\\ &=c^\top x^*=p^*. \end{aligned} $$弱对偶又给出 $d^*\le p^*$，故 $d^*=p^*$，且 $\lambda^*$ 为对偶最优解。□

强对偶说明，只要找到原、对偶可行解并验证目标值相等，就同时获得两边的最优性证书。

互补松弛¶设 $x^*$ 和 $\lambda^*$ 分别是 $(P)$ 与 $(D)$ 的可行解。二者同时最优，当且仅当$$ \lambda_i^*(a_i^\top x^*-b_i)=0, \qquad i=1,\ldots,m. $$

证明. 原、对偶目标值之差为$$ \begin{aligned} c^\top x^*-b^\top\lambda^* &=(A^\top\lambda^*)^\top x^*-b^\top\lambda^*\\ &=\sum_i\lambda_i^*(a_i^\top x^*-b_i). \end{aligned} $$每一项都非负，因此总和为零当且仅当每一项都为零。由强对偶，零对偶间隙又等价于两边同时最优。□

互补松弛的含义是：

对最小化原问题，约束方向决定对偶变量符号：

类似地，原变量的符号限制决定对偶约束是等式还是不等式。最稳妥的推导方式不是死记表格，而是重新执行“约束聚合并匹配目标系数”这一步。