拉格朗日乘子法

写这篇文章的动机主要是最近正在学习机器学习的课程，学到逻辑回归的时候发现使用了拉格朗日乘子法，网上也很多文章讲拉格朗日乘子法的，因此这篇文章只是记录学习的过程，希望能较为全面地展示拉格朗日乘子法的各个方面。如果文章有错误请大家指出。也希望接下来能在学习过程中记录下机器学习中的一些知识点。

基本思想

拉格朗日乘子法想要解决的问题事实上是比较常出现的，也就是对于一个式子来说，大多数情况下我们是不可能无限制求其理想情况下的最优值的（这里的最优值可能是最大值也可能是最小值），总是存在一些约束生成了一部分可行解域，从机器学习上来说，我们的可行解域就被限制住了。但是很显然我们如果将这个视为约束条件下的最优化，直接求解起来事实上是有一定困难的，我们更希望求解的是无约束的优化问题。

作为一种优化算法，拉格朗日乘子法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题。

在转化过程中，拉格朗日乘子法通过引入k个拉格朗日乘子，将n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题。举个例子来说，会有如下转化：
minx,y,zf(x,y,z)s.t.g(x,y,z)=0min_{x,y,z} f(x,y,z)\\ s.t. \ g(x,y,z)=0 minx,y,z​f(x,y,z)s.t. g(x,y,z)=0
求解上述最优化等价于求如下无约束优化：
minx,y,z,λf(x,y,z)+λg(x,y,z)min_{x,y,z,\lambda}f(x,y,z)+\lambda g(x,y,z) minx,y,z,λ​f(x,y,z)+λg(x,y,z)
接下来对于约束条件只有等式以及约束条件中出现不等式约束的情况分别讨论。

等式约束

等式约束是拉格朗日乘子法中最简单的一种形式，为了方便画图辅助理解，假设我们有如下优化式子：
maxx,yf(x,y)s.t.g(x,y)=cmax_{x,y} f(x,y)\\ s.t. \ g(x,y)=c maxx,y​f(x,y)s.t. g(x,y)=c
我们最后会将其转化为无约束优化：
maxx,y,λf(x,y)+λ(g(x,y)−c)(1)max_{x,y,\lambda}f(x,y)+\lambda (g(x,y)-c) \tag{1} maxx,y,λ​f(x,y)+λ(g(x,y)−c)(1)
这里的$\lambda$​​是没有约束的，这是和不等式约束一个很大的区别，因此在这里进行解释为什么这样能够求出最优值点。这是在一个二维平面上的优化式子，因此可以做出如下图辅助理解：

需要注意的是上图中蓝色的虚线表示待优化原函数的等高线图，也就是说在一条蓝色虚线上的点$f(x,y)$​都是相等的，而绿色的实线其实也可以理解为$g(x,y)$​的等高线图，只不过由于约束，可行解只能落在这一条绿色的实线上。

如果结合图像来理解，对于$f(x,y)$来说，我们不妨假设其越往内的等高线表示其值越大，也就是说针对图中的值来说d2>d1d_2>d_1d2​>d1​​​，由于在某一点的梯度指向最快的上升方向，因此对图上的函数来说梯度方向都是向内的。而对于绿色的线来说由于没有前置条件，所以我们无法判断其梯度的具体方向，结合图来说，图中的绿色箭头表示约束条件函数的梯度方向，但是这个方向如果取反向事实上也是可以的。

我们猜想最优值的点就在图中的切点位置，更具体一点也就是在这一点原函数$f(x,y)$​的梯度方向和$g(x,y)$​的梯度方向相同或相反。如果不是用严格的数学定理来证明，而是从几何意义来说，$f(x,y)$​​当然希望沿着梯度方向走的越多越好，而且使用朴素的思想来说，只要在梯度方向还能运动，就说明还没到达最优值点。

而我们的可行域固定在了$g(x,y)=c$​这一条线上，不妨假设我们在这条线上移动点来求得最优值，那么如果当前点处$g(x,y)=c$​的梯度和与当前节点相交的$f(x,y)=d$​的梯度方向并不平行，那么就表示如果继续移动这个点，总存在$f(x,y)=d$​的梯度方向的一个分量使得$f(x,y)$​​的值更大，也就不符合最优值点的定义，由此可见最优值点处约束函数与待优化函数的梯度必是平行的，转化为数学的语言来说也就是：
$$\nabla f(x,y)+\lambda \nabla g(x,y)=0$$
我们发现这不就是公式(1)的梯度为0的点吗？由此可见只要求出我们转化后的梯度为0的点其实就等价于求出了最优值点。

