拉格朗日乘子法
KKT条件（Karush–Kuhn–Tucker Conditions）
不等约束条件下的优化
如果$x^*$是不等约束条件下的一个极值点，那么有KKT条件：
- Primal Feasibility: $g(x^*) \le 0$
- Dual Feasibility: $\alpha \ge 0$
- Complementary Slackness: $\alpha g(x^*) = 0$
- Lagrangian Stationarity: $\nabla f(x^) = \alpha \times \nabla g(x^)$
我们要找的极值点必然是符合KKT条件的点($x^*$)。
KKT条件的直观理解
Lagrangian Stationarity
- 对于一个相等约束条件下的优化问题来说，极值点往往是目标函数与约束条件的切点。
- 函数梯度与函数等高线的切线是正交的。
结合上述两个事实，可知约束（$\nabla g$）的和目标函数（$\nabla f$）在极值点（切点）的梯度平行或者反向平行。即
$$ \nabla f(x^) = \alpha \times \nabla g(x^)$$
Dual Feasibility ($\alpha \ge 0$)
$\alpha$被称为KKT乘子或对偶变量。在解释为什么KKT乘子只能是非负值之前，我们先来看一看在相等约束条件下的优化问题中, KKT乘子的符号会产生什么影响。
- 如果$\alpha \ge 0$，意味着$\nabla f$和$\nabla g$的梯度方向是平行的，
- 如果$\alpha \le 0$，那么$\nabla f$和$\nabla g$的梯度方向反向平行。
那么为什么KKT条件会有这样的符号限制呢？先小小地跑一下题。
- $g(x,y) = 0(x + y - 1 = 0)$: 可行域只是一条直线
- $g(x,y) \ge 0$: 可行域是直线上方的区域
- $g(x,y) \le 0$: 可行域是直线下方的区域
约束（$\nabla g$）的梯度方向总是朝向$g(x,y) \ge 0$的可行域。
因此，只有在可行域上下翻转的情况下（$i.e.,x+y \ge -1$），KKT乘子的符号才有可能为负。这时约束不会对目标函数造成任何影响。
Complementary Slackness Condition
$$\alpha \times g(x^*) = 0$$
这个条件说明在极值点处，KKT乘子或不等约束（$g(x^*) \le 0$）为0。我们可以将任何不等约束分成两类：
- 触发约束：极值点出现在约束的区域边界，这时$g(x^*) = 0$，
- 未触发约束：极值点出现在约束的可行域中。
Primal Feasibility Condition
优化函数需要满足的条件。