Linear Dual

每个线性规划问题都有一个与之对应的对偶问题，对偶问题也是一个线性规划问题，并且对偶问题的对偶问题是原问题。原问题的最优解可以由对偶问题得到，有时候利用对偶理论求解线性规划问题更加简单，也更能了解问题的本质。在对偶理论的启发下，单纯形法的性能得到了改进，也出现了一些求解线性规划问题的非单纯形法，本文暂不详解。

对偶关系

考虑如下形式的对偶问题

$$\begin{align*} minimize\quad c^{T}x \\ subject\ to\quad Ax\ge b\\ A\ge0 \end{align*}$$

将其称为原问题，其相应的对偶形式定义为

$$\begin{align*} maximize\quad \lambda^{T}b \\ subject\ to\quad \lambda^{T} A\le c^{T}\\ \lambda \ge0 \end{align*}$$

其中$\lambda$称为对偶向量，这种对偶称为对称形式的对偶。 另外对于线性规划的标准形，其约束为$Ax=b$，等价于

$$\begin{align*} Ax\ge b\\ -Ax\ge -b \end{align*}$$

因此含有等式约束的原问题可以写为

$$\begin{align*} minimize\quad c^{T}x\\ subject\ to\quad \begin{bmatrix} A\\-A \end{bmatrix}x\ge \begin{bmatrix} b\\-b \end{bmatrix}\\ x\ge 0 \end{align*}$$

这与对称形式的原问题具有相同的结构，因此上述问题的对偶问题为

$$\begin{align*} maximize\quad [u^{T}\ v^{T}] \begin{bmatrix} b\\-b \end{bmatrix}\\ subject\ to\quad [u^{T}\ v^{T}] \begin{bmatrix} A\\-A \end{bmatrix}\le c^{T}\\ u,v\ge 0 \end{align*}$$

对偶问题可以整理为

$$\begin{align*} maximize\quad (u-v)^{T}b\\ subject\ to\quad (u-v)^{T}A\le c^{T}\\ u,v\ge 0 \end{align*}$$

令$\lambda=u-v$，上述问题则变为

$$\begin{align*} maximize\quad \lambda^{T}b\\ subject\ to\quad \lambda^{T}A\le c^{T} \end{align*}$$

注意此时由于$u,v\ge 0,\lambda=u-v$，没有了非负约束，将这种关系称为非对称形式的对偶。##对偶问题的性质 在这里给出对偶问题的一些基本结论，暂不做证明 弱对偶引理：假设$x$和$\lambda$分别是线性规划的原问题和对偶问题（对称形式及非对称形式）的可行解，则$x^{T}x\ge \lambda^{T}b$，即“极大值$\le$极小值”。

定理 1：假设$x_{0}$和$\lambda_{0}$分别是原问题和对偶问题的可行解，如果$c^{T}x_{0}=\lambda_{0}^{T}b$，那么$x_{0}$和$\lambda_{0}$分别是各自问题的最优解。

定理 2（对偶定理）：如果原问题有最优解，那么其对偶问题也有最优解，并且它们目标函数的最优解相同。

定理 3（互补松弛条件）：$x$和$\lambda$分别是原问题和对偶问题的可行解，则它们分别是各自问题的最优解的充分必要条件为

$$\begin{align*} 1.\quad(c^{T}-\lambda^{T}A)x=0\\ 2.\quad\lambda^{T}(Ax-b)=0 \end{align*}$$