浅谈最优化问题的KKT条件

发表: 2017-05-19 浏览: 2441

KKT 机器学习

Clipboard Image.png

最近学习了最优化理论，正好学到了机器学习中支持向量机（Support Vector Machine）和最大熵模型（Maximum Entropy Model）中用到的KKT条件（Karush–Kuhn–Tucker conditions）.

之前看了一些相关书籍，发现KKT条件的证明不是有些简略，就是太偏“数学”（对于非数学专业的学生可能看不懂）——不适合非数学专业的同学入门. 因此我通过总结教材、上课笔记和加入一些帮助理解的重要注记（个人认为不“显然”的内容），写下这篇文章，供大家学习和交流！

PS：知乎的排版有些乱，望看官们不要介意：）

0.什么是KKT条件
1.等式约束优化问题（Lagrange乘数法）
2.不等式约束优化问题
3.总结

0.什么是KKT条件

本文从本科高数（微积分）中的有条件极值的Lagrange乘数法入手，一步步推导到KKT条件. 但在讲述推导过程之前，我想先给出KKT条件：

对于具有等式和不等式约束的一般优化问题

Clipboard Image.png

KKT条件给出了判断 ${{\bf{x}}^*}$ 是否为最优解的必要条件，即：

Clipboard Image.png

1. 等式约束优化问题（Lagrange乘数法）

对于这部分内容，其实本科高数课程中已学过，因此本文直接给出结论，并补充一些我的理解与总结，它能帮助理解不等式约束中的一些内容，具体的推导过程在同济7版的高数下册（P.116-118）中已写的较详细。

所谓的等式约束优化问题是指

Clipboard Image.png

我们令 Clipboard Image.png 函数 $L(x,y)$ 称为Lagrange函数，参数 $\lambda$ 称为Lagrange乘子.再联立方程组：

得到的解为可能极值点，由于我们用的是必要条件，具体是否为极值点需根据问题本身的具体情况检验. 这个方程组称为等式约束的极值必要条件.

上式我们对 $n$ 个 $x_{i}$ 和 $l$ 个 $\lambda _{k}$ 分别求偏导，回想一下在无约束优化问题 $f(x_{1}, x_{2},...,x_{n} )=0$ 中，我们根据极值的必要条件，分别令 $\frac{\partial f}{\partial x_{i} } =0$ ，求出可能的极值点. 因此可以联想到：等式约束下的Lagrange乘数法引入了 $l$ 个Lagrange乘子，或许我们可以把 $\lambda _{k}$ 也看作优化变量（ $x_{i}$ 就叫做优化变量）. 相当于将优化变量个数增加到 $(n+l)$ 个， $x_{i}$ 与 $\lambda _{k}$ 一视同仁，均为优化变量，均对它们求偏导.

2. 不等式约束优化问题

以上我们讨论了等式约束的情形，接下来我们来介绍不等式约束的优化问题.我们先给出其主要思想：转化的思想——将不等式约束条件变成等式约束条件.具体做法：引入松弛变量.松弛变量也是优化变量，也需要一视同仁求偏导.

Clipboard Image.png

具体而言，我们先看一个一元函数的例子：

Clipboard Image.png

（注：优化问题中，我们必须求得一个确定的值，因此不妨令所有的不等式均取到等号，即 $\leq$ 的情况.）

对于约束 $g_{1}$ 和 $g_{2}$ ，我们分别引入两个松弛变量 $a_{1}^{2}$ 和 $b_{1}^{2}$ ，得到 $h_{1} (x,a_{1} )=g_{1} +a_{1}^{2} =0$ 和 $h_{2} (x,b_{1} )=g_{2} +b_{1}^{2} =0$ .注意，这里直接加上平方项 $a_{1}^{2}$ 、 $b_{1}^{2}$ 而非 $a_{1}$ 、 $b_{1}$ ，是因为 $g_{1}$ 和 $g_{2}$ 这两个不等式的左边必须加上一个正数才能使不等式变为等式.若只加上 $a_{1}$ 和 $b_{1}$ ，又会引入新的约束 $a_{1} \geq 0$ 和 $b_{1} \geq 0$ ，这不符合我们的意愿.

Clipboard Image.png

由此我们将不等式约束转化为了等式约束，并得到Lagrange函数

Clipboard Image.png

我们再按照等式约束优化问题（极值必要条件）对其求解，联立方程

Clipboard Image.png

（注：这里的 $\mu _{1} \geq 0$ ， $\mu _{2} \geq 0$ 先承认，我们待会再解释！（先上车再买票，手动斜眼）实际上对于不等式约束前的乘子，我们要求其大于等于0）

得出方程组后，便开始动手解它. 看到第3行的两式 $\mu _{1} a_{1} =0$ 和 $\mu _{1} a_{1} =0$ 比较简单，我们就从它们入手吧~

对于 $\mu _{1} a_{1} =0$ ，我们有两种情况：

