线性规划——对偶问题的对偶问题

原对偶问题

$$\begin{gathered} \underset{y}{\max }{b}^{T}y \\ s.t.A^{T}y+s=c \\ s\ge 0\text{\hspace{1em}(2)} \end{gathered}$$ $A\in {\mathbb{R}}^{m\times n},s\in {\mathbb{R}}^n,y\in {\mathbb{R}}^m$

等价问题： $$\begin{gathered} \underset{y}{\min }-b^{T}y \\ s.t.A^{T}y+s=c \\ s\ge 0\text{\hspace{1em}(2)} \end{gathered}$$ 对偶问题的推导参见博文《线性规划——对偶问题的推导》。

---

引入拉格朗日函数：$$L(x,y,s)=-b^{T}y+x^T(A^{T}y+s-c)$$ $$\begin{gathered} g(x)\triangleq \underset{y,s}{\inf }L(x,y,s) \\ =\underset{y,s}{\inf }\{-c^{T}x+(Ax-b{)}^{T}y+x^{T}s\} \\ =-c^{T}x+\underset{y}{\inf }(A^{T}x-b{)}^{T}y+\underset{s}{\inf }{x}^{T}s \end{gathered}$$

分开来看， $$\begin{gathered} \underset{y}{\inf }(Ax-b{)}^{T}y \\ =\{\begin{array}{lr}0,Ax-b=0& \\ -\infty ,otherwise& \end{array} \end{gathered}$$ $$\begin{gathered} \underset{s}{\inf }{x}^{T}s \\ =\{\begin{array}{lr}0,z\ge 0& \\ -\infty ,otherwise& \end{array} \end{gathered}$$ 显然，最大化 $g(x)$ 只有在其有下界时有意义。因此得到约束条件：$Ax-b=0,z\ge 0。$ 原对偶问题的对偶问题为：$$\begin{gathered} maximize-c^{T}x \\ s.t.Ax-b=0 \\ z\ge 0 \end{gathered}$$等价于$$\begin{gathered} minimize{c}^{T}x \\ s.t.Ax-b=0 \\ z\ge 0 \end{gathered}$$即为线性规划的标准形式。 得出结论： 线性规划的对偶问题的对偶问题是原问题。