那么看到这里可能会产生一个疑惑，上述例子中给出的是求$f(x,y)$的最大值点，那么我们求出来的梯度为0的点会不会是最小值点呢？也就是说求的极值不符合要求呢？同样是从上图来看，如果在该约束下还能求出$f(x,y)$的最小值，那么最小值点处也必是满足$\nabla f(x,y)+\lambda \nabla g(x,y)=0$​​​，由此可见拉格朗日乘子法只是极值点的一个必要条件，但是保证不了求出的是不是我们要求的那一个极值点（也就是说不能保证我们目标是max，求出的会不会是min），因此求出的结果还需要自行根据实际情况判断。

不等式约束、KKT条件

在真实情况下约束条件大多是有不等式约束也有等式约束，因此这一小节主要介绍不等式约束条件下的拉格朗日乘子法以及这一部分很重要的一个KKT条件，这一条件在SVM的对偶问题转换中起到重要作用。

这里我们先单独考虑只有不等式的约束条件，如果约束中还有考虑约束条件下的优化如下：
minx,yf(x,y)s.t.g(x,y)<0min_{x,y} f(x,y)\\ s.t. \ g(x,y)<0 minx,y​f(x,y)s.t. g(x,y)<0
先给出结论，这一优化问题转化为无约束优化如下：
minx,y,λf(x,y)+αg(x,y)s.t.α>=0(2)min_{x,y,\lambda}f(x,y)+\alpha g(x,y) \tag{2}\\ \ \ \ \ \ s.t.\ \ \ \alpha>=0 minx,y,λ​f(x,y)+αg(x,y)     s.t.   α>=0(2)
其中很重要的一点就是$\alpha >=0$这一约束，这和等式约束是很不一样的。接下来同样结合图来解释。

对于不等式约束，我们可以给出两种情况，第一种情况就是不等式约束给出的可行解域中包含了f(x,y)的最值，那么这种情况对应的图示如下：

在这种情况下也就是说不等式约束事实上是不起作用的，所以求解带不等式约束的最优化问题等价于求原优化问题，所以等价于求公式（2）中$\alpha =0$的情况。

更需要关注的是可行解域不包含f(x,y)的最值的情况，可用如下图表示：

我们不妨结合图来看，首先给出观点，我们要求的最小值点图中的切点位置，在这一点处g(x,y)的梯度和f(x,y)的梯度是反向的，而且这个反向是必须的，这一点和等式约束中的可以是相同方向不同。接下来从几何意义方面解释为什么必须是反向的。

从图上的情况来看，由于我们要求最小值，当然希望等高线缩得越靠近最优值点越好，而且需要注意的是由于约束条件确定的可行解域（图中的绿色部分）不包含理想情况下的最优值点，因此我们的最值将会在可行解域的边界上取到。不妨假设我们沿着边界移动来寻找最优值点，那么解释和上面等式约束一样，可以比较容易得出在最优值点处一定是两个梯度平行的，接下来解释为什么两个梯度一定是反向的。

结合图中来说，我们观察切点，如果这个点处两个梯度是相同方向的关系，也就是说图中的切点处的绿色箭头和蓝色箭头同向，那就是说在当前切点处沿着梯度的反方向（也就是当前的绿色箭头方向）运动一点得到的g(x,y）是比当前切点处小的，而当前切点处的g(x,y)=0，那不就是说我们可以继续往理想情况的最优值点靠近一点吗？那也就意味着当前点不是最优值点，和假设不符。

从几何角度解释这一点我认为是更容易理解的，因此不给出详细的数学证明。最后给出一个KKT条件，这一条件是强对偶性的充要条件，后续博客中将会详细介绍强对偶性和KKT条件的关系，这里只给出KKT的形式：

假设有一个优化问题如下：
minxf(x)s.t.gi(x)=0i=1,2,..phj(x)≤0j=1,2,…qmin_{x}f(x) \\s.t.\ g_i(x)=0\ \ \ \ i=1,2,..p \\h_j(x)\le0\ \ \ \ \ \ \ \ \ j=1,2,…q minx​f(x)s.t. gi​(x)=0    i=1,2,..phj​(x)≤0         j=1,2,...q
则可以转化为拉格朗日函数如下：
L(x,λ,μ)=f(x)+∑i=1qλigi(x)+∑j=1pαjhj(x)L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{q}\lambda_ig_i(x)+\sum_{j=1}^{p}\alpha_jh_j(x) L(x,λ,μ)=f(x)+i=1∑q​λi​gi​(x)+j=1∑p​αj​hj​(x)
则KKT条件为：
∇L=0gi(x)=0,i=1,2,..phj(x)≤0,j=1,2..qαj≥0αjhj(x)=0,j=1,2,..p\nabla L=0\\ g_i(x)=0,i=1,2,..p\\ h_j(x)\le0,j=1,2..q\\ \alpha_j\ge0\\ \alpha_j h_j(x)=0,j=1,2,..p ∇L=0gi​(x)=0,i=1,2,..phj​(x)≤0,j=1,2..qαj​≥0αj​hj​(x)=0,j=1,2,..p