KKT conditions

1. KKT 最优化条件简介
2. KKT 最优化条件（拉格朗日乘数法的推广）
3. 实例：求不等式约束条件下函数的最小值
4. 从局部最优解到全局最优解（凸优化）

1. KKT 最优化条件简介

拉格朗日乘数法，可以解决带有约束条件的极值问题，但要求约束条件都是“等式”。现实生活中会遇到约束条件为“不等式”的情况。KKT 最优化条件可以解决约束条件含有“不等式”的情况，可以看作是拉格朗日乘数法的推广。

KKT(Karush-Kuhn-Tucker) 名字来源于三个人名的缩写：不等式约束问题的必要和充分条件初见于卡罗需（William Karush）的博士论文，在一份由 W.库恩（Harold W. Kuhn）及塔克（Albert W. Tucker）撰写的研讨生论文出现后才受到重视。

2. KKT 最优化条件（拉格朗日乘数法的推广）

这里讨论的优化问题一般可表述为：求满足条件 $g_{i} (x) \leq 0, \forall i = 1, \dots, m$ 和 $h_{j} (x) = 0, \forall j = 1, \dots, n$ 时函数 $f (x)$ 的极小值。这个条件约束问题可记为下面形式：
$\begin{aligned} \underset{x}{minimize} & f (x) \\ subject to & g_{i} (x) \leq 0, i = 1, 2, \dots, m \\ h_{j} (x) = 0, j = 1, 2, \dots, n \end{aligned}$

其中 $x$ 是一个向量，可表示任意多个变量。 $f$ 是目标函数或代价函数， $g_{i}$ 是不等式约束条件（共 $m$ 个）， $h_{j}$ 是等式约束条件（共 $n$ 个）。

