从Lagrange对偶到线性规划对偶问题
#! https://zhuanlan.zhihu.com/p/597492395 # 从Lagrange对偶到线性规划对偶问题
Lagrange对偶
我们熟悉Lagrange乘子法，它是求解带有等式约束的最值问题的方法，而Lagrange对偶函数可以理解为是它的一种拓展，它能解决带有等式和不等式约束的问题，也就是标准形式的优化问题。标准形式的优化问题形如
\[ \min f_0(x) \\ {s.t.}\left \{ \begin{array}{l} f_i(x)\le 0,i=1,\dots ,m\\ h_i(x)=0,i=1,\dots ,p \end{array} \right. \]
设问题的定义域\(D = \cap_{i=0}^m dom \ f_i \cap \cap_{i=1}^p dom \ h_i\)非空，最优值为\(p^*\)。
定义Lagrange对偶函数\(g:R^m \times R^p \rightarrow R\)，对\(\lambda \in R^m\)，\(v \in R^p\)有
\[ g(\lambda,v) = \inf_{x\in D} L(x,\lambda,v) = \inf_{x\in D} (f_0(x)+\sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p v_i h_i(x)) \]
如果Lagrange函数关于x无下界，那么对偶函数取值为\(-\infty\)。无论原问题的凸性如何，Lagrange对偶函数都是凹函数。因为它是一族关于\(\lambda,v\)的线性函数的逐点下确界。
对偶函数值构成了原问题最优值的下界，即对于任意的\(\lambda \ge 0\)和\(v\)，有
\[ g(\lambda,v) \le p^* \]
证明是显然的。
Lagrange对偶函数与共轭函数
我们知道\(f:R^n \rightarrow R\)的共轭函数\(f^*\)为
\[ f^*(y) = \sup_{x\in dom \ f} (y^Tx-f(x)) \]
一些情况下利用共轭函数，我们可以简化Lagrange对偶函数。考虑一个优化问题
\[ \min f_0(x) \\ {s.t.}\left \{ \begin{array}{l} Ax \le b\\ Cx = d \end{array} \right. \]
利用\(f_0\)的共轭函数，我们可以导出它的对偶函数
\[ g(\lambda,v) = \inf_x (f_0(x) + \lambda^T (Ax-b) + v^T (Cx-d))\\ = -b^T\lambda - d^Tv + \inf_x (f_0(x) + (A^T\lambda + C^T v)^T x)\\ = -b^T\lambda - d^Tv - f_0^* (-A^T\lambda-C^Tv) \]
Lagrange对偶问题
前面提到对偶函数值给出原问题最优值的下界，那么我们希望得到最优的下界，也就是
\[ \max g(\lambda,v) \\ {s.t.} \begin{array}{l} \lambda \ge 0 \end{array} \]
这是一个凸优化问题，它的凸性与原问题的凸性无关。
强对偶性与Slater条件
如果Lagrange对偶问题的最优解是\(d^*\)，我们知道一定有\(d^*\le p^*\)。在一些情况下，有\(d^*=p^*\)，那么此时强对偶性成立。
如果原问题是凸的，那么在一些情况下（并不是所有情况）强对偶性会成立。一个简单的约束准则是Slater条件，当原问题是凸的且Slater条件成立，那么强对偶性成立。对于如下形式的凸问题
\[ \min f_0(x) \\ {s.t.}\left \{ \begin{array}{l} f_i(x)\le 0,i=1,\dots ,m\\ Ax = b \end{array} \right. \]
Slater条件说的是存在一点\(x\in relint \ D\)，也就是D的相对内点，使下式成立
\[ f_i(x) < 0,\quad i=1,\dots,m, \quad Ax=b \]
而在不等式约束\(f_i\)中，如果其中一些是仿射函数（线性函数）时，Slater条件可以进一步的改进。如果最前面的k个约束\(f_1,\dots,f_k\)是仿射的，则Slater条件可以改进为存在一点\(x\in relint \ D\)使得
\[ f_i(x)\le 0, \ i=1,\dots,k, \quad f_i(k)<0, \ i=k+1,\dots,m,\quad Ax=b \]
也就是说其中仿射的不等式约束是不需要严格成立的。
线性规划对偶问题
根据Slater条件，我们不难发现，对于任意的线性规划问题，只要是原问题是可行的，就满足（改进的）Slater条件，也就是强对偶性成立。因此研究线性规划问题的对偶问题是很有价值的。另一方面研究线性规划的对偶问题对我们后续的处理、解释等都是有好处的。
标准形式线性规划
对于标准形式的线性规划，即
\[ \min c^T x \\ {s.t.}\left \{ \begin{array}{l} Ax = b\\ x\ge 0 \end{array} \right. \]
它的Lagrange函数为 \[ L(x,\lambda,v) = c^Tx-\lambda^Tx+v^T(Ax-b) = -b^Tv + (c+A^Tv-\lambda)^Tx \]
所以它的Lagrange对偶函数为 \[ g(\lambda,v) = \inf_x L(x,\lambda,v) = -bv^T + \inf_x (c+A^Tv-\lambda)^Tx \]
我们知道非常函数的仿射函数是无界的，因此 \[ g(\lambda) = \left \{ \begin{array}{l} -b^Tv\lambda,A^Tv-\lambda+c=0\\ -\infty,A^Tv-\lambda+c\neq0 \end{array} \right . \]
所以它的对偶问题就为
\[ \max -b^Tv \\ {s.t.}\left \{ \begin{array}{l} A^Tv-\lambda+c=0\\ \lambda \ge 0 \end{array} \right. \]
它等价于
\[ \max -b^Tv \\ {s.t.} \begin{array}{l} A^Tv+c\ge0\\ \end{array} \]
不等式形式线性规划
不等式形式线性规划即
\[ \min c^T x \\ {s.t.} \begin{array}{l} Ax \le b \end{array} \]
它的Lagrange函数为
\[ L(x,\lambda) = c^T x + \lambda^T(Ax-b) = -b^T \lambda + (A^T \lambda + c)^T x \]
所以它的Lagrange对偶函数为
\[ g(\lambda) = \inf_x L(x,\lambda) = -b^T \lambda + \inf_x (A^T \lambda + c)x \]
我们知道，对于一个仿射函数，如果不是常函数，那么它是无界的，因此
\[ g(\lambda) = \left \{ \begin{array}{l} -b^T\lambda,A^T\lambda+c=0\\ -\infty,A^T\lambda+c\neq0 \end{array} \right . \]
所以它的对偶问题就为
\[ \max -b^T \lambda \\ {s.t.}\left \{ \begin{array}{l} A^T\lambda+c=0\\ \lambda \ge 0 \end{array} \right. \]
可以看到，标准形式线性规划的对偶问题是只含有不等式约束的线性规划，只含有不等式约束的线性规划的对偶问题是标准形式的线性规划。
一般形式的线性规划
对于一般形式的线性规划，也就是
\[ \min c^T x + d \\ {s.t.}\left \{ \begin{array}{l} Gx \le h\\ Ax = b \end{array} \right. \]
它的Lagrange函数为 \[ L(x,\lambda,v) = c^Tx + d + \lambda^T(Gx-h)+v^T(Ax-b) = -b^Tv -h^T\lambda+d + (c+A^Tv+G^T\lambda)^Tx \]
所以它的Lagrange对偶函数为 \[ g(\lambda,v) = \inf_x L(x,\lambda,v) = -b^Tv -h^T\lambda+d + \inf_x (c+A^Tv+G^T\lambda)^Tx \]
利用仿射函数的性质，得 \[ g(\lambda) = \left \{ \begin{array}{l} -b^Tv -h^T\lambda+d ,c+A^Tv+G^T\lambda=0\\ -\infty,c+A^Tv+G^T\lambda\neq0 \end{array} \right . \]
所以它的对偶问题为
\[ \max -b^Tv -h^T\lambda+d \\ {s.t.}\left \{ \begin{array}{l} c+A^Tv+G^T\lambda=0\\ \lambda \ge 0 \end{array} \right. \]
观察它的特点，原问题中x的项都失去x并出现在了约束中，而原问题中的不含x的项则出现在了目标函数中。实际上，网上有很多关于利用原问题直接写出对偶问题的记忆法，这里不再赘述。