Karush-Kuhn-Tucker (KKT)条件_ZNDS问答

polly0228

专栏文章汇总

文章结构如下：
1：等式约束优化问题
2：不等式约束优化问题
3：一台例子
<hr/>

注：本文来自台湾周志成老师《线性代数》及其博客

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

给定一台目标函数 $f:\mathbb{R}^n\to\mathbb{R}$ ，我们希望找到 $\mathbf{x}\in\mathbb{R}^n$ ，在满足约束条件  的前提下，使得  有最小值。这个约束优化问题记为

$\displaystyle \begin{array}{ll} \hbox{min}&f(\mathbf{x})\\ \hbox{s.t.}&g(\mathbf{x})=0. \end{array}\\$
为省事分析，假设  与 $g$ 是连续可导函数。Lagrange乘数法是等式约束优化问题的典型解法。定义Lagrangian函数

$\displaystyle L(\mathbf{x},\lambda)=f(\mathbf{x})+\lambda g(\mathbf{x})\\$
其中  称为Lagrange乘数。Lagrange乘数法将原本的约束优化问题转换成等价的无约束优化问题

$\displaystyle \underset{\mathbf{x},\lambda}{\hbox{min}}~~L(\mathbf{x},\lambda)\\$
计算 $L$ 对  与  的偏导数并设为零，可得最优解的必要条件：

$\displaystyle \begin{aligned} \nabla_{\mathbf{x}}L&=\frac{\partial L}{\partial\mathbf{x}}=\nabla f+\lambda\nabla g=\mathbf{0}\\ \nabla_{\lambda}L&=\frac{\partial L}{\partial\lambda}=g(\mathbf{x})=0 \end{aligned}\\$
其中第一式为定常方程式(stationary equation)，第二式为约束条件。解开上面 $n+1$ 个方程式可得  的stationary point  以及  的值(正负数皆可能)。
<hr/>2：不等式约束优化问题

接下来我们将约束等式  推广为不等式  。考虑这个问题

$\displaystyle \begin{array}{ll} \hbox{min}&f(\mathbf{x})\\ \hbox{s.t.}&g(\mathbf{x})\le 0. \end{array}\\$
约束不等式  称为原始可行性(primal feasibility)，据此我们定义可行域(feasible region) $K={\mathbf{x}\in\mathbb{R}^n|g(\mathbf{x})\le 0}$ 。假设  为满足约束条件的最佳解，分开两种情况讨论：
(1) $g(\mathbf{x}^\star)<0$ ，最佳解位于  的内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)；
(2) $g(\mathbf{x}^\star)=0$ ，最佳解落在  的边界，称为边界解(boundary solution)，此时约束条件是有效的(active)。
这两种情况的最佳解具有不同的必要条件。
(1)内部解：在约束条件无效的情形下， $g(\mathbf{x})$ 不起作用，约束优化问题退化为无约束优化问题，因此驻点  满足 $\nabla f =\mathbf{0}$ 且 $\lambda=0$ 。
(2)边界解：在约束条件有效的情形下，约束不等式变成等式  ，这与前述Lagrange乘数法的情况相同。我们可以证明驻点  发生于 $\nabla f\in\hbox{span}{\nabla g}$ ，换句话说，存在  使得 $\nabla f=-\lambda\nabla g$ ，但这里  的正负号是有其意义的。因为我们希望最小化  ，梯度 $\nabla f$ (函数  在点  的最陡上升方向)应该指向可行域  的内部(因为你的最优解最小值是在边界取得的)，但 $\nabla g$ 指向  的外部(即 $g(\mathbf{x})>0$ 的区域，因为你的约束是小于等于0)，因此 $\lambda\ge 0$ ，称为对偶可行性(dual feasibility)。
因此，不论是内部解或边界解， $\lambda g(\mathbf{x})=0$ 恒成立，称为互补松弛性(complementary slackness)。整合上述两种情况，最佳解的必要条件包括Lagrangian函数  的定常方程式、原始可行性、对偶可行性，以及互补松弛性：

$\displaystyle \begin{aligned} \nabla_{\mathbf{x}}L&=\nabla f+\lambda\nabla g=\mathbf{0}\\ g(\mathbf{x})&\le 0\\ \lambda& \ge 0\\ \lambda g(\mathbf{x})&=0. \end{aligned}\\$
这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化  且受限于  ，那么对偶可行性要改成 $\lambda\le 0$ 。
上面结果可推广至多个约束等式与约束不等式的情况。考虑标准约束优化问题(或称非线性规划)：

