KKT条件

2020-05-25 | 阅读：196次

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

1. 等式约束优化问题

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

$\begin{align*} min \quad f&(x)\\ s.t. \quad g&(x)=0\end{align*}$

为方便分析，假设 $f$ 与 $g$ 是连续可导函数。我们在高等数学中学过的Lagrange乘数法是等式约束优化问题的典型解法。

定义Lagrangian函数

$L(x,\lambda) = f(x) + \lambda g(x)$

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

$\min\limits_{x,\lambda} \ L(x,\lambda)$

计算 $L$ 对 $x$ 与 $\lambda$ 的偏导数并令其为0，可得最优解的必要条件： $\nabla_{x}L = \frac{\partial L}{\partial x} = \nabla f + \lambda \nabla g = 0$

$\nabla_{\lambda}L = \frac{\partial L}{\partial \lambda} = g(x) = 0$

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

2. 不等式约束优化问题

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

$\begin{align*} min \quad f&(x)\\ s.t. \quad g&(x) \leq 0\end{align*}$

假设 $x^{\star}$ 为满足约束条件的最佳解，分开两种情况讨论：

(1) $g(x^{\star}) < 0$ , 最佳解位于可行域 $K$ 的内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)；

(2) $g(x^{\star}) = 0$ , 最佳解落在可行域 $K$ 的边界，称为边界解(boundary solution)，此时约束条件是有效的(active)。

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

(1)内部解：在约束条件无效的情形下， $g(x)=0$ 不起作用，约束优化问题退化为无约束优化问题，因此驻点 $x^{\star}$ 满足 $\nabla f=0$ 且 $\lambda=0$ 。

(2)边界解：在约束条件有效的情形下，约束不等式变成等式 $g(x)=0$ ，这与前述Lagrange乘数法的情况相同。我们可以证明驻点 $x^{\star}$ 发生于 $\nabla f \in span \nabla g$ ，换句话说，存在 $\lambda$ 使得 $\nabla f = -\lambda \nabla g$ ，但这里 $\lambda$ 的正负号是有其意义的。因为我们希望最小化 $f$ ，梯度 $\nabla f$ (函数 $f$ 在点 $x$ 的最陡上升方向)应该指向可行域 $K$ 的内部(因为最优解最小值是在边界取得的)，但 $\nabla g$ 指向 $K$ 的外部(即 $g(x) > 0$ 的区域，因为约束是小于等于0)，因此 $\lambda \ge 0$ ，称为对偶可行性(dual feasibility)。

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

$\begin{align*}\nabla_{x}L = \nabla f + \lambda \nabla g = 0 \\g(x) \leq 0 \\ \lambda \geq 0 \\ \lambda g(x) = 0 \end{align*}$

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

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

$\begin{align*}min \quad f&(x)\\s.t. \quad g_{j}&(x) = 0, j = 1,\cdots,m,\\ \quad h_{k}&(x) \leq 0, k = 1,\cdots,p.\end{align*}$

定义Lagrangian 函数

$L(x,\{\lambda_{j}\},\{\mu_{k}\}) = f(x) + \sum\limits_{j=1}^m \lambda_{j}g_{j}(x) + \sum\limits_{k=1}^p\mu_{k}h_{k}(x)$

其中 $\lambda_{j}$ 是对应 $g_{j}(x)=0$ 的Lagrange乘数， $\mu_{k}$ 是对应 $h_{k}(x) \leq 0$ 的Lagrange乘数(或称KKT乘数)。

KKT条件包括

$\begin{align*}\nabla_{x}L &= 0 \\g_{j}(x)& = 0, j=1,\cdots,m,\\h_{k}(x) &\leq 0,\\ \mu_{k} &\geq 0,\\ \mu_{k}h_{k}(x) &= 0, k=1,\cdots,p.\end{align*}$

3. 一个例子

$\begin{align*}min \quad x_1^2 + x_2^2,\\s.t. \quad x_1 + x_2 = 1 \\ \quad x_2 \leq \alpha, \end{align*}$

其中 $\left(x_{1}, x_{2}\right) \in \mathbb{R}^{2}$ ， $\alpha$ 为实数. 写出Lagrangigan函数

$L\left(x_{1}, x_{2}, \lambda, \mu\right)=x_{1}^{2}+x_{2}^{2}+\lambda\left(1-x_{1}-x_{2}\right)+\mu\left(x_{2}-\alpha\right)$

KKT方程组如下：

$\begin{aligned} \frac{\partial L}{\partial x_{i}} &=0, \quad i=1,2 \\ x_{1}+x_{2} &=1 \\ x_{2}-\alpha & \leq 0 \\ \mu & \geq 0 \\ \mu\left(x_{2}-\alpha\right) &=0 \end{aligned}$

求偏导可得 $\frac{\partial L}{\partial x_1}=2 x_1-\lambda=0$ , $\frac{\partial L}{\partial x_2}=2 x_2-\lambda+\mu=0$ , 分别解出 $x_1=\frac{\lambda}{2}$ 且 $x_2=\frac{\lambda}{2}-\frac{\mu}{2}$ . 代入约束等式 $x_1 + x_2 = 1$ , 得 $x_1=\frac{\mu}{4}+\frac{1}{2}$ , $x_2=-\frac{\mu}{4}+\frac{1}{2}$

最后再加入约束不等式， $-\frac{\mu}{4}+\frac{1}{2} \leq \alpha$ ，即 $\mu \geq 2-4 \alpha$ . 下面分三种情况讨论

(1) $\alpha > \frac{1}{2}$ : 不难验证 $\mu=0>2-4 \alpha$ 满足所有的KKT条件，约束不等式是无效的， $x_1^{\star}=x_2^{\star}=\frac{1}{2}$ 是内部解，目标函数的最小值是 $\frac{1}{2}$ .

(2) $\alpha = \frac{1}{2}$ : 如同1， $\mu=0=2-4 \alpha$ ，满足所有的KKT条件， $x_1^{\star}=x_2^{\star}=\frac{1}{2}$ 是边界解

(3) $\alpha < \frac{1}{2}$ : 这时约束不等式是有效的， $\mu=2-4 \alpha>0$ ，则 $x_1^{\star}=1-\alpha$ ， $x_2^{\star}=\alpha$ ，目标函数的极小值是 $(1-\alpha)^{2}+\alpha^{2}$ .

Te-Shi

小黑特

KKT条件

1. 等式约束优化问题

2. 不等式约束优化问题

3. 一个例子