Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及等式的约束优化问题推广至不等式。在实际应用上，KKT条件(方程组)一般不存在代数解，许多优化算法可供数值计算选用。这篇短文从Lagrange乘数法推导KKT条件并举一个简单的例子说明解法。

文章结构如下：

1： 等式约束优化问题

2： 不等式约束优化问题

3： 一个例子

---

1： 等式约束优化问题

给定一个目标函数 f:Rn→R ，我们希望找到 x∈Rn ，在满足约束条件 g(x)=0 的前提下，使得 f(x) 有最小值。这个约束优化问题记为：

为方便分析，假设 f 与 g 是连续可导函数。Lagrange乘数法是等式约束优化问题的典型解法。定义Lagrangian函数：

其中 λ 称为Lagrange乘数。Lagrange乘数法将原本的约束优化问题转换成等价的无约束优化问题

计算 L 对 x 与 λ 的偏导数并设为零，可得最优解的必要条件：

其中第一式为定常方程式(stationary equation)，第二式为约束条件。解开上面 n+1 个方程式可得 L(x,λ) 的stationary point x* 以及 λ 的值(正负数皆可能)。

 

2： 不等式约束优化问题

接下来我们将约束等式 g(x)=0 推广为不等式 g(x)≤0 。考虑这个问题

约束不等式 g(x)≤0 称为原始可行性(primal feasibility)，据此我们定义可行域(feasible region) K=x∈Rⁿ|g(x)≤0 。假设 x* 为满足约束条件的最佳解，分开两种情况讨论：

(1) g(x*)<0 ，最佳解位于 K 的内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)；

(2) g(x*)=0 ，最佳解落在 K 的边界，称为边界解(boundary solution)，此时约束条件是有效的(active)。

这两种情况的最佳解具有不同的必要条件。

(1)内部解：在约束条件无效的情形下， g(x) 不起作用，约束优化问题退化为无约束优化问题，因此驻点 x* 满足 ∇f=0 且 λ=0 。

(2)边界解：在约束条件有效的情形下，约束不等式变成等式 g(x)=0 ，这与前述Lagrange乘数法的情况相同。我们可以证明驻点 x* 发生于 ∇f∈span∇g ，换句话说，存在 λ 使得 ∇f=−λ∇g ，但这里 λ 的正负号是有其意义的。

因为我们希望最小化 f ，梯度 ∇f (函数 f 在点 x 的最陡上升方向)应该指向可行域 K 的内部(因为你的最优解最小值是在边界取得的)，但 ∇g 指向 K 的外部(即 g(x)>0 的区域，因为你的约束是小于等于0)，因此 λ≥0 ，称为对偶可行性(dual feasibility)。

因此，不论是内部解或边界解， λg(x)=0 恒成立，称为互补松弛性(complementary slackness)。整合上述两种情况，最佳解的必要条件包括Lagrangian函数 L(x,λ) 的定常方程式、原始可行性、对偶可行性，以及互补松弛性：

这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化 f(x) 且受限于 g(x)≤0 ，那么对偶可行性要改成 λ≤0 。

上面结果可推广至多个约束等式与约束不等式的情况。考虑标准约束优化问题(或称非线性规划)：

定义Lagrangian 函数

其中 λ_j 是对应 g_j(x)=0 的Lagrange乘数， μ_k是对应 h_k(x)≤0 的Lagrange乘数(或称KKT乘数)。KKT条件包括

在使用KKT条件时需要满足Regularity conditions (or constraint qualifications)，维基在第三部分有了介绍：Karush-Kuhn-Tucker conditions 。比较常见的是Linearity constraint qualification (LCQ)，即约束条件是仿射函数。

 

3： 一个例子

考虑这个问题

其中 ，(x₁,x₂)∈R²，α 为实数。写出Lagrangigan函数

KKT 方程组如下：

求偏导可得：

 

最后再加入约束不等式 −μ/4+1/2≤α 或 μ≥2−4α 。底下分开三种情况讨论。

(1) α>1/2 ：不难验证 μ=0>2−4α 满足所有的KKT条件，约束不等式是无效的， x₁*=x₂*=1/2 是内部解，目标函数的极小值是 1/2 。

(2) α=1/2 ：如同1， μ=0=2−4α 满足所有的KKT条件， x₁*=x₂*=1/2 是边界解，因为 x₂*=α 。

(3) α<1/2 ：这时约束不等式是有效的， μ=2−4α>0 ，则 x₁*=1−α 且 x₂*=α ，目标函数的极小值是 (1−α)²+α² 。

 

4： 参考文献

周志成：《线性代数》，国立交通大学出版社

 

---

文章转载自知乎  作者：Eureka 

