1 前言
拉格朗日乘子法(Lagrange Multiplier) 和 KKT(Karush-Kuhn-Tucker) 条件是求解约束优化问题的重要方法，在有等式约束时使用拉格朗日乘子法，在有不等约束时使用 KKT 条件。当然，这两个方法求得的结果只是必要条件，只有当目标函数是凸函数的情况下，才能保证是充分必要条件。
1.1 最优化问题三种约束条件
1：无约束条件
解决方法通常是函数对变量求导，令导函数等于0的点可能是极值点，将结果带回原函数进行验证。
2：等式约束条件
设目标函数为 $f(x)$，约束条件为 $h_k(x)$。s.t. 表示 subject to ，“受限于”的意思。比如：
$\quad min \quad f(x)$
$\quad s.t.\quad h_{k}(x)=0 \quad k=1,2,...,l$
解决方法是 消元法 或者 拉格朗日法，消元法比较简单不在赘述。
3：不等式约束条件
设目标函数 $f(x)$，不等式约束为 $g(x)$，有的教程还会添加上等式约束条件 $h(x)$。此时的约束优化问题描述如下：
$\quad min \quad f(x)$
$\quad s.t.\quad h_{j}(x)=0 \quad j=1,2,...,p$
$\quad \quad \quad g_{k}(x) \le 0 \quad k=1,2,...,q$
2 拉格朗日乘数法
在数学最优问题中，拉格朗日乘数法是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有 $n$ 个变量与 $k$ 个约束条件的最优化问题转换为一个有 $n + k$ 个变量的方程组的极值问题，其变量不受任何约束。
2.1 一个等式约束条件下
$\quad min \quad f(x，y)$
$\quad s.t. \quad \varphi (x,y)=0$
设给定二元函数 $z=f(x,y)$ 和附加条件 $\varphi (x,y)=0$，为寻找 $z=f(x,y)$ 在附加条件下的极值点，先做拉格朗日函数$F(x,y,\lambda ) =f(x,y)+\lambda \varphi (x,y)$ ，其中$\lambda$为参数。
令 $F(x,y,\lambda )$ 对 $x$ 和 $y$ 和 $\lambda$ 的一阶偏导数等于零，即
$F^{‘}_x =f^{‘}_x(x,y) +\lambda \varphi ^{‘}_x(x,y)=0$
$F^{‘}_y =f^{‘}_y(x,y) +\lambda \varphi ^{‘}_y(x,y)=0$
$F^{‘}_\lambda = \varphi(x,y)=0$
由上述方程组解出 $x,y$ 及 $\lambda$，如此求得的 $(x,y)$，就是函数 $z=f(x,y)$ 在附加条件 $ \varphi(x,y)=0$ 下的可能极值点。
几何意义
设给定目标函数为 $f(x,y)$ ，约束条件为 $\varphi(x,y)=0$ 。
如图所示，曲线 $L$ 为约束条件 $\varphi(x,y)=0$，$f(x,y)=C$ 为目标函数的等值线族。
在 $f(x,y)$ 、$\varphi(x,y)$ 偏导数都连续的条件下，目标函数 $f(x,y)$ 在约束条件 $\varphi(x,y)=0$ 下的可能极值点 $M(x_0,y_0)$，从几何上看，必是目标函数等值线曲线族中与约束条件曲线能相切的那个切点。
具体的例子
$\min f(d_1,d_2) = d_1^2 + d_2^2 - 2d_2 + 2 $
$s.t.\quad d_1^2 + d_2^2 \le 4$
1）首先写出拉格朗日函数
$g(d_1,d_2,\lambda, \eta) = f(d_1, d_2) + \lambda (d_1^2 + d_2^2 - 4 + \eta^2)$
2）$\lambda$ 是拉格朗日乘子，引入的新的 $\eta$ 是一个松弛变量，目的是为了将不等式约束经过松弛后，变为等式约束，注意 $\lambda \ge 0$。 这是不等式约束与等式约束最优化问题拉格朗日乘数法的一个重要区别。
3）然后对四个未知量分别求导，且令导函数为 $0$，有
$\begin{cases}2\eta\lambda = 0 \\d_1^2+d_2^2-4 + \eta^2 = 0\\2d_2 - 2 + 2\lambda d_2 = 0\\ 2d_1 + 2\lambda d_1 = 0\\ \lambda\ge 0\end{cases}$
4）由 $d_1 + \lambda d_1 = 0$ 知 $d_1 = 0$ ,$\eta\lambda = 0$ 情况需要分开判断，假设 $\lambda = 0$ 则 $d_2 = 1, \eta = \sqrt{3}$, 若 $\lambda > 0$ 则 $\eta =0$，求出 $\eta < 0$ 与假设矛盾。
2.2 多个等式约束条件下
$\quad min \quad f(x)$
$\quad s.t.\quad h_{k}(x)=0 \quad k=1,2,...,l$
定义拉格朗日函数 $F(x)$
$F(x,\lambda)=f(x)+\sum \limits _{k=1}^{l} \lambda_kh_k(x)$
其中 $\lambda_k$ 是各个约束条件的待定系数。
然后求解各变量的偏导方程：
$\frac{\partial F}{\partial x} ,...,\frac{\partial F}{\partial \lambda_1} ,...,\frac{\partial F}{\partial \lambda_l}$
如果有 $n$ 个变量与 $k$ 个约束条件的最优化问题，就应该有 $n+k $ 个方程。求出的方程组的解就可能是最优化值，将结果带回原方程验证就可得到解。
3 KKT条件
KKT条件有几个不同的等价表述方式，这里只讨论其中一种，其他表述可以类似地推得。给定优化问题：
$\quad min \quad f(x)$
$\quad s.t.\quad h_{j}(x)=0 \quad j=1,2,...,p$
$\quad \quad \quad g_{k}(x) \le 0 \quad k=1,2,...,q$
则我们定义不等式约束下的拉格朗日函数 $L$，则 $L$ 表达式为：
$L(x,\lambda ,\mu )=f(x)+\sum \limits _{j=1}^{p}\lambda _jh_j(x) +\sum \limits _{k=1}^{q}\mu _kg_k(x)$
其中 $f(x)$ 是原目标函数，$h_j(x)$ 是第 $j$ 个等式约束条件，$λ_j$ 是对应的约束系数，$g_k$ 是不等式约束，$u_k$ 是对应的约束系数。
此时若要求解上述优化问题，必须满足下述条件：
$\frac{\partial L}{\partial x}{\Large |} _{x=x^{*}}=0\quad \quad \quad \quad\quad\quad \quad\quad\quad\quad(1)$
$\lambda _j\ne 0 \quad \quad \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(2)$
$\mu _k\ge 0 \quad \quad \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(3)$
$\mu _k g_k(x^*)=0 \quad \quad \quad\quad\quad\quad \quad\quad\quad\quad(4)$
$h_j(x^*)=0\quad \quad j=1,2,...,p \quad \quad \quad (5)$
$g_k(x^*)\le 0\quad \quad k=1,2,...,q \quad \quad \quad (6)$
这些求解条件就是KKT条件。
- (1) 是对拉格朗日函数取极值时候带来的一个必要条件。
- (2) 等式情况：是拉格朗日系数约束，权值 $\lambda _j$ 没有要求。
- (3) 不等式约束情况：$\mu _k$非负。
- (4) 互补松弛条件：如果某个$g_k(x^*)$严格小于0，那么这个约束不会出现在加权式中，因为对应的权值$\mu _k$必须为 0。换句话说，只有 $x^*$ 恰好在边界$g_k=0$上的那些$g_k$ 的梯度才会出现在加权式中。如果去掉不等式约束的部分，那么上式就是拉格朗日乘子法的精确表述。
- (5) $h_j$原约束条件。
- (6) $g_k$原约束条件。