1带约束的优化

在最优化问题中，经常需要添加一些约束条件，此时问题表示为：

\begin{aligned} & \text{min} & & f(x) \\[0.6em] & \text{s.t.} & & h_i(x) = 0, \; i = 1, \ldots, m. \\[0.6em] & & & g_j(x) \leq 0, \; j = 1, \ldots, p. \end{aligned}

或者写成向量形式，

\begin{aligned} & \text{min} & & f(x) \\[0.6em] & \text{s.t.} & & {h}({x})=\mathbf{0} \\[0.6em] & & & {g}({x}) \leqslant \mathbf{0} \end{aligned}

其中，，，，，即个等式约束和个不等式约束。

注意，这一问题中的目标函数和约束函数是允许一般情况的，不一定是指凸函数。如果限制在凸函数，那后面处理起来会方便一些。但本文的主角 KKT 条件并不局限于凸函数。

对于一个不等式约束，如果在处，那么称该不等式约束是处的起作用约束；如果在处，那么称该约束是处的不起作用约束。

按惯例，把等式约束总是当作起作用约束。

这个问题怎么解呢？我们知道，无约束的优化问题以及带等式约束的优化问题也不是很好求的，更何况现在还多了一些不等式约束。

对于带等式约束的优化问题，我们知道有著名的拉格朗日乘子法。

2只带等式约束

为了逐步进入状态，我们先来看一下这种只带等式约束的情况。

\begin{aligned} & \text{min} & & f(x) \\[0.6em] & \text{s.t.} & & h_i(x) = 0, \; i = 1, \ldots, m. \end{aligned}

首先，构造拉格朗日函数，

