LittleBlackTe

A good man is seldom uneasy.

KKT条件

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*}

为方便分析,假设fg是连续可导函数。Lagrange乘数法是等式约束优化问题的典型解法。

定义Lagrangian函数

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

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

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

计算Lx\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 pointx^{\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*}

约束不等式g(x) \leq 0称为原始可行性(primal feasibility),据此我们定义可行域(feasible region) K = \{x \in \mathbb{R}^n|g(x)\leq 0\}。假设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*}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注