原文链接：https://zhuanlan.zhihu.com/p/38163970

Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及等式的约束优化问题推广至不等式。在实际应用上，KKT条件(方程组)一般不存在代数解，许多优化算法可供数值计算选用。这篇短文从Lagrange乘数法推导KKT条件并举一个简单的例子说明解法。

文章结构如下：

1： 等式约束优化问题

2： 不等式约束优化问题

3： 一个例子

---

1： 等式约束优化问题

给定一个目标函数 f:Rn→R ，我们希望找到 x∈Rn ，在满足约束条件 g(x)=0 的前提下，使得 f(x) 有最小值。这个约束优化问题记为：

为方便分析，假设 f 与 g 是连续可导函数。Lagrange乘数法是等式约束优化问题的典型解法。定义Lagrangian函数：

其中 λ 称为Lagrange乘数。Lagrange乘数法将原本的约束优化问题转换成等价的无约束优化问题

计算 L 对 x 与 λ 的偏导数并设为零，可得最优解的必要条件：

其中第一式为定常方程式(stationary equation)，第二式为约束条件。解开上面 n+1 个方程式可得 L(x,λ) 的stationary point x* 以及 λ 的值(正负数皆可能)。

 

2： 不等式约束优化问题

接下来我们将约束等式 g(x)=0 推广为不等式 g(x)≤0 。考虑这个问题

约束不等式 g(x)≤0 称为原始可行性(primal feasibility)，据此我们定义可行域(feasible region) K=x∈Rⁿ|g(x)≤0 。假设 x* 为满足约束条件的最佳解，分开两种情况讨论：

(1) g(x*)<0 ，最佳解位于 K 的内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)；

(2) g(x*)=0 ，最佳解落在 K 的边界，称为边界解(boundary solution)，此时约束条件是有效的(active)。

这两种情况的最佳解具有不同的必要条件。

(1)内部解：在约束条件无效的情形下， g(x) 不起作用，约束优化问题退化为无约束优化问题，因此驻点 x* 满足 ∇f=0 且 λ=0 。

(2)边界解：在约束条件有效的情形下，约束不等式变成等式 g(x)=0 ，这与前述Lagrange乘数法的情况相同。我们可以证明驻点 x* 发生于 ∇f∈span∇g ，换句话说，存在 λ 使得 ∇f=−λ∇g ，但这里 λ 的正负号是有其意义的。

因为我们希望最小化 f ，梯度 ∇f (函数 f 在点 x 的最陡上升方向)应该指向可行域 K 的内部(因为你的最优解最小值是在边界取得的)，但 ∇g 指向 K 的外部(即 g(x)>0 的区域，因为你的约束是小于等于0)，因此 λ≥0 ，称为对偶可行性(dual feasibility)。

因此，不论是内部解或边界解， λg(x)=0 恒成立，称为互补松弛性(complementary slackness)。整合上述两种情况，最佳解的必要条件包括Lagrangian函数 L(x,λ) 的定常方程式、原始可行性、对偶可行性，以及互补松弛性：

这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化 f(x) 且受限于 g(x)≤0 ，那么对偶可行性要改成 λ≤0 。

上面结果可推广至多个约束等式与约束不等式的情况。考虑标准约束优化问题(或称非线性规划)：

定义Lagrangian 函数

其中 λ_j 是对应 g_j(x)=0 的Lagrange乘数， μ_k是对应 h_k(x)≤0 的Lagrange乘数(或称KKT乘数)。KKT条件包括

在使用KKT条件时需要满足Regularity conditions (or constraint qualifications)，维基在第三部分有了介绍：Karush-Kuhn-Tucker conditions 。比较常见的是Linearity constraint qualification (LCQ)，即约束条件是仿射函数。

 

3： 一个例子

考虑这个问题

其中 ，(x₁,x₂)∈R²，α 为实数。写出Lagrangigan函数

KKT 方程组如下：

求偏导可得：

 

最后再加入约束不等式 −μ/4+1/2≤α 或 μ≥2−4α 。底下分开三种情况讨论。

(1) α>1/2 ：不难验证 μ=0>2−4α 满足所有的KKT条件，约束不等式是无效的， x₁*=x₂*=1/2 是内部解，目标函数的极小值是 1/2 。

(2) α=1/2 ：如同1， μ=0=2−4α 满足所有的KKT条件， x₁*=x₂*=1/2 是边界解，因为 x₂*=α 。

(3) α<1/2 ：这时约束不等式是有效的， μ=2−4α>0 ，则 x₁*=1−α 且 x₂*=α ，目标函数的极小值是 (1−α)²+α² 。

 

4： 参考文献

周志成：《线性代数》，国立交通大学出版社

 

---

文章转载自知乎  作者：Eureka 

原文链接：https://zhuanlan.zhihu.com/p/38163970