求解SVM时为什么要最大化拉格朗日函数？

SVM可以看作是「最小化最大间隔」的任务，本质上是一个二次规划的最优化问题。而求解二次规划问题的一个方法是利用拉格朗日乘数法，而在这个算法之中的一个难点就是「为什么要最大化拉格朗日函数？」

其实我们都知道该如何对无约束函数进行最优化：求导寻找极值。而对于带有约束的函数优化，就不能简单地求导寻找极值了：因为找到的极值可能不满足约束条件。所以这时候我们就要使用拉格朗日乘数法来解决这个问题了。

其实所谓的拉格朗日乘数法，就是求解等式或（和）不等式约束下最优化函数的一个方法。它能够将约束条件编码进巧妙设计的拉格朗日函数之中，使得对这个函数进行无约束的最优化所找到的极值就是原始函数在约束条件下的极值。

下面是一个带约束优化问题的基本形式：

$\begin{align} \min_{x\in \mathbf{R}^n} ~~~~~&f(x)& \\ s.t. ~~~~~&c_i(x)\leq0, &i=1,2,\dots,k \\ &h_j(x)=0, &j=1,2,\dots,l \end{align}$

这个问题称为原始最优化问题或原始问题。

然后引入广义拉格朗日函数(Generalized Lagrange Function)

$L(x,\alpha,\beta) = f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)$

其中$x=(x^{(1)}, x^{(2)}, \dots,x^{(n)})^T\in\mathbf{R}^n$，$\alpha_i,\beta_i$是拉格朗日乘子(Lagrange Multiplier)，$\alpha_i\geq0$。考虑$x$的函数

$\theta_{P}(x)=\max_{\alpha,\beta:\alpha_i\geq0}L(x,\alpha,\beta)$

上面这个函数，和带有约束的原始函数$f(x)$等价。那么为什么上面出现了$\max$这样的表示？为什么最大化这个拉格朗日函数，就相当于求解了原始函数？

其实我们只需要考虑一下这个拉格朗日函数在各个参数下的情况即可。

首先我们把上面的函数展开：

$\theta_P(x)=\max_{\alpha,\beta:\alpha_i\geq0}\left[f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\right]$

首先，我们考虑如果在给定一个$x$后，任意一个约束条件($c_i(x)$或$h_j(x)$)不被满足时会发生什么情况：

$h_j(x)\neq0$时，由于没有限制$\beta_j$的取值范围，所以可以通过调节$\beta_j$来实现$\beta_jh_j(x)=+\infty$，所以$\theta_P(x)=+\infty$
$c_i(x)>0$时，直接让$\alpha_i=+\infty$，也会导致$\theta_P(x)=+\infty$

而如果约束条件被满足，则：

$h_j(x)=0$时，带有$\beta_j$这一项不起作用。
$c_i(x)<=0$时，由于限制了$\alpha_i\geq0$，所以此时只有$\alpha_i=0$才能让这个函数取得最大值。而此时带有$\alpha_i$这一项也不起作用了。

这说明，当约束条件被满足时，$\theta_P(x)=f(x)$。而当约束条件不满足时$\theta_P(x)=+\infty$。

如果对这个函数进行最小化，就相当于对原始函数$f(x)$进行最小化，而且得到的值一定满足约束条件（因为不满足约束条件时，这个函数达到最大值），即：

$\min_x\theta_P(x)=\min_x\max_{\alpha,\beta:\alpha_i\geq0}L(x,\alpha,\beta)$

是与原始的优化问题等价的。

P.S. 上面这个原始优化问题其实是包含了等式和不等式两种约束。而SVM其实只有不等式约束，表示起来还要更简单一些。