拉格朗日乘子法&KKT条件---未完成

2018/6/14 posted in  MachineLearning

如果不理解拉格朗日乘子法和KKT条件的相关原理,则不可能真正理解SVM的计算方法.

这是我们学习SVM的大前提

优化问题

通常,我们要求解的函数优化问题,大致可分为以下3类

  • 无约束条件的优化问题: \[min f(X)\]
  • 只有等式约束的优化问题: \[min f(X) \\\ s.t: h_i(X)=0,i \in {1,2,...,n}\]
  • 含有不等式约束的优化问题:
    \[min f(X) \\\
    s.t: h_i(X)=0,i \in {1,2,...,n} \\\
    g_j(X) \leq 0, j \in {1,2,...,n} \]

其中大写的X表示所有自变量的集合(也可以说是所有样本点的集合),\(h_i(X)\)表示等式约束条件,\(g_i(X)\)表示不等式约束条件.这里用\(min f(X)\)表示求取最优值的目标函数,其实不一定是求取最小值,求最大值也是可以的(取相反数即可).但是一般最优化都是取小值.

注意:默认所有解决的最优问题都是凸优化问题(即求取凸函数的最优解).拉格朗日乘子法一定是适用于凸优化问题,而不一定适用于其他非凸问题.

回到最上面的三类优化问题,解决方法是明确的,参考如下(注意:默认都是针对凸优化问题):

  • 对于无约束条件的优化问题,直接对其各个自变量求导,令导数为0,得全局最优解.
  • 对于只有等式约束的优化问题,利用拉格朗日乘子法,得到全局最优解.
  • 对于含不等式约束的优化问题,利用KKT条件,得全局最优解.

拉格朗日乘子法

举个例子来描述拉格朗日乘子法的基本思路:
\[min f(X)=2x_1^2+3x_2^2+7x_3^2 \\\
s.t : 2x_1+x_2=1,\quad 2x_2+3x_3=2\]

这个例子正式只有等式约束条件的优化问题,求解思路如下:
首先想到直接对3个自变量分别求偏导,令其偏导数都为0,则此时\(x_1,x_2,x_3\)都是0,看函数也是这样,当3个自变量都是0时,函数取得最小值0.但是这显然不符合约束条件的.

怎么把约束条件考虑进去呢?用拉格朗日乘子法,把改写后的约束条件乘以一个系数,然后以加的形式带入目标函数,该函数称之为拉格朗日函数.先看看改写后的约束条件:
\[s.t : 2x_1+x_2-1=0,\quad 2x_2+3x_3-2=0\]
左右移项,实际上没发生任何变化.其后,将改写后的约束条件带入目标函数,构造拉格朗日函数:
\[L(X,\alpha)=2x_1^2+3x_2^2+7x_3^2+\alpha_1(2x_1+x_2-1)+\alpha_2(2x_2+3x_3-2)\]

可见,当求得的最优解满足约束条件时,\(L(x,\alpha)\)与原始的目标函数并没有差别(后面都是0).这样,我们再对这个拉格朗日函数求关于各个自变量的偏导,并令这些偏导数为0.
\[
\begin{aligned}
\dfrac{\partial f(X)}{\partial x_1} & =4x_1+2\alpha_1=0 \implies x_1=-\frac12\alpha_1 \\
\dfrac{\partial f(X)}{\partial x_2} & =6x_2+\alpha_1+2\alpha_2=0 \implies x_2=-\frac16\alpha_1 - \frac13\alpha_2 \\
\dfrac{\partial f(X)}{\partial x_3} & =14x_3+3\alpha_2=0 \implies x_3=-\frac{3}{14}\alpha_2
\end{aligned}\]

现在,将用系数\(\alpha_1,\alpha_2\)表示的3个自变量带入约束条件,可得如下方程:
\[
\begin{aligned}
-\dfrac{7}{6}\alpha1 - \dfrac{1}{3}\alpha_2 -1 & =0 \\
-\dfrac{1}{3}\alpha1 - \dfrac{55}{44}\alpha_2 -2 & =0
\end{aligned}\]

两个未知数,两个方程,可以求解得到\(\alpha_1=-0.45,\alpha_2=-1.41\),再带入自变量的表达式,即求得最优解.

拉格朗日乘子法的形式化描述

