线性规划对偶

一对标准形式 ​

考虑覆盖形式的线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。

$$\begin{array}{rl}\text{(P)}\underset{x}{min}& c^{\mathsf{T}}x\\ \text{s.t.}& Ax\ge b,\\ & x\ge 0.\end{array}$$

它的对偶是

$$\begin{array}{rl}\text{(D)}\underset{y}{max}& b^{\mathsf{T}}y\\ \text{s.t.}& A^{\mathsf{T}}y\le c,\\ & y\ge 0.\end{array}$$

原问题的每条约束产生一个对偶变量，每个原变量则产生一条对偶约束。若原约束改为等式，对应对偶变量不受符号限制；若原变量是自由变量，对应对偶约束改为等式。最大化、$\le$ 形式也可通过统一变号得到等价配对，因此使用对偶公式前必须先固定标准形式，不能只凭变量名称猜不等号方向。

弱对偶与证书 ​

对任意原始可行 $x$ 和对偶可行 $y$，非负性与两侧约束给出

$$c^{\mathsf{T}}x\ge x^{\mathsf{T}}{A}^{\mathsf{T}}y=y^{\mathsf{T}}Ax\ge b^{\mathsf{T}}y.$$

这就是弱对偶：每个对偶可行解都给最小化原问题的下界，每个原始可行解都给上界。二者目标差

$$c^{\mathsf{T}}x-b^{\mathsf{T}}y\ge 0$$

是可直接核验的对偶间隙。若某对可行解的目标相等，弱对偶立即证明它们分别最优；这个结论不需要先知道最优值，也不依赖求解算法如何找到它们。

强对偶与互补松弛 ​

有限维 LP 的强对偶说明：若原问题可行且最优值有限，则对偶也取得最优解，且两侧最优值相等；交换原、对偶后同样成立。强对偶保证最紧的线性证书不会留下间隙，但不表示任意原始可行点与任意对偶可行点都会相遇。

一对可行解 $x,y$ 同时最优，当且仅当满足互补松弛：

$$y_i((Ax{)}_i-b_i)=0\text{对每条原约束，}$$

以及

$$x_j(c_j-(A^{\mathsf{T}}y{)}_j)=0\text{对每个原变量。}$$

也就是说，正的对偶价格只能落在紧的原约束上，正的原变量只能对应紧的对偶约束。互补松弛不是额外的建模假设，而是把零对偶间隙逐项拆开后得到的最优性条件。

顶点覆盖的对偶图像 ​

加权顶点覆盖的 LP 松弛为

$$min\sum _{v\in V}{w}_v{x}_v\text{s.t.}{x}_u+x_v\ge 1(uv\in E),x_v\ge 0.$$

其对偶给每条边一个非负变量 $y_e$：

$$max\sum _{e\in E}{y}_e\text{s.t.}\sum _{e\ni v}{y}_e\le w_v(v\in V),y_e\ge 0.$$

原始变量表示是否购买顶点，对偶变量把预算装入边；每个顶点承受的相邻边总价不能超过其权重。任何合法装价都给出整数顶点覆盖成本的下界，因为整数可行域包含在 LP 松弛中。原始—对偶方法公理库原始—对偶方法Primal-dual method同时维护原问题与对偶问题的可行性和互补条件以构造解的算法框架。会提高这些边价直到顶点约束变紧，再据此构造覆盖；Dual Fitting公理库Dual Fittingdual fitting · 对偶拟合法从算法收费构造可能不可行的对偶解，再统一缩放为可行下界证书。则允许装价暂时超出容量，事后以统一因子缩放成可行证书。

边界与辨析 ​

LP 强对偶只连接连续松弛的两侧。若原问题要求 $x$ 取整数，对偶最优值仍只是松弛界；整数最优值与 LP 值之间可能存在整数性间隙公理库整数性间隙Integrality gap衡量整数最优值与其松弛最优值在最坏实例上的比值。。因此“原、对偶目标相等”能证明 LP 最优，不能自动证明某个取整方案最优。

若原问题无界，则对偶必不可行；但原问题不可行时，对偶可能不可行，也可能无界，单看一侧状态不能任意反推另一侧。数值求解器报告的近似可行解还要把约束残差计入上下界，不能把一个很小的目标差单独当成精确证书。

拉格朗日对偶公理库拉格朗日对偶Lagrange duality通过拉格朗日函数构造原问题下界的对偶问题，并研究弱对偶、强对偶与最优性条件。可以从更一般的约束优化问题构造对偶函数，在线性情形会导出这里的 LP 对偶。组合优化中的原始—对偶与 dual fitting 只需当前页面的线性可行性、弱对偶和互补松弛；把一般凸分析整条路径列为先修会掩盖它们实际使用的证书结构。

参考资料

• Alexander Schrijver, Theory of Linear and Integer Programming, Wiley, 1986，Chs. 7–8。
• Bernhard Korte and Jens Vygen, Combinatorial Optimization, 6th ed., Springer, 2018，Chs. 4–5。
• David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011，Ch. 1。