KKT 最优化条件(KKT conditions)是指，目标函数可能的极小值点满足：
${\begin{cases} \nabla f (x) + \sum_{i = 1}^{m} μ_{i} \nabla g_{i} (x) + \sum_{j = 1}^{n} λ_{j} \nabla h_{j} (x) = 0 \\ g_{i} (x) \leq 0, \forall i = 1, \dots, m \\ h_{j} (x) = 0, \forall j = 1, \dots, n \\ μ_{i} \geq 0, \forall i = 1, \dots, m \\ μ_{i} g_{i} (x) = 0, \forall j = 1, \dots, m \end{cases}$

在上面的方程组中，如果没有“不等式”约束条件，即 $m = 0$ ，则 KKT 最优化条件就是拉格朗日乘数法中极值点满足的方程组：
${\begin{cases} \nabla f (x) + \sum_{j = 1}^{n} λ_{j} \nabla h_{j} (x) = 0 \\ h_{j} (x) = 0, \forall j = 1, \dots, n \end{cases}$
所以 KKT 最优化条件是拉格朗日乘数法的推广，拉格朗日乘数法是 KKT 最优化条件的特例。

KKT 条件中的第一个条件和拉格朗日乘数法中的条件是一样的；第二、三个条件是显而易见的，因为它们就是题设的约束条件；第四个条件称为 Dual Feasibility Condition；最后一个条件称为互补松弛条件(Complementary Slackness Condition)。

特别注意： 和拉格朗日乘数法类似，KKT 最优化条件只是必要条件。也就是最优解一定满足 KKT 条件，但满足 KKT 条件的解不一定是最优解。 我们往往根据具体问题的性质来判断找到的是不是最优解。

2.1. 如何理解“互补松弛条件”

KKT 条件中的互补松弛条件为：
$μ_{i} g_{i} (x) = 0, \forall j = 1, \dots, m$

“互补松弛”的字面含义是：
对 $g_{i} (x)$ 的限制不严格时，对 $μ_{i}$ 的限制就很严格。即当 $g_{i} (x)$ 没有特别限定，只需满足题设的约束条件（ $g_{i} (x) < 0$ ）时， $μ_{i} = 0$ ；
对 $g_{i} (x)$ 的限制很严格时，对 $μ_{i}$ 的限制就不严格。即当 $g_{i} (x) = 0$ 时，对 $μ_{i}$ 没有特别限制。

怎么形象地理解它呢？参见图 1 。

Figure 1: KKT 的互补松弛条件（摘自 KKT Wikipedia）

图 1 中闭合的一层层圆环是目标函数 $f (x)$ 对应的等高线图， $x^{*}$ 是极值点。左子图中，极值点在 $g_{i}$ 内部取得（限制不严格），对应的 KKT 乘数 $μ_{i}$ 应该为 0（这种情况下我们不需要关心 $g_{i}$ 的具体表达式）；右子图中，极值点在 $g_{i}$ 边界处取得（限制很严格），对应的 KKT 乘数 $μ_{i}$ 无特别要求。

参考：
Karush-Kuhn-Tucker (KKT) conditions
Lagrange multiplier 的 Wikipedia 有目标函数的等高线图的简单例子。

2.2. 用 KKT 最优化条件求极大值

一般在描述最优化问题时，我们习惯于讨论极小值。极大值问题可以方便地转换为极小值问题。

如何求解最大值的最优化问题：
$\begin{aligned} maximize & f (x) \\ subject to & g_{i} (x) \leq 0, i = 1, 2, \dots, m \\ h_{j} (x) = 0, j = 1, 2, \dots, n \end{aligned}$

显然，这个问题可以方便地转换为前面介绍过的最小值的最优化问题：
$\begin{aligned} minimize & - f (x) \\ subject to & g_{i} (x) \leq 0, i = 1, 2, \dots, m \\ h_{j} (x) = 0, j = 1, 2, \dots, n \end{aligned}$

此时，对应的 KKT 最优化条件为：
${\begin{cases} \nabla f (x) - \sum_{i = 1}^{m} μ_{i} \nabla g_{i} (x) + \sum_{j = 1}^{n} λ_{j} \nabla h_{j} (x) = 0 \\ g_{i} (x) \leq 0, \forall i = 1, \dots, m \\ h_{j} (x) = 0, \forall j = 1, \dots, n \\ μ_{i} \geq 0, \forall i = 1, \dots, m \\ μ_{i} g_{i} (x) = 0, \forall j = 1, \dots, m \end{cases}$

2.3. 一般仅用 KKT 最优化条件来验证找到的解

The KKT conditions are usually not solved directly in the analysis of practical large nonlinear programming problems by software packages. Iterative successive approximation methods are most often used. The results, however they are obtained, must satisfy these conditions.

摘自：http://ocw.mit.edu/courses/mechanical-engineering/2-854-introduction-to-manufacturing-systems-fall-2010/lecture-notes/MIT2_854F10_kkt_ex.pdf

3. 实例：求不等式约束条件下函数的最小值

求解下面优化问题：
$\begin{aligned} \underset{x, y}{minimize} & f (x, y) = x^{2} + 2 y^{2} \\ subject to & x + y \geq 3 \\ y - x^{2} \geq 1 \end{aligned}$

解：两个“不等式”约束条件为： $g_{1} (x, y) = - x - y + 3 \leq 0, g_{2} (x, y) = x^{2} - y + 1 \leq 0$ ，拉格朗日函数为： $L (x, y) = x^{2} + 2 y^{2} + λ_{1} (- x - y + 3) + λ_{2} (x^{2} - y + 1)$ ，所以 KKT 条件为：
${\begin{cases} \frac{\partial L}{\partial x} = 2 x - λ_{1} + 2 λ_{2} x = 0 \\ \frac{\partial L}{\partial y} = 4 y - λ_{1} - λ_{2} = 0 \\ - x - y + 3 \leq 0 \\ x^{2} - y + 1 \leq 0 \\ λ_{1} \geq 0 \\ λ_{2} \geq 0 \\ λ_{1} (- x - y + 3) = 0 \\ λ_{2} (x^{2} - y + 1) = 0 \end{cases}$

情况 1：假设 $λ_{1} = λ_{2} = 0$ ，则由第 1，2 式得 $x = 0$ 和 $y = 0$ ，但这和第 3，4 式矛盾。
情况 2：假设 $λ_{1} > 0, λ_{2} = 0$ ，则由 ${\begin{cases} 2 x - λ_{1} = 0 \\ 4 y - λ_{1} = 0 \\ λ_{1} (- x - y + 3) = 0 \end{cases}$ 得 $x = 2, y = 1$ ，但这和 $x^{2} - y + 1 \leq 0$ 矛盾。
情况 3：假设 $λ_{1} = 0, λ_{2} > 0$ ，则由 ${\begin{cases} 2 x + 2 λ_{2} x = 0 \\ 4 y - λ_{2} = 0 \end{cases}$ 得 $x = 0, y = 1$ ，但这和 $- x - y + 3 \leq 0$ 矛盾。
情况 4：假设 $λ_{1} > 0, λ_{2} > 0$ ，则由 ${\begin{cases} - x - y + 3 = 0 \\ x^{2} - y + 1 = 0 \end{cases}$ 得 $x = - 2, y = 5$ 或者 $x = 1, y = 2$ 。先考虑 $x = - 2, y = 5$ ，这时第 1 式变为 $- 4 - λ_{1} - 4 λ_{2} = 0$ ，而 $λ_{1}$ 和 $λ_{2}$ 都是负数，显然不可能有解。再考虑 $x = 1, y = 2$ ，这时由第 1，2 式可以得到 $λ_{1} = 6, λ_{2} = 2$ 。
至此，我们找到一个满足 KKT 所有条件的唯一解： $x = 1, y = 2$ ，而原问题的最小值显然一定存在，所以解 $x = 1, y = 2$ 就是问题的解。

参考：
Optimization models and applications: http://myweb.clemson.edu/~pbelott/bulk/teaching/lehigh/ie426-f09/lecture20.pdf

4. 从局部最优解到全局最优解（凸优化）

拉格朗日乘数法和 KKT 最优化条件找到的解都只是问题的“可能局部最优解”。
凸优化(Convex optimization)中有一个重要性质——局部最优解就是全局最优解。 当然，凸优化要求函数 $f$ 为凸函数，而拉格朗日乘数法和KKT最优化条件并没有这个要求。