\begin{aligned} L(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i h_i(x) \end{aligned}

为了求其驻点（stationary point），取各变元偏导数并置为，

\begin{aligned} \nabla L(x, \lambda) = \mathbf{0} \end{aligned}

现将和各个分开，得

\begin{aligned} \nabla f(x) + \sum_{i=1}^m \lambda_i \nabla h_i(x) = {\bf 0} \end{aligned}

\begin{aligned} \frac{\partial L(x,\lambda)}{\partial \lambda_i} = 0 \; \Rightarrow \; h_i(x) = 0 \end{aligned}

于是就得到一个方程组（线性和非线性都有可能）。然后想办法解之，得解以及的值（这里正负值都是允许的）。

需要注意的是，上面给出的只是最优值的必要条件。但这样子至少可以拿来判定有没有可能是我们要的带约束问题的极值点。

另外，如果函数和约束函数满足某些其他条件，那么上述极值条件也可以成为充要条件。

我们来总结一下上述做法的基本思路，

将一个带等式约束的优化问题转换为一个无约束的优化问题；进而得到带约束优化问题的极值点的必要条件。

为了跟后面的 KKT 条件在形式上一致，我们将上述拉格朗日乘子法的极值点必要条件罗列如下，

\begin{aligned} 1.\;\;\nabla f(x) + \sum_{i=1}^m \lambda_i \nabla h_i(x) = {\bf 0} \end{aligned}

\begin{aligned} 2.\;\;h_i(x) = 0, \quad\; i = 1, \ldots, m. \end{aligned}

.几何解释 .

上述两个条件中的第条就是约束条件，它们一般会把原函数本身在无约束条件下的极值点排除掉。

主要看第条，我们简化一下，只考虑一个约束条件，参见下图。

第个条件的意义就是说：极值点只能出现在和共线的地方。如果在某点处它俩不共线，假设上图中蓝色点附近找一个点，你就会发现：虽然点只能在红色等值线上移动，但是可以找到与梯度方向夹角大于 90 度的方向，因此函数值会变得更小，从而排除了成为极值点的可能。

第个条件也可以写为，

\nabla f(x) = - \sum_{i=1}^m \lambda_i \nabla h_i(x)

如果有多个约束条件，这相当于说函数在该点处的梯度与所有约束条件在该点处的梯度方向构成的子空间的正交补正交。或者说函数在该点处的梯度与该点处的可行方向都正交。

3KKT 条件

现在，我们来看带不等式约束的最优化问题，

\begin{aligned} & \text{min} & & f(x) \\[0.6em] & \text{s.t.} & & h_i(x) = 0, \; i = 1, \ldots, m. \\[0.6em] & & & g_j(x) \leq 0, \; j = 1, \ldots, p. \end{aligned}

多了一些不等式约束，我们还能不能使用同样的招术，将之转化为无约束优化问题呢？

先不管那么多，先撸起来再说。我们仿照拉格朗日函数，将上述问题中的函数和约束条件写成如下形式，

\mathcal{L}(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i h_i(x) + \sum_{j=1}^p \mu_j g_j(x)

同样的，为了便于描述，我们也简化一下，只考虑带一个不等式约束的情况。

\begin{aligned} & \text{min} & & f(x) \\ & \text{s.t.} & & g(x) \leq 0 \end{aligned}

此时，该问题的广义拉格朗日函数为，

\mathcal{L}(x, \mu) = f(x) + \mu g(x)

然后像上面一样，试着计算驻点，得到那部分是

\nabla f(x) + \mu \nabla g(x) = {\bf 0}

然后再求一下。

咦！等等！这不是跟上面只带等式约束时的情况一样了吗？

其实这样做是不对的。因为此时函数的最小值并不等于待求的目标函数的最小值。比如在某点处，那么我们可以任意增大的值，使得函数的值可以任意小。

虽然形式上类似，但现在这种情况与等式约束时的情况还是有所不同的。

因为此时不一定被限制在约束条件的等值面上。只要满足就够了啊，它的活动范围明显更大，因此改变值的同时使得目标函数值变小的余地就会更大。

那问题是，接下来到底怎么整？

此时想起一句俗语，用在此处或许比较恰当。正所谓，

解铃还须系铃人。

答案就在约束条件上。既然等于和小于对于的制约作用不同，那我们就分开考虑：

当时，什么情况下才可能成为目标函数在带约束下的极值点，即边界解；
当时，什么情况下才可能成为目标函数在带约束下的极值点，即内部解。

对照下图，分两种情况来解读：

.边界解 .

先看左图，当满足时，意味着在约束条件的边界上。在这种情况下，只有当和指向相反的方向时才有可能是极值点。

像等式约束时一样，两者要共线才行，要不然还有局部移动的余地使得目标函数值变得更小。但与等式约束不同的是，不光共线就行，还要反向，如果共线但同向，是成不了极小点的。例如，上左图里的红色箭头（即）如果调头跟黑色箭头（即）同向，那显然只要沿着方向走，目标函数值将变得更小。

那怎么做到要求它满足共线反向呢？

我们将等式约束中的梯度条件写为，

\nabla f(x) = - \mu \nabla g(x)

只要就可以了。

因此，第一种情况的条件为，

g(x) = 0 \quad 且 \quad \mu \ge 0

.内部解 .

现在我们考虑第二种情况，上面图片中右边的情况，当位于位置（即不是限制在约束边界上，而是在可行域内部）。

此时约束条件不起作用，约束优化问题退化为无约束优化问题。我们直接从拉格朗日函数中把它除去就行了，即令，极值条件也变为。

因此，第二种情况的条件为，

g(x) < 0 \quad 且 \quad \mu = 0

.小结 .

极值点处函数关于的梯度满足的条件可以用一个式子统一起来，即

\nabla f(x) + \mu \nabla g(x) = {\bf 0}

其实它包括了两种情况，

1、当时，

是目标函数带约束时的极值点的必要条件是，。

2、当时，

是目标函数带约束时的极值点的必要条件是，。

通过一个式子，完美地将它们整合在一起了。

.KKT 条件 .

有了上述简易情况下的图示，我们可以发挥想象，把它们整合起来得到完整的形式。

最后，对于最小化来说，所谓的 KKT 条件概括起来就是下面几条：

Stationarity

\nabla f\left(x^{{\star}}\right)+\sum_{i=1}^{m} \lambda_{i} \nabla h_{i}\left(x^{{\star}}\right)+\sum_{j=1}^{p} \mu_{j} \nabla g_{j}\left(x^{{\star}}\right)=\mathbf{0}

Primal feasibility

\begin{aligned} &h_{i}\left(x^{{\star}}\right)=0, \; i=1, \ldots, m\\[0.6em] &g_{j}\left(x^{{\star}}\right) \leq 0, \; j=1, \ldots, p \end{aligned}

Dual feasibility

\mu_{j} \geq 0, \; j=1, \ldots, p

Complementary slackness

\sum_{j=1}^{p} \mu_{j} g_{j}\left(x^{{\star}}\right) = 0 .

最后一个条件翻译过来就是互补松弛，它将我们上面讨论的两种情况囊括在一个式子里，而不需要 if else 之类的方式。另外，这一条有时也写成等价形式：

\mu_{j} g_{j}\left(x^{{\star}}\right)=0,\; j=1, \ldots, p.

严格来说，我们考虑的优化问题还需要满足一些正则条件，那么原始约束优化问题的极值点才是必须满足上述 KKT 条件。

例如，LICQ（Linear independence constraint qualification），即起作用约束（包括等式约束和不等式约束）的梯度在处线性无关。

最优化问题 KKT 条件的直观解释

1带约束的优化