情形1： $\mu _{1} =0,a_{1} \ne 0$

此时由于乘子 $\mu _{1} =0$ ，因此 $g_{1}$ 与其相乘为零，可以理解为约束 $g_{1}$ 不起作用，且有 $g_{1}(x) =a-x< 0$ .

情形2： $\mu _{1} \geq 0,a_{1} =0$

此时 $g_{1}(x) =a-x= 0$ 且 $\mu _{1} > 0$ ，可以理解为约束 $g_{1}$ 起作用，且有 $g_{1}(x)=0$ .

合并情形1和情形2得： $\mu _{1}g_{1}=0$ ，且在约束起作用时 $\mu _{1} > 0$ ， $g_{1}(x)=0$ ；约束不起作用时 $\mu _{1}=0$ ， $g_{1}(x)<0$ .

同样地，分析 $\mu _{2}b_{1}=0$ ，可得出约束 $g_{2}$ 起作用和不起作用的情形，并分析得到 $\mu _{2}g_{2}=0$ .

由此，方程组（极值必要条件）转化为

Clipboard Image.png

这是一元一次的情形.类似地，对于多元多次不等式约束问题

Clipboard Image.png

注意到梯度为向量. 上式表示在约束极小值点 ${{\bf{x}}^*}$ 处，函数 $f\left( {{{\bf{x}}^*}} \right)$ 的负梯度一定可以表示成：所有起作用约束在该点的梯度（等值线的法向量）的线性组合.（复习课本中梯度的性质：某点梯度的方向就是函数等值线 $f({\bf{x}}) = C$ 在这点的法线方向，等值线就是地理的等高线）

为方便作图，假设现在只有两个起作用约束，我们作出图形如下图.注意我们上面推导过，约束起作用时 ${g_j}\left( {\bf{x}} \right) = 0$ ，所以此时约束在几何上应该是一簇约束平面.我们假设在 ${{\bf{x}}^*}$ 取得极小值点，若同时满足 ${g_1}\left( {\bf{x}} \right) = 0$ 和 ${g_2}\left( {\bf{x}} \right) = 0$ ，则 ${{\bf{x}}^k}$ 一定在这两个平面的交线上，且 $- \nabla f\left( {{{\bf{x}}^*}} \right) = \sum\limits_{j \in J} {{\mu _j}\nabla {g_j}\left( {{{\bf{x}}^*}} \right)}$ ，即 $- \nabla f\left( {{{\bf{x}}^k}} \right)$ 、 $\nabla {g_1}\left( {{{\bf{x}}^k}} \right)$ 和 $\nabla {g_2}\left( {{{\bf{x}}^k}} \right)$ 共面.

Clipboard Image.png

下图是在点 ${{\bf{x}}^k}$ 处沿 $x_{1}Ox_{2}$ 面的截面，过点 ${{\bf{x}}^k}$ 作目标函数的负梯度 $- \nabla f\left( {{{\bf{x}}^k}} \right)$ ，它垂直于目标函数的等值线 $f({\bf{x}}) = C$ （高数课本：一点的梯度与等值线相互垂直），且指向目标函数 $f({\bf{x}})$ 的最速减小方向.再作约束函数 ${g_1}\left( {\bf{x}} \right) = 0$ 和 ${g_2}\left( {\bf{x}} \right) = 0$ 的梯度 $\nabla {g_1}\left( {{{\bf{x}}^k}} \right)$ 和 $\nabla {g_2}\left( {{{\bf{x}}^k}} \right)$ ，它们分别垂直 ${g_1}\left( {\bf{x}} \right) = 0$ 和 ${g_2}\left( {\bf{x}} \right) = 0$ 两曲面在 ${{\bf{x}}^k}$ 的切平面，并形成一个锥形夹角区域.此时，可能有a、b两种情形：

Clipboard Image.png

我们先来看情形b：若3个向量的位置关系如b所示，即 $- \nabla f$ 落在 $\nabla {g_1}$ 和 $\nabla {g_2}$ 所形成的锥角区外的一侧. 此时，作等值面 $f({\bf{x}}) = C$ 在点 ${{\bf{x}}^k}$ 的切平面（它与 $- \nabla f\left( {{{\bf{x}}^k}} \right)$ 垂直），我们发现：沿着与负梯度 $- \nabla f$ 成锐角的方向移动（如下图红色箭头方向），只要在红色区域取值，目标函数 $f({\bf{x}})$ 总能减小.而红色区域是可行域（ $f({\bf{x}}) = C$ ，C取不同的常数能得到不同的等值线，因此能取到红色区域），因此既可减小目标函数值，又不破坏约束条件. 这说明 ${{\bf{x}}^k}$ 仍可沿约束曲面移动而不破坏约束条件，且目标函数值还能够减小.所以 ${{\bf{x}}^k}$ 不是稳定的最优点，即不是局部极值点.