对偶理论

阐述

标准形式

• 原始问题：$\min c^Tx,~\mathrm{s.t.}~Ax=b;x\ge0$
• 对偶问题：$\max p^Tb,~\mathrm{s.t.}~p^TA\le c^T$

几何形式

• 原始问题：$\min c^Tx,~\mathrm{s.t.}~Ax\ge b$
• 对偶问题：$\max p^Tb,~\mathrm{s.t.}~p^TA=c^T,p\ge0$

更一般的情形

来源

对于原始问题，我们可以从以下角度考虑：如果我们能找到一组组合系数 $p$，并保证 $p^TA\le c^T$，我们就有

$$c^Tx\ge p^TAx\ge p^Tb$$

因此我们就能给出一个原始问题目标函数值的下界 $p^Tb$。我们希望尽可能提高这个下界，此时就对应了这个对偶问题。

实例

性质

1. （弱对偶）原始问题的可行解对应的目标函数值一定大于对偶问题的可行解
   1. 如果 $x,p$ 可行，且 $p^Tb=c^Tx$，则两个都是最优的
2. （强对偶）如果原始问题有最优解，则对偶问题有一个同样数值的最优解
3. 原始问题和对偶问题的关系

情况	原始有界	原始无界	原始不可行
对偶有界	✅	❌	❌
对偶无界	❌	❌	✅
对偶不可行	❌	✅	✅

最优解的证明

对偶问题的解可以用来证明原始问题的解是最优的。也即如果同时提供了 $x, p$ 并且 $c^Tx=p^Tb$，则原始问题一定是最优解。

互补松弛性

设 $x,p$ 是两个问题的可行解，则下面的条件是他们最优性的充要条件：

$$p\odot(Ax-b)=0; (c-p^TA)\odot x=0$$

证明：注意到

$$c^Tx-p^Tb=\sum p\odot(Ax-b)+\sum(c-p^TA)\odot x$$

敏感度

如果约束改变了 $b\to b+\varepsilon$，则当 $\varepsilon$ 足够小的时候，对应的目标函数是

$$p^T(b+\varepsilon)=z^*+p^T\varepsilon$$

也就是说对偶问题的解是原始问题的约束的敏感度。

对偶单纯形法

可以直接求解一个线性规划问题，也可以先转化为对偶问题之后再求解。

在表格法中，意味着不要求 $x_B\ge0$，但是要求 $c=c^T-c_B^TB^{-1}A\ge0$

如果在已经得到最优解之后又加了一个约束，则原始问题不一定仍然可行，但是对偶问题仍然是可行的。

相关内容

参考文献