拉格朗日乘子法和KKT条件

首先，拉格朗日乘子法和kkt条件都是解决数学中最优化问题的方法。什么时候会用到这种方法呢？
比如，求解函数 $f(x) = x^2-2x -1$ ，直接求 $f(x)$ 关于x的一阶导数，让一阶导数为0，便得到 $f(x)$ 取最小值时的最优解为1。但要是x有限制条件呢？那么就会用到上面的两种方法。

一、限制条件为等式
$\begin{cases} \min_{x,y}f(x,y)\\ g(x,y)=0\\ \end{cases}$
这是一个有等式约束的优化问题，如果不借助其他工具是不是很难求解，尤其是 $f(x,y)$ 或g(x,y)都比较复杂的情况下。拉格朗日乘子法将这个问题转化成了无约束问题，那么就可以用求偏导的方法去求解。拉格朗日函数为：
$L(x,y,\lambda)=f(x,y)+\lambda g(x,y) \\ \lambda!=0$
求 $L(x,y,\lambda)$ 分别关于 $x,y,\lambda$ 的偏导(没有找到偏导符号，用d代替)：
$\frac {dL(x,y,\lambda)}{dx}=0\\ \frac {dL(x,y,\lambda)}{dy}=0\\ \frac {dL(x,y,\lambda)}{d\lambda}=0\\$
通过求解 $x,y,\lambda$ 的偏导数为0，便可获得 $L(x,y,\lambda)$ 取极值时的最优解。
那么为什么这样做呢？即 $L(x,y,\lambda)$ 取极值时的最优解是否就是 $f(x,y)$ 的最优解呢？其实在等式约束条件这里是非常容易理解的，因为 $L(x,y,\lambda)$ 的后半分 $\lambda g(x,y)$ 恒等于0，那么自然 $L(x,y,\lambda)$ 和 $f(x,y)$ 的最优解是一致的。
从另一个角度来看，下图是对原问题的几何描述，只有当 $f(x,y)$ 和 $g(x,y)=0$ 的切线重合的时候，原问题能够取得最优解。那么在切点的梯度有 $\Delta f(x,y)=\lambda \Delta g(x,y)$

图1

那么限制条件为不等式呢？下面来看

二、限制条件为不等式
当最优解问题是：
$\begin{cases} \min_{x,y}f(x,y)\\ g(x,y)<=0\\ \end{cases}$
那么如果同样用拉格朗日函数将上述有约束问题化解为无约束问题，是否可以直接通过求 $L(x,y,\lambda)$ 分别关于 $x,y,\lambda$ 的偏导，令偏导数为0来获得最优解呢？答案是不能。为什么不能呢？看下图就明白了：

图2

上图中，

f(x,y)

的极值并没有落在切线上，这个时候

g(x,y)<0

，切点处的

x,y,\lambda

已经不是最优解了。

所以我们采用广义拉格朗日乘子法，先求 $L(x,y,\lambda)$ 关于乘子的最大，再求关于x,y的最小。原始问题的拉格朗日函数为：
$min_{x,y}max_{\lambda}L(x,y,\lambda)=f(x,y)+\lambda g(x,y)$
这个问题很难求解，所以想要将问题转化为原问题的对偶问题：
$min_{\lambda}max_{x,y}L(x,y,\lambda)=f(x,y)+\lambda g(x,y)$
那么原问题和对偶问题的解是否等价呢？

所以这里我们引入KKT条件， $x,y,\lambda$ 同时是原始问题和对偶问题的解的充分必要条件就是满足以下条件：

$\frac {dL(x,y,\lambda)}{d{x,y,\lambda}}=0$
$\lambda>=0$
$\lambda g(x,y)=0$
$g(x,y)<=0$
当 $x,y,\lambda$ 满足上述的kkt条件时，对偶问题的解就是原始问题的解。当约束如图1所示，那么 $g(x,y)=0，\lambda >0$ ；当约束如图2所示，实际上约束已经不起作用，那么 $g(x,y)<0，\lambda =0$ 。

拉格朗日乘子法和KKT条件

推荐阅读更多精彩内容