线性规划强对偶性的证明

· · 算法·理论

Farkas 引理

对于给定的 A\in R^{m\times n} 和 b\in R^m，以下两个命题对立成立：

\exist x\in R^n\land x\ge0,Ax=b \exist y\in R^m,A^Ty\le0\land b^Ty>0

考虑其几何意义，将 A 视为若干 m 维列向量的组合，其非负组合构成的是一个椎体。

若向量 b 位于锥体内，其一定可以被表示为 A 若干列的非负线性组合，即存在非负向量 x_1,x_2\cdots x_n 有 b=x_1a_1+x_2a_2\cdots x_na_n。这部分对应的是第一个命题。

反之，对于在椎体外的 b，一定存在这样一个 y，其与锥体内的所有向量余弦值为负，与 b 的余弦值为正，即:

\exist y\in R^m,A^Ty\le0\land b^Ty>0

证毕。

线性规划的强对偶性

写得好看点：

对于原始线性规划 \min\limits_x\{c^Tx|Ax\ge b,x\ge0\} 存在解 x^*，其对偶形式 \max\limits_y\{b^Ty|A^Ty\le c,y\ge0\} 存在解 y^*，则一定有 c^Tx^*=b^Ty^*。

令 z^*=c^Tx^*，即原线性规划的最优解，不妨设有以下向量：

\hat A=\left(\begin{matrix}A\\-c^T\end{matrix}\right),\hat b_\varepsilon=\left(\begin{matrix}b\\-z^*+\varepsilon\end{matrix}\right)

其中，\varepsilon>0，显然不存在 x\ge0 使得 \hat Ax=\hat b_\varepsilon，因为根据定义 -z^* 是能达到的最大值。故他不满足 Farkas 引理的第一个命题，故：

一定存在向量 \hat y=\left(\begin{matrix}y\\\alpha\end{matrix}\right) 使得 \hat A^T\hat y\le0\land\hat b_\varepsilon^T\hat y>0

等价于 A^Ty\le\alpha c,b^Ty>\alpha(z^*-\varepsilon)

根据定义：\hat b_\varepsilon^T\hat y=\hat b_0^T\hat y+\alpha\varepsilon>0

根据定义：\hat Ax^*=\hat b_0，故满足 Farkas 引理的第一个命题，所以对于一个 \hat A^T\hat y\le0 有 \hat b_0^T\hat y\le0。

又因为 \hat b_0^T\hat y+\alpha\varepsilon>0，有 \alpha\ge0。由此：

A^T\frac{y}{\alpha}\le c,b^T\frac{y}{\alpha}>z^*-\varepsilon

进而易得：\max\limits_y\{b^Ty|A^Ty\le c\}>z^*-\varepsilon

又由线性规划的弱对偶形可以知道：

z^*\ge\max\limits_y\{b^Ty|A^Ty\le c\}

故 z^*-\varepsilon<\max\limits_y\{b^Ty|A^Ty\le c\}\le z^*。

取 \varepsilon\to0，可以得到 z^*=\max\limits_y\{b^Ty|A^Ty\le c\}，即我们要证明的强对偶性。