拉格朗日松弛法、KKT条件与线性规划的对偶

拉格朗日松弛

深度解析拉格朗日乘子法，让你成为高手

对于等式约束，实际上是存在一条等值线，最优解必须存在在这条解上。

其目的是判断约束 $g(x)$的梯度方向是否和等值线的梯度方向共线。

即：

$$[x_1,x_2,x_3{]}^T=\lambda [y_1,y_2,y_3]$$

此时 $\lambda$取正负都可以。

KKT条件

KKT条件，原来如此简单 | 理论+算例实践

配合下式可以说：假设最优解出现在其中n个 $g(x)$上，那么他们可以被放到拉格朗日松弛目标函数中，其余的如果不满足约束说明假设错了，如果满足约束证明是一种可行解。

$$\begin{array}{ll}\min & f(X)\\ \text{ s.t. }& g_i(X)\le 0,i=1,\dots ,m\\ & h_j(X)=0,j=1,\dots ,n\end{array}$$

可以被转化为：

$$L=f\left(X\right)+\sum _{i=1}^m{\lambda }_i{g}_i\left(X\right)+\sum _{j=1}^n{\mu }_j{h}_j(X)$$

对于任意的X，要想使L满足要求(${\lambda }_i{g}_i\left(X\right)=0$)。考虑到 $g_i\left(X\right)\le 0$。问题就转化为求L关于 $\lambda$ 的最大值。

$$f\left(x^{\ast }\right)=\underset{x}{\min }f(x)=\underset{x}{\min }\left\{\underset{\lambda ,\mu }{\max }L(\lambda ,\mu ,x)\right\}$$

这样，自然的可以写出KKT条件。

$$\begin{array}{rl}& \nabla f\left(X^{\ast }\right)+\sum _{i=1}^m{\lambda }_i\nabla g_i\left(X^{\ast }\right)+\sum _{j=1}^n{\mu }_j\nabla h_j(X)=0\\ & {\lambda }_i{g}_i\left(X^{\ast }\right)=0,i=1,\dots ,m\\ & h_j\left(X^{\ast }\right)=0,j=1,\dots ,n\\ & {\lambda }_i\ge 0,i=1,\dots ,m\\ & g_i\left(X^{\ast }\right)\le 0,i=1,\dots ,m\end{array}$$

若 $g_i(X^{\ast })$等于0，说明约束张紧， $\lambda \ne 0$。若 $g_i(X^{\ast })$不等于0，说明约束不起作用（满足时）， $\lambda \ne 0$。

为什么 $\lambda \ge 0$呢？

$$g_i(X)\le 0$$

$g_i(x)$的梯度方向仍然是可行的。

求目标函数的最小值时，若目标函数的梯度方向与$g_i(x)$的梯度同向， 说明目标函数仍然可以继续下降，并没有取到最优值。

因此，

$$\nabla f\left(X^{\ast }\right)=-\lambda \nabla g_i(X^{\ast })$$

$$\begin{array}{ll}\min & x_1^2+2x_2^2-4x_1-4x_2\\ \text{ s.t. }& x_1+x_2\le 3\\ & x_1+2x_2\ge 5\end{array}$$

最小值需要整理为小于等与0的形式

$$\begin{array}{ll}\min & x_1^2+2x_2^2-4x_1-4x_2\\ \text{ s.t. }& x_1+x_2-3\le 0\\ & -x_1-2x_2+5\le 0\end{array}$$

$x_1^2+2x_2^2-4x_1-4x_2+{\lambda }_1(x_1+x_2+x_3)+{\lambda }_2(-x_1-x_2+5)$

（1）若 ${\lambda }_1={\lambda }_2=0$,求无约束极值问题：

需要检查 $g_i(X^{\ast })$是否小于0，若满足上式成立，一种可行解。

（2）若 ${\lambda }_1=0，{\lambda }_2\ne 0$

检查 ${\lambda }_2$是否大于0， $g_1(X^{\ast })$是否小于0，都满足是一种可行解

略

线性规划的对偶

$$\begin{array}{c}\min c^{T}x\\ \text{ s.t. }Ax\ge bx\ge 0\end{array}$$

利用KKT条件进行转化：

$$\begin{array}{rl}L(x,\lambda )& =c^{T}x-{\lambda }^T(Ax-b)\\ & ={\lambda }^{T}b+(c^T-{\lambda }^{T}A)x\end{array}(\lambda \ge 0)$$

这时的 $L(x,\lambda )$已经没有约束，若想使其有最小值，需要 $(c^T-{\lambda }^{T}A)$每一个分量都大于等于0。($x\ge 0$)

这时问题转化为如下形式：

$$\underset{x}{\min }L(x,\lambda )={\lambda }^{T}bif{c}^T-{\lambda }^{T}A\ge 0$$

由于 f ( x ∗ ) = min ⁡ x f ( x ) = min ⁡ x { max ⁡ λ , μ L ( λ , μ , x ) } f\left(x^*\right)=\min _x f(x)=\min _x\left\{\max _{\lambda, \mu} L(\lambda, \mu, x)\right\} f(x∗)=minx​f(x)=minx​{maxλ,μ​L(λ,μ,x)}

交换顺序：

$$\begin{gathered} f\left(x^{\ast }\right)=\underset{x}{\min }f(x)=\underset{\lambda }{\max }{b}^T\lambda \\ \begin{array}{rl}\text{s.t.}{A}^T\lambda & \le c\\ \lambda & \ge 0\end{array} \end{gathered}$$

对偶问题的标准形式

针对上述的推导，我们进行一定的拓展：

（1）若原问题存在等式约束

KKT条件退化为拉格朗日松弛，不需要对 $\lambda$进行限制

（2）若原问题存在自由变量。

若想使L有界，需要对系数项$(c^T-{\lambda }^{T}A)$置0，不等式约束转化为等式约束。

综上，对偶问题的转化关系如下：

原问题：

$$\begin{array}{ll}\min & c^{T}x\\ \text{ s.t. }& g_i(X)\le b_i,i=1,\dots ,p\\ & h_j(X)=b_j,j=p+1,\dots ,m\\ & x_l\ge 0,l=1,\dots ,q\\ & x_k\gtrless 0,k=q+1,\dots ,n\end{array}$$

对偶问题:

$$\begin{array}{ll}\max & b^T\lambda \\ \text{ s.t. }& {\lambda }_i\ge 0,i=1,\dots ,{\lambda }_i\\ & {\lambda }_j\gtrless 0,j=p+1,\dots ,m\\ & c_l-A_l^T\lambda \ge 0,l=1,\dots ,q\\ & c_l-A_l^T\lambda =0,k=q+1,\dots ,n\end{array}$$