$\displaystyle \begin{array}{lll} \hbox{min}&f(\mathbf{x})\\ \hbox{s.t.}&g_j(\mathbf{x})=0,&j=1,\ldots,m ,\\ &h_k(\mathbf{x})\le 0,&k=1,\ldots,p. \end{array}\\$
定义Lagrangian 函数

$\displaystyle L\left(\mathbf{x},\{\lambda_j\},\{\mu_k\}\right)=f(\mathbf{x})+\sum_{j=1}^m\lambda_jg_j( \mathbf{x})+\sum_{k=1}^p\mu_kh_k(\mathbf{x})\\$
其中 $\lambda_j$ 是对应 $g_j(\mathbf{x})=0$ 的Lagrange乘数， $\mu_k$ $是对应 $h_k(\mathbf{x})\le 0$ 的Lagrange乘数(或称KKT乘数)。KKT条件包括

$\displaystyle \begin{aligned} \nabla_{\mathbf{x}}L&=\mathbf{0}\\ g_j(\mathbf{x})&=0,~~j=1,\ldots,m,\\ h_k(\mathbf{x})&\le 0,\\ \mu_k&\ge 0,\\ \mu_k h_k(\mathbf{x})&=0,~~k=1,\ldots,p. \end {aligned}\\$

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

<hr/>3：一台例子

考虑这个问题

$\displaystyle \begin{array}{ll} \hbox{min}&x_1^2+x_2^2,\\ \hbox{s.t.}&x_1+x_2=1\\ &x_2\le\alpha,\end{array}\\$
其中 $(x_1,x_2)\in\mathbb{R}^2，\alpha$ 为实数。写出Lagrangigan函数

$\displaystyle L(x_1,x_2,\lambda,\mu)=x_1^2+x_2^2+\lambda(1-x_1-x_2)+\mu(x_2- \alpha)\\$
KKT 方程组如下：

$\displaystyle \begin{aligned} \frac{\partial L}{\partial x_i}&=0,~~i=1,2,\\ x_1+x_2&=1\\ x_2-\alpha&\le 0\\ \mu&\ge 0\\ \mu (x_2-\alpha)&=0. \end{aligned}\\$
求偏导可得 $\frac{\partial L}{\partial x_1}=2x_1-\lambda=0$ 且 $\frac{\partial L}{\partial x_2}=2x_2-\lambda+\mu=0$ ，分别解出 $x_1=\frac{\lambda}{2}$ 且 $x_2=\frac{\lambda}{2}-\frac{\mu}{2}$ 。代入约束等式 $x_1+x_2=\lambda-\frac{\mu}{2}=1$ 或 $\lambda=\frac{\mu}{2}+1$ 。合并上面结果，

$\displaystyle x_1=\frac{\mu}{4}+\frac{1}{2},~~~~x_2=-\frac{\mu}{4}+\frac{1}{2}\\$
最后再加入约束不等式 $-\frac{\mu}{4}+\frac{1}{2}\le\alpha$ 或 $\mu\ge 2-4\alpha$ 。底下分开三种情况讨论。
(1) $\alpha>\frac{1}{2}$ ：不难验证 $\mu=0>2-4\alpha$ 满足所有的KKT条件，约束不等式是无效的，  是内部解，目标函数的极小值是 $\frac{1}{2}$ 。
(2) $\alpha=\frac{1}{2}$ ：如同1， $\mu=0=2-4\alpha$ 满足所有的KKT条件，  是边界解，因为  。
(3) $\alpha < \frac{1}{2}$ ：这时约束不等式是有效的， $\mu=2-4\alpha>0$ ，则 $x^\star_1=1-\alpha$ 且  ，目标函数的极小值是 $(1-\alpha)^2+\alpha^2$ 。
<hr/>4：参考文献

周志成：《线性代数》，国立交通大学出版社
Karush-Kuhn-Tucker (KKT) 條件

加油，不过有一些表述不是很习惯，比如束缚不等式－>约束不等式；互补驰与狐步松弛性

诶呀尴尬了，评论的那会儿刚起床脑子不清醒是互补松弛性……

Byod的凸优化对于kkt和互补松弛条件都有详细介绍

讲的不错

没看懂……看不懂……

谢谢，已修改

哪里看不懂？可以写的在详细点

啊啊啊啊不是您写的不够详细！是我知识方面的不足！感谢作者大大的回复！！

加油，我也是在学习ing

		自动登录	找回密码
密码			立即注册

Karush-Kuhn-Tucker (KKT)条件

相关问题更多>

最新回答