KKT条件约束优化中非常关键的条件,与算法的设计与收敛性分析息息相关。
1. 拉格朗日乘子
我们以简单的一类问题做为讨论KKT条件的序言。一般来说,任何有\(n\)个元素的变量\(x=(x_{1},\ldots,x_{n})^{T}\)和\(m\)个等式约束的优化问题可以写成
接下来的讨论中,我们将假设问题中所涉及的任何函数都是可微的,并且这些结果的大多数都存在次梯度版本。
这个问题的拉格朗日松弛为:
这里的\(m\)个新的\(\lambda_{i}\)被称为拉格朗日乘子(在线性规划中,这些是对偶变量)。我们可以把这看作是消除了约束,但是给目标增加了惩罚成本。如果任一项\(g_{i}(x)\ne0\),我们就会产生一个单位的惩罚成本\(\lambda_{i}\)。如果仔细选择这个惩罚成本,松弛问题的解将与原问题的解完全相同。
1.1 推导
我们推导二维问题的拉格朗日乘子法
\(h\)是\(g\)水平集(无数条等值线)上特殊的一条曲线,即可行域。我们可以将二维平面上\(f(x,y)\)的水平集以及\(g(x,y)\)的水平集想象成参数曲线。我们的目标是在曲线\(h\)上找到到达\(f\)可能的最低水平集的点\((x,y)\).想象:沿着\(h\)走,观察\(f\)的值是如何变化的。为了使\(f\)到达最小,在这条曲线上必须有某个点,它的值暂时不会改变。这种情况的发生可能有两个原因:要么\(h\)与\(f\)的等式线相切,要么\(f\)本身变平了(梯度为0)。为了检查\(h\)是否与\(f\)的等值线相切(在\(x^*\)处),由于梯度\(\nabla_{x,y}(f)=(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y})^{T}\)与\(f\)的等值线相互正交。如果\(h\)与\(f\)的等值线相切,则意味着\(h\)的梯度应该是\(f\)的梯度的标量倍,即应该有一个常数\(\lambda\),使得
\[\nabla_{x,y}(f)=\lambda\nabla_{x,y}(g). \]这个条件对\(f\)是平坦的也成立,因为此时可以用\(\lambda=0\)。现在我们只是找到了某个点\((x,y)\)是原问题的一个最优解的必要条件
\[\nabla_{x,y}(f)=\lambda\nabla_{x,y}(g), \]且
\[h=g(x,y)=0, \]这两个条件分别是稳定性和可行性。
我们将这些合并到一个方程中,定义拉格朗日函数
求解$$\nabla_{x,y,\lambda}L(x,y,\lambda)=0,$$
这封装了我们对解的稳定性和可行性的要求。类似地,可以把这个结论推广到一般的情形。
2. KKT条件
KKT条件是拉格朗日乘子法的推广,它给出了包含等式约束和不等式约束系统的最优性的一组必要条件。假设我们有一个涉及\(m\)个等式约束,\(l\)个不等式约束的优化问题。这样的问题具有一般的形式
同样地,我们通过消除约束并且合并为每个约束添加惩罚成本来形成一个松弛问题
\[\min_{x\in\mathbb{R}^{n}}\quad f(x)+\sum_{i=1}^{m}\lambda_{i}g_{i}(x)+\sum_{j=1}^{l}\mu_{j} h_{j}(x), \]现在,每一个等式约束有一个乘子\(\lambda_{i},\), 每个不等式约束都有一个乘子\(\mu_{j}\),这些乘子被称为KKT乘子。
拉格朗日乘子法的许多推理在这里仍然适用。我们可以将上面的目标定义为拉格朗日函数\(L(x,\lambda,\mu),\)我们发现最优性的必要条件包括:\(\nabla_{x}L=0\)(稳定性),\(\nabla_{\lambda}L=0\)(等式约束的可行性);然而这里我们没有必要让\(\nabla_{\mu}L=0\),因为它为\(0\),这就强迫\(h_{j}(x)=0\),只给了我们部分解。因此,我们不能简单地说\(\nabla_{x,\lambda,\mu}L=0\),我们需要额外的信息来确定乘子组\(\mu\)的值。
注意到,在前一=节中,没有对\(\lambda\)的符号添加约束。我们将会发现,在不等式约束的情形,\(\mu\)的符号非常重要,所以要非常小心。
2.1 推导\(\mu\)
从考虑简化的二维系统开始
只涉及不等式约束。同样地,我们可以想象:\(f\)在水平面上的水平集,约束\(h(x,y)\le0\)定义了平面内的一个区域。最优解有两种可能:要么它完全位于可行域内部,此时\(h(x,y)<0\)且\(f\)处于极值;要么它位于边界上,此时\(h(x,y)=0\),且\(h(x,y)\)的边界与\(f\)的等值线相切。
如果最优解出现在\(h(x,y)<0\),则不等式约束对问题没有影响,可以忽略;否则,\(h(x,y)=0\)。在这两种情况下,对某个\(\mu\)必须满足约束\(\mu h(x,y)=0\),即要么\(h(x,y)=0\),在这种情况下,\(\mu\)的值无关紧要;要么\(h(x,y)<0\),在这种情况下,\(\mu\)必须等于\(0\),这就是互补松弛条件。
然而,我们必须考虑\(\mu\)的正负号。我们的目标是能够使用这个变量做为松弛问题的目标的一部分
和前面一样,最优性需要这个表达式在\((x,y)\)处是平稳的,如果我们有
\[\nabla_{x,y}f(x,y)+\mu\nabla_{x,y}h(x,y)=0 \]则这是正确的。把它重新排列,得到
\[\mu=-\frac{[\nabla f(x,y)]_{k}}{[\nabla h(x,y)]_{k}},k=1,2. \]回想一下,函数的梯度是目标函数值上升最快的方向。对于\(h\),由于区域的边界是由\(h(x,y)=0\)确定,而内部是由\(h(x,y)<0\)定义,这意味着我们沿着\(f\)的梯度方向向可行域内部移动时,\(h\)必须减小,即\(h\)的梯度应该指向区域外。这与梯度方向是相反的。所以\([\nabla f(x,y)]_{k}\)和$[\nabla h(x,y)]_{k},k=1,2 \(必有相反的符号。故\)\mu\(总是正的。 同时,我们还要注意到,对于\)\max f(x)$, \(f\)的梯度应该指向区域的外部,那么\(\nabla f(x,y)\)与\(\nabla h(x,y)\)有相同的方向,这将迫使\(\mu<0\)。我们把这个做为一个替代约束,但是按照惯例,我们仍然要求\(\mu>0\),并且简单地改变拉格朗日中惩罚项的符号,得到
\[\nabla_{x,y}f(x,y)-\mu\nabla_{x,y}h(x,y)=0. \]2.2 一般的结果
\[\min_{x\in\mathbb{R}^{n}}\quad f(x)\quad s.t.\quad g_{i}(x)=0, i=1,\ldots,m; h_{j}(x)\le0,j=1,\ldots,l. \]它的KKT条件是任何最优解\(x\)必须满足的一组必要条件。具体地,必须存在乘子\(\lambda=(\lambda_{1},\ldots,\lambda_{m})\)和\(\mu=(\mu_{1},\ldots,\mu_{l})\)满足下列条件;
(1) 稳定性
如果 minimization
\[\nabla_{x}f(x)+\sum_{i=1}^{m}\lambda_{i}\nabla_{x}g_{i}(x)+\sum_{j=1}^{l}\mu_{j} \nabla_{x}h_{j}(x)=0,
\]如果 maximization
\[\nabla_{x}f(x)+\sum_{i=1}^{m}\lambda_{i}\nabla_{x}g_{i}(x)-\sum_{j=1}^{l}\mu_{j} \nabla_{x}h_{j}(x)=0.
\](2)原始可行性
\[g_{i}(x)=0,i=1,\ldots,m; h_{j}(x)\le0,j=1,\ldots,l. \](3)对偶可行性
\[\mu_{j}\ge0,\quad j=1,\ldots,l \](4)互补松弛条件
\[\mu_{j}h_{j}(x)=0, \quad j=1,\ldots,l. \]注意:这并不适用于所有规划,这意味着存在某些优化问题,其中对于给定的最优解\(x\),不存在任何满足KKT条件的乘子\(\lambda\)和\(\mu\)。为了使解存在,\(f\),\(g_{i}\)和\(h_{j}\)必须满足一定的正则性条件。已知有几大类约束总是满足这些条件。
(1)如果所有的\(g_{i}\)和\(h_{j}\)都是仿射的,我们就自动有了正则性。
(2)满足Slater条件的函数,它要求是凸规划的。
(3)对于满足连续可微的正则性条件的凸规划,KKT条件是全局最优解的充分必要条件。