《SVM笔记系列之三》拉格朗日乘数法和KKT条件的直观解释-电源网

本文转自徐飞翔的“《SVM笔记系列之三》拉格朗日乘数法和KKT条件的直观解释”

版权声明：本文为博主原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。

最优化问题

我们在高中，包括在高数中都会经常遇到求解一个函数的最小值，最大值之类的问题，这类问题就是属于最优化问题。比如给出下列一个不带有约束的最优化问题：

其中的我们称为目标函数(objective function)。这样的问题，直接利用**罗尔定理（Rolle’s theorem）**求出其鞍点，又因为其为凸函数而且可行域是整个，求出的鞍点便是最值点，这个是对于无约束最优化问题的解题套路。如果问题带有约束条件，那么就变得不一样了，如：

因为此时的约束条件是仿射函数（affine function）1，所以可以利用换元法将X表示为Y的函数，从而将目标函数变为无约束的形式，然后利用罗尔定理便可以求出最值点了。然而如果约束条件一般化为，那么X就不一定可以用其他变量表示出来了，这个时候就要利用拉格朗日乘数法(Lagrange multipliers ) 了。

拉格朗日乘数法(Lagrange multipliers)我们先一般化一个二元最优化问题为( 2.1 ) 形式：

将目标函数和等式约束条件画出来就如下图所示：

其中的虚线为等高线，而红线为这个约束函数曲线与的交点的连线在平面映射。其中，假设有，点为最小值点（最优值点）。从直观上可以发现，在与的非最优化交点A,B,C,D上，其和的法线方向并不是共线的，注意，这个相当关键，因为如果不是共线的，说明与的交点中，还存在可以取得更小值的点存在。对于A点来说，B点就是更为小的存在。因此，我们从直觉上推论出只有当与的法线共线时，才是最小值点的候选点（鞍点）。推论到多元变量的问题的时候，法线便用梯度表示。于是，我们有原问题取得最优值的必要条件：

(2.2)其中的 $\lambda$ 表示两个梯度共线。可以简单的变形为：

让我们去掉梯度算子，得出

这个时候 $\lambda$ 取个负号也是不影响的，所以式子(2.4)通常写作：

看！我们得出了我们高数中经常见到的等式约束下的拉格朗日乘数函数的表示方法。

多约束的拉格朗日乘数法

以上，我们讨论的都是单约束的拉格朗日乘数法，当存在多个等式约束时（其实不等式约束也是一样的），我们进行一些推广。先一般化一个二元多约束最小化问题：

对于每个目标函数和约束配对，我们有:

将上式相加有：

定义多约束的拉格朗日函数为：

因为λ $\lambda_i$ 是常数，表示共线的含义而已，所以乘上一个常数 $\frac{1}{N}$ 也不会有任何影响，我们仍然用 $\lambda_i$ 表示，因此式子( 2.8 ) 变成：

这就是多约束拉格朗日乘数法的函数表达形式。

一个计算例子

让我们举一个单约束的拉格朗日乘数法的计算例子，例子来源于引用3。给出一个最大化任务：

图像如：

只有一个约束，使用一个乘子 $\lambda$ ，有拉格朗日函数：

按照条件求解候选点：

有

根据式子( i ) ( i i ) ( i i i ) ，解得有：

代入f ( x , y )，得到：2， -2， 0，也就是我们需要求得的最大值，最小值。可以从图中看出，我们观察到其等高线与约束投影线的确是相切的。

广义拉格朗日乘数法(Generalized Lagrange multipliers)上面我们的拉格朗日乘数法解决了等式约束的最优化问题，但是在存在不等式约束的最优化问题（包括我们SVM中需要求解的最优化问题）上，普通的拉格朗日乘数法并不能解决，因此学者提出了广义拉格朗日乘数法（Generalized Lagrange multipliers），用于解决含有不等式约束的最优化问题。这一章，我们谈一谈广义拉格朗日乘数法。

首先，我们先一般化我们的问题，规定一个二元标准的带有不等式约束的最小化问题(当然可以推广到多元的问题)，如：

类似于拉格朗日乘数法，参照式子( 2.9 ) ，我们使用 $\alpha_i$ 和 $\beta_i$ 作为等式约束和不等式约束的拉格朗日乘子，得出下式：

KKT条件（Karush–Kuhn–Tucker conditions）指出，当满足以下几个条件的时候，其解是问题最优解的候选解(摘自wikipedia)。

Stationarity

对于最小化问题就是：

对于最大化问题就是：

Primal feasibility

Dual feasibility

Complementary slackness

其中的第一个条件和我们的拉格朗日乘数法的含义是相同的，就是梯度共线的意思；而第二个条件就是主要约束条件，自然是需要满足的；有趣的和值得注意的是第三个和第四个条件，接下来我们探讨下这两个条件，以及为什么不等式约束会多出这两个条件。

为了接下来的讨论方便，我们将N设为3，并且去掉等式约束，这样我们的最小化问题的广义拉格朗日函数就变成了：

绘制出来的示意图如下所示：

其中，而蓝线为最优化寻路过程。

让我们仔细观察式子( 3.7 )和( 3.8 )，我们不难发现，因为 $a_i \geq 0$ 而 $g_i(x, y) \leq 0$ ，并且需要满足，所以和之中必有一个为0，那为什么会这样呢？

我们从上面的示意图入手理解并且记好公式( 3.3 )。让我们假设初始化一个点A，这个点A明显不处于最优点，也不在可行域内，可知违背了( 3.5 ) ，为了满足约束( 3.8 ) ，有，导致 $a_2 \nabla g_2(x,y)=0$ ，而对于，因为满足约束条件而且 $g_1(x,y) \neq 0, g_3(x,y) \neq 0$ ，所以 $a_1 = 0, \alpha_3 = 0$ 。这样我们的式子( 3.3 )就只剩下 $\nabla f(x,y)$ ，因此对着 $\nabla f(x,y)$ 进行优化，也就是沿着梯度方向下降即可，不需考虑其他的条件（因为还完全处于可行域之外）。因此，A点一直走啊走，从A到B，从B到C，从C到D，这个时候因为D点满足，因此，所以 $\nabla g_2(x,y) \neq 0$ ，因此( 3.3 ) 就变成了 $\nabla f(x,y)+\alpha_2\nabla g_2(x,y)$ 所以在优化下一个点E的时候，就会考虑到需要满足约束 $g_2(x,y) \leq 0$ 的条件，朝着向减小，而且减小的方向优化。因此下一个优化点就变成了E点，而不是G点。因此没有约束的情况下其优化路径可能是 $A \rightarrow B \rightarrow C \rightarrow D \rightarrow G \rightarrow H$ ，而添加了约束之后，其路径变成了 $A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F$ 。