用拉格朗日乘子法解决只有等式约束条件的优化问题,可以被如下形式化的描述:
现有优化问题:
\[min f(X) \\
s.t: h_i(X)=0,i \in {1,2,...,n}\]
则需要先得到拉格朗日函数\(L(X,\alpha)=f(X)+\sum_{i=1}^n \alpha_i \cdot h_i(X)\),对该函数的各个自变量求偏导,令偏导数为0,则可以求出各个自变量的含系数\(\alpha\)的代数式,再带入约束条件,解得\(\alpha\)后,可最终得到最优解.

KKT条件

上面说的拉格朗日乘子法,解决的是只有等式约束条件的优化问题,而现实中更普遍的情况是求解含有不等式约束条件的问题.

还是通过一个例子讲解,优化问题如下:
\[min f(X)=x_1^2-2x_1+1+x_2^2+4x_2+4 \\\
s.t : x_1+10x_2 > 10 \\\
10x_1-x_2 < 10\]

第一步:把约束条件改写如下:
\[s.t : 10-x_1-10x_2<0 \\\
10x_1-x_2-10<0\]

改写的目的是方便后面的计算,且这种改写没有改变约束条件本身,所以不影响.

第二步:与拉格朗日乘子法相同,给约束条件乘以系数后加入目标函数,构成拉格朗日函数\(L(X,\beta)\)
\[L(X,\beta)=x_1^2-2x_1+1+x_2^2+4x_2+4+\beta_1(10-x_1-10x_2)+\beta_2(10x_1-x_2-10)\]

第三步:对拉格朗日函数的各个自变量求偏导:
\[
\begin{aligned}
\dfrac{\partial f(X)}{\partial x_1} & =2x_1-\beta_1+10\beta_2 -2 \\
\dfrac{\partial f(X)}{\partial x_2} & =2x_2-10\beta_1-10\beta_2+4
\end{aligned}\]

做完以上3步,先不往下进行了.先给出KKT条件的形式化描述如下.

KKT条件的形式化描述

KKT条件用于解决带有不等式约束条件的优化问题,可以被如下形式化描述:
现有优化问题:
\[min f(X) \\\
s.t: h_i(X)=0,i \in {1,2,...,n} \\\
g_j(X) \leq 0, j \in {1,2,...,n} \]
根据这个优化问题可以得到拉格朗日函数:
\[L(X,\alpha,\beta)=f(X)+\sum_{i=1}^m\alpha_i \cdot h_i(X)+\sum_{j=1}^m\beta_j \cdot g_j(X)\]

那么KKT条件就是函数的最优值必定满足下面3个条件(这3个条件是重点中的重点)

  • \(L(X,\alpha,\beta)\)对各个自变量求导为0
  • h(X)=0
  • \(\sum_{i=1}^m\beta_j \cdot g_j(X)=0,\beta_j \geq 0\)

3个条件中,前两个很好理解,不说了.关键在于第3个条件,这也是这篇文章中最难理解的部分.我尝试解释一下这个条件的原理.

首先,我们已知\(\beta_j \geq0,而g_j(X)\leq 0\)(这样设计的目的是要求目标函数的梯度和约束条件的梯度必须反向).也就是说,想要条件3成立,则每一项\(\beta_j \cdot g_j(X)都等于0\),再换个说法,对于每一项来说,要么\(\beta_j=0\),要么\(g_j(X)=0\).这就是条件3所要表达的真实含义.

下面解释为什么这样的条件可以用来寻找最优解.

假设X由2个自变量\(x_1,x_2\)组成,那么我们很容易想象出目标函数f(X)的图像,它就是一个三维空间中的曲面;再假设此时优化问题有3个不等式约束条件\(g_1(X),g_2(X),g_3(X)\).那现在可以把优化问题的图像画出来,如下图所示.画的是该问题再\(x_1 x_2\)平面上的投影,虚线为f(X)的等高线,那现在就有左图和右图两种不同情况了.

左图表示的是min f(X)在不等式的约束范围内,且不在不等式的约束面上.这时,f(X)的最优解与不等式的约束实际上没关系了,我们就令\(\beta_1=\beta_2=\beta3=0\)成立,而且此时,\(L(X,\alpha,\beta)\)对各个自变量求导为0的解就是最优解.换句话说,这种情况需要条件1,3同时成立.

参考

https://blog.csdn.net/on2way/article/details/47729419