KKT 条件

KKT（Karush, Kuhn, Tucker）条件是 Lagrange 条件在一般优化问题中的推广。具体的，现在我们考虑以下的优化问题：其中的所有函数均要求可微。仍记其可行集为。现在我们先考虑其与等式约束问题的关系。为此，对于任意与，我们称约束在是活跃的，当且仅当，并定义活跃集。现在考察处的情况，由于约束是有限的，我们可以找到一个的邻域使其位于所有不活跃的约束的可行域内部，因此我们可以抛开这些不活跃的约束。那么对于优化问题：同样是以下问题的极值点：而后者是等式约束问题，可以使用 Lagrange 条件刻画。以上说法是局部的，不严谨的直观，严格的叙述则在以下给出。

极值点的 KKT 条件

首先我们仍然要定义正则点这一概念。对于，我们称其正则，当且仅当线性无关。由以上的讨论，加上 Lagrange 条件，对于正则的极值点与 Lagrange 乘子就应该有：再令不活跃约束处的，就得到了：而该条件可以被进一步加强，即。这就是以下的 KKT 条件。
- 【定理 5】若是优化问题的正则极值点，则存在拉格朗日乘子使得以下的 KKT 条件成立：
  1. 驻点性。。
  2. 乘子非负性。。
  3. 互补松弛性。。
为了严格表述 KKT 的直观和证明，我们先引入一些概念。对于，称为在处的切向量，若存在可微的路径，使得，且。处的切向量的全体构成了该处的切锥，记作，其意义是“全体可行方向”。再定义法锥为张成的锥。

那么 KKT 的直观是，因为我们要考察局部的性质，所以我们要通过微分做局部的线性化。此时等式约束的可行域基本是一个超平面，而不等式约束的可行域则基本是半空间。在仅有等式约束的情况下，若干约束的可行域的交是一个子空间（切空间），其正交补为法空间，包含了极值点处的梯度；而在包含不等式约束时，若干约束的可行域的交则是一个锥（切锥），极值点处的梯度同样落在其极锥（法锥）中。

上图是一个例子，(a) 描述了三个不等式约束，其中在处是活跃的，下方的区域即为它们的可行域的交，是一个锥；而上方由张成的锥恰为切锥的法锥，应落在该法锥中。(b) 描述了一个不等式约束和一个等式约束，是唯一可行的方向，其法锥为红色区域，由张成，包含了。这暗示我们可以将一个等式约束拆分成两个不等式约束。

KKT 条件的证明

以上，驻点性和互补松弛性是自然的，主要的问题是乘子的非负性。我们先试着将原先 GEC 的证明推广到 KKT 中来。不失一般性的，现在我们只考虑不等约束。对于在处活跃的约束，应有：这就是说一定是法锥的极锥的子集。我们仍然期待这两者是相等的，因为由【引理 1】，这样便可以保证极值点处的梯度落在法锥中。但这件事不一定总是成立，考虑下例：

可以看出切锥为红线，法锥为和所在的直线，它们显然不是互为极锥的，而正则性则规避了这一情况。现在我们希望说明法锥的极锥同样是的子集，为此我们希望构造一条路径使其满足以上所述的要求，然而这却是比较繁琐的，可能需要一些高级的定理¹，因此我们先停在这里。

不妨尝试反证法。此处的直观是，假设有：使得存在某一，那么由正则性，我们取与其余梯度正交的分量。由于正交性，且应是附近使得的合法方向，我们可以直接沿用 GEC 中的构造得到一可行的路径使其从出发恰沿，并且也为下降的方向，从而导出矛盾。

现在我们将以上直观严格化。即假设存在某一使得，记，以及：由正则性，，则取与正交的分量，显然。由于，由【引理 2】，必然存在路径，使得，，且。注意到：那么在充分小时必然有，这就是说是可行的路径。由 KKT 条件：从而在充分小时必然有，产生矛盾，说明不存在。

凸优化的 KKT 条件

我们先前讨论过对于带有等式约束的凸优化问题，Lagrange 条件是充分必要的，而我们也可以期待类似的事情在带有不等式约束的凸优化上成立。具体的，我们先前已经证明了 KKT 条件是正则极值点的充分条件，现在我们可以证明凸优化问题中满足 KKT 条件的点一定是全局最优点。²

考虑任意满足 KKT 条件的点，由于是凸的，只需。我们有：考虑到所有等式约束都是仿射的，显然，从而只需：考虑到所有都是凸的，同样有：由 KKT 条件，有，从而，那么充分性得证。

Submersion Theorem，应是 Lyusternik-Graves Theorem 的特例。↩︎
我不确定凸优化中必要性部分的正则性是不是必须的，这里我们暂且认为是必须的。而由以下的证明可以看出，充分性其实并不要求正则性。↩︎

不等式约束优化问题的KKT条件

KKT 条件

极值点的 KKT 条件

KKT 条件的证明

凸优化的 KKT 条件