|
前言： 我搜了一下目前网络上很少有关于拉格朗日松弛方法(LR)的系统性的介绍，同时拉格朗日松弛方法非常的有意思在于它是运筹优化领域解决混合整数的一种主要方法，同时也是机器学习里边SVM（支持向量机）的理论基础。我发现很多同学无法完全领会支持向量机的精髓，恰恰是因为对拉格朗日松弛不了解。废话到此，那么直接上干的。
1拉格朗日松弛方法(LR)的简介
在运筹优化领域，LR常用来求解混合整数规划问题，是数学方法里边求解混合整数规划问题比较有效的方法。一般同学对混合整数规划问题接触最多的是进化计算方法（例如：GA, PSO等），还有启发式方法，割平面法。关于本文要用到的一些名词可以参考 离散/整数/组合/非凸优化概述及其在AI的应用。我们先抛开这些背景。考虑如下标准形式的优化问题（如果有等式约束的话可以转化成两个不等式的约束）：
min
?
x
f
0
(
x
)
s
.
t
.
????
f
i
(
x
)
≤
0
,
??????
i
=
1
,
.
.
.
,
m
????????????
(
A
1
)
\begin{array}{l} \mathop {\min }\limits_x {f_0}\left( x \right)\\ s.t.\;\;{f_i}\left( x \right) \le 0,\;\;\;i = 1,...,m \end{array} \;\;\;\;\;\; (A1)
xmin?f0?(x)s.t.fi?(x)≤0,i=1,...,m?(A1)
LR的基本思想很简单，就是将约束放到目标函数上去考虑。如果把所有的约束都放到目标函数上去话，约束优化问题就转化成无约束优化问题了，这样的话问题就简单多了。那么LR是怎么转化的呢，如下所示：
L
(
x
,
λ
)
=
f
0
(
x
)
+
∑
i
=
1
m
λ
i
f
i
(
x
)
L\left( {x,\lambda } \right) = {f_0}\left( x \right) + \sum\limits_{i = 1}^m {{\lambda _i}{f_i}\left( x \right)}
L(x,λ)=f0?(x)+i=1∑m?λi?fi?(x)
我们把
L
(
x
,
λ
)
L\left( {x,\lambda } \right)
L(x,λ) 称为拉格朗日函数，即在原来的目标函数上增加了约束的加权求和，得到一个增广的目标函数。通过这样一个转化将约束放到了目标函数上，求解A1这个优化问题就转化成了求解如下优化问题
g
(
λ
)
=
min
?
x
L
(
x
,
λ
)
????????????
(
A
2
)
g\left( \lambda \right) = \mathop {\min }\limits_x L\left( {x,\lambda } \right) \;\;\;\;\;\; (A2)
g(λ)=xmin?L(x,λ)(A2)
g
(
λ
)
g\left( \lambda \right)
g(λ) 是一个函数，我们称为对偶函数，每取一个
λ
\lambda
λ 都有一个
g
(
λ
)
g\left( \lambda \right)
g(λ) 与之对应。由此我们可知对偶函数
g
(
λ
)
g\left( \lambda \right)
g(λ) 是原优化问题A1最优值
p
?
{p^*}
p? 的下界，即对任意
λ
≥
0
\lambda \ge 0
λ≥0 有如下式成立
g
(
λ
)
≤
p
?
g\left( \lambda \right) \le {p^*}
g(λ)≤p?
很容易证明这一点，设
x
^
\hat{x}
x^ 为原优化问题A1任意的一个可行解，那么有
g
(
λ
)
=
L
(
x
^
,
λ
)
=
f
0
(
x
^
)
+
∑
i
=
1
m
λ
i
f
i
(
x
^
)
≤
f
0
(
x
^
)
g\left( \lambda \right) =L\left( \hat{x},\lambda \right) =f_0\left( \hat{x} \right) +\sum_{i=1}^m{\lambda _if_i\left( \hat{x} \right) \le}f_0\left( \hat{x} \right)
g(λ)=L(x^,λ)=f0?(x^)+i=1∑m?λi?fi?(x^)≤f0?(x^)
因为
λ
≥
0
\lambda \ge 0
λ≥0 ，且
x
^
\hat{x}
x^ 还是可行解，所以
L
(
x
^
,
λ
)
L\left( \hat{x} ,\lambda \right)
L(x^,λ) 的第二项总是小于等于0的，因此可以证明上面的结论。同时
g
(
λ
)
g\left( \lambda \right)
g(λ) 是一个凸函数，这一点在这里就不给出说明了，因为要用到一些关于下确界的性质。我们知道
g
(
λ
)
≤
p
?
g\left( \lambda \right) \le {p^*}
g(λ)≤p? 是对任意的
λ
≥
0
\lambda \ge 0
λ≥0 都满足的，那我们想用
g
(
λ
)
g\left( \lambda \right)
g(λ) 来近似原优化问题的话，我们自然希望
g
(
λ
)
g\left( \lambda \right)
g(λ) 和原优化问题最优解是越接近越好了，那我们需要找一个最好的下界，可以将问题表述为如下优化问题
max
?
λ
g
(
λ
)
s
.
t
.
??????
λ
≥
0
????????????
(
B
1
)
\begin{array}{l} \mathop {\max }\limits_\lambda g\left( \lambda \right)\\ s.t.\;\;\;\lambda \ge 0 \end{array} \;\;\;\;\;\; (B1)
λmax?g(λ)s.t.λ≥0?(B1)
这个优化问题被称为对偶问题，前面已经说了
g
(
λ
)
g\left( \lambda \right)
g(λ) 是凸函数，那么该对偶问题是一个凸优化问题，而且不论原问题凸不凸，其对偶问题肯定是凸的。对偶问题的出发点就是在下界里边找到一个最好的最解决原问题最优解的
λ
?
{\lambda ^*}
λ? 。
g
(
λ
?
)
g\left( {{\lambda ^*}} \right)
g(λ?) 依然小于
p
?
{p^*}
p? ，只不过相对于其它任选的
g
(
λ
)
g\left( \lambda \right)
g(λ) ，它更接近
p
?
{p^*}
p? 。可以看到LR方法是在用凸优化来逼近原优化问题A1(一般的优化问题)，因为凸优化很好求到全局最优，同时我们一般也比较容易能找到一个可行解做为
p
?
{p^*}
p? 的上界，这样从上下两个方向上夹逼最优解就达到了我们的目的。
2拉格朗日松弛方法的进一步理解----与惩罚函数法有什么不同
我们可以将原优化问题A1重新等价的表示为如下无约束优化问题
min
?
x
f
0
(
x
)
+
∑
i
=
1
m
I
?
(
f
i
(
x
)
)
????????????
(
A
3
)
\mathop {\min }\limits_x {f_0}\left( x \right) + \sum\limits_{i = 1}^m {{I_ - }\left( {{f_i}\left( x \right)} \right)}\;\;\;\;\;\; (A3)
xmin?f0?(x)+i=1∑m?I??(fi?(x))(A3)
其中
I
?
(
u
)
=
{
0
,
????
u
≤
0
∞
,
????
u
>
0
{I_ - }\left( u \right) = \left\{ \begin{array}{l} 0,\;\;u \le 0\\ \infty ,\;\;u > 0 \end{array} \right.
I??(u)={0,u≤0∞,u>0?
约束的意思就是绝对不能违反，通过
I
?
(
u
)
{I_ - }\left( u \right)
I??(u) 函数可以反映这样的一个意思，即违反约束的话就施加无穷大的惩罚，让优化问题A3绝对不可能违反约束。而对比优化问题A2，相当于用线性函数去替代
I
?
(
u
)
{I_ - }\left( u \right)
I??(u) 函数。我们用一个软的约束去替代了一个硬约束，可以看做用线性函数做
I
?
(
u
)
{I_ - }\left( u \right)
I??(u) 的一个下估计（
λ
u
≤
I
?
(
u
)
\lambda u \le {I_ - }\left( u \right)
λu≤I??(u) ）。也就是说此时优化问题A2有可能会接受
f
i
(
x
)
>
0
{f_i}\left( x \right) > 0
fi?(x)>0 的点，那么相对优化问题A3来说无形中扩大了可行域，一个更大的可行域上的最小值肯定是比在一个小的可行域上的最小值要小。这也解释了为什么优化问题A2是原问题A1的一个下界了。
到这里如果是以前多少接触过优化的同学都会想到一个概念就是惩罚函数法。惩罚函数的基本思想也是约束比较复杂难以处理，那么我就把约束乘以一个惩罚因子放到目标函数上去，若采用L2惩罚函数的话，优化问题A1可以转化为如下形式
min
?
x
f
0
(
x
)
+
μ
∑
i
=
1
m
(
max
?
[
0
,
f
i
(
x
)
]
)
2
????????????
(
A
4
)
\mathop {\min }\limits_x {f_0}\left( x \right) + \mu \sum\limits_{i = 1}^m {{{\left( {\max \left[ {0,{f_i}\left( x \right)} \right]} \right)}^2}} \;\;\;\;\;\; (A4)
xmin?f0?(x)+μi=1∑m?(max[0,fi?(x)])2(A4)
其中
μ
>
0
\mu > 0
μ>0 ，简单来说就是违反约束的话施加一个惩罚到目标函数上去，没有违反的话就不加惩罚，这么一个非常简单的思想。同理可以证明该优化A4也是优化问题A1的最优解的一个下界，和之前证明A2的情况完全是一个道理。当然惩罚函数的形式不一定非要取成L2范数的形式也就是平方的形式。我们可以把拉格朗日松弛看做是一种特殊的罚函数也不是不可以。那么惩罚函数法和LR方法有什么不同呢，主要是LR中我们是通过求解一个对偶问题
max
?
λ
g
(
λ
)
\begin{array}{l} \mathop {\max }\limits_\lambda g\left( \lambda \right)\\ \end{array}
λmax?g(λ)? 来找到一个最优的
λ
?
{\lambda ^*}
λ? ，而惩罚函数法则没有这一个过程，一般都是人为的设定一个系数 \mu ，这是两者思想差别最大的地方。惩罚函数法细分的话有精确罚函数，非精确罚函数等等这里也就不在这里一一讨论了，有兴趣的文后会列出参考文献方便查阅。
3拉格朗日松弛的理论分析----如何保证其最优性（强对偶性与弱对偶性）
通过上面的分析我们得到了一个重要的结论就是优化问题B1的最优解是优化问题A1的下界，即
g
(
λ
?
)
≤
p
?
g\left( {{\lambda ^*}} \right) \le {p^*}
g(λ?)≤p? ，那我们自然会问既然是小于等于，那等号什么时候成立呢。如果等号成立的话那这个世界真的就是非常和谐了，因为对于这样的优化问题，借助LR方法我们可以转化成凸优化，而凸优化可以求到全局最优解，一切的一切就非常完美了。我们一般把等号成立的情况称为强对偶性，如果等号不成立称为弱对偶性。 有很多的研究都给出了强对偶性成立的条件，首先要求原优化问题A1是一个凸优化问题，同时要满足一个Slater条件（一个让人很费解的条件，所以这里也不给出了，有兴趣可以参考参考文献[1]中第5章关于强弱对偶性的论述）。总体来说强对偶性要成立，最起码原问题得是一个凸优化问题才行。
看到这个结论可能会让你失望了，LR无法保证对非凸优化问题满足强对偶性（哈哈，如果满足了非凸优化也变得很简单了），也就是说LR只能说能尽量去逼近原问题最优解，确没法证明一定能达到。
g
(
λ
?
)
≤
p
?
≤
f
(
x
^
)
g\left( {{\lambda ^*}} \right) \le {p^*} \le f\left( \hat{x} \right)
g(λ?)≤p?≤f(x^)
4拉格朗日松弛算法的具体求解过程（次梯度法）
我们把前面讲的内容整理一下发现LR方法的可以表述为如下形式
max
?
λ
min
?
x
L
(
x
,
λ
)
\mathop {\max }\limits_\lambda \mathop {\min }\limits_x L\left( {x,\lambda } \right)
λmax?xmin?L(x,λ)
先对
x
x
x求极小，然后x就没有了也就是变成了仅仅关于
λ
\lambda
λ 的函数
g
(
λ
)
g\left( \lambda \right)
g(λ) ，然后再对
g
(
λ
)
g\left( \lambda \right)
g(λ) 求极大值。也就是我们在一些书上可能会看到了极小极大化问题，根本的来源是LR方法。
那么如何求解这个问题呢，我们这里简要介绍一下LR的求解框架，
1 一般先随机给一个初始的
λ
(
k
)
{{\lambda ^{\left( k \right)}}}
λ(k)
2 把
λ
(
k
)
{{\lambda ^{\left( k \right)}}}
λ(k) 代入到
L
(
x
,
λ
)
L\left( {x,\lambda } \right)
L(x,λ) 中，然后求解松弛问题也就是
min
?
x
L
(
x
,
λ
(
k
)
)
\mathop {\min }\limits_x L\left( {x,{\lambda ^{\left( k \right)}}} \right)
xmin?L(x,λ(k)) ，解完得到一个当前步的最优的
x
(
k
)
{x^{\left( k \right)}}
x(k) 。
3 然后将这个
x
(
k
)
{x^{\left( k \right)}}
x(k) 代入到
L
(
x
,
λ
)
L\left( {x,\lambda } \right)
L(x,λ) ，然后求解对偶问题
max
?
λ
L
(
x
(
k
)
,
λ
)
\mathop {\max }\limits_\lambda L\left( {{x^{\left( k \right)}},\lambda } \right)
λmax?L(x(k),λ) ，得到
λ
(
k
+
1
)
{\lambda ^{\left( k+1 \right)}}
λ(k+1)
4令
λ
k
=
λ
k
+
1
{\lambda _k} = {\lambda _{k + 1}}
λk?=λk+1? ，判断是否停止，若没停止跳到第2步继续执行。
由于要先极大再极小，我们只能先固定住一个变量，在求解另一个变量，然后反复的迭代。整个算法流程就是先固定
λ
\lambda
λ ，对 x 求极小，然后固定住 x ，对
λ
\lambda
λ 求极大，然后反复进行。LR相关的论文可以证明该算法的收敛性。
至于松弛问题和对偶问题如何求解这里只是简单提一句，松弛问题的形式一般来讲是不确定的，但是若要让LR方法效果比较好松弛问题不宜过于复杂，因为在实际问题的求解中一般我们不会把所有的约束都放到目标函数上去，我们只是把复杂的难以处理的约束放到目标函数上去，选择那些约束放到目标函数上去这个要结合具体问题，甚至要结合具体的应用场景去设计。如果松弛之后得到的松弛问题是线性规划（LP），二次规划（QP）那就是最好不过的了。对偶问题的求解相对固定一些，因为前面说了无论原问题怎么样，对偶问题是一个凸优化，严格来讲是一个不可微的凸优化问题，针对不可微的凸优化问题一般采用次梯度方法来求解，可以理解为是把梯度的概念进行了推广，次梯度往往不唯一，这一点和梯度不同。研究如何选取次梯度也是LR中一个重要的方面，相关研究也有很多论文。
4SVM中的拉格朗日松弛方法
前面基本上把LR的基本过程介绍了一遍，虽然跳过了几个重要点，但是大致交待清楚了整个原理。然后我们进入SVM的介绍。我们先以经典的线性可分的二分类问题为例子，从这个非常直观的例子切入SVM的核心思想，对比SVM和神经网络的不同。
我要找一条线把两类点分开，如上图所示。对于上图的情况，可以找到无数条线能把这两类完全分开的（处于两条虚线之间的线都是可行解）。如果用传统的神经网络来做这个分类问题的话，最终得到的是这无数条线当中的一条而已，而且如果是采用BP的话由于每次初始点选择不一样的话每次得到的结果不一定会一样。如果用SVM同样来做这个分类问题的话，那么得到的就是最中间那条线。SVM这样一个机制实际上是要求不仅仅把两类分开，而且要尽可能的离两边都远一些。如果把仅仅分开这两类的解称为可行解，那么SVM就是在可行解里边找一个最好的，采用优化的思想来这样理解SVM显得更加有趣一些。也就是神经网络仅仅是找了一个可行解，SVM不满足现状从这些可行解里边找了一个最优解。既然是最优解那么如何用数学表达出来呢？ 很多的SVM书都有如下的一个优化问题形式：
min
?
w
,
b
1
2
∥
w
∥
2
s
.
t
.
??????
y
(
i
)
(
w
T
x
(
i
)
+
b
)
≥
1
,
??????
i
=
1
,
?
?
,
m
????????????
(
S
1
)
\begin{array}{l} \mathop {\min }\limits_{w,b} \frac{1}{2}{\left\| w \right\|^2}\\ s.t.\;\;\;{y^{\left( i \right)}}\left( {{w^T}{x^{\left( i \right)}} + b} \right) \ge 1,\;\;\;i = 1, \cdots ,m \end{array} \;\;\;\;\;\; (S1)
w,bmin?21?∥w∥2s.t.y(i)(wTx(i)+b)≥1,i=1,?,m?(S1)
其中
(
w
,
b
)
\left( {w,b} \right)
(w,b) 就是我们要找的直线的斜率和截距，
(
x
(
i
)
,
y
(
i
)
)
\left( {{x^{\left( i \right)}},{y^{\left( i \right)}}} \right)
(x(i),y(i)) 是图中第i个点的坐标值（是已知的），一共有m个点。
至于这个优化问题的形式是怎么来的这里不进行展开了，具体可以参考SVM相关书籍。我们可以看到这是一个QP问题，约束线性，目标函数二次，自然也是一个凸优化问题了。到这里我们实际上可以直接求解这个QP问题也是可以的。而采用LR转化成对偶问题之后，我们就可以得到后边，关于支持向量还有kernal这些概念了，同时和直接求解QP比较来看，转出对偶问题的求解更加效率一些。那么我们就套用LR方法把约束放上去，得到如下形式：
L
(
w
,
b
,
λ
)
=
1
2
∥
w
∥
2
?
∑
i
=
1
m
λ
i
[
y
(
i
)
(
w
T
x
(
i
)
+
b
)
?
1
]
????????????
(
S
2
)
L\left( {w,b,\lambda } \right) = \frac{1}{2}{\left\| w \right\|^2} - \sum\limits_{i = 1}^m {{\lambda _i}\left[ {{y^{\left( i \right)}}\left( {{w^T}{x^{\left( i \right)}} + b} \right) - 1} \right]} \;\;\;\;\;\; (S2)
L(w,b,λ)=21?∥w∥2?i=1∑m?λi?[y(i)(wTx(i)+b)?1](S2)
由于之前说了，如果S1是凸优化问题，且满足Slater条件的话，那么就满足强对偶性，也就是求解对偶问题和求解原问题是等价的。在这里我们知道S1是凸优化问题，Slater条件也容易验证满足。这就是SVM的一个数学基础，没有这个强对偶性SVM就没有那么漂亮。
得到
L
(
w
,
b
,
λ
)
L\left( {w,b,\lambda } \right)
L(w,b,λ) ，实际上我们借助KKT条件就能导出一个关于SVM的类似解析解的形式，这样一个形式比直接求解原问题S1要快的多。具体过程可以参考 零基础学Support Vector Machine(SVM)，这里就不赘述了。
6总结
题目是运筹学中的拉格朗日松弛方法与支持向量机中的拉格朗日松弛方法，其实这两种LR方法本质上没有区别。我们可以看到LR方法集中要处理的是约束，化繁为简，以凸逼近非凸的思想。在运筹，数学优化领域，LR常用来求解混合整数规划问题，是数学方法里边求解混合整数规划问题比较有效的方法。一般同学对混合整数规划问题接触最多的是进化计算方法（例如 GA, PSO），还有分支定界，割平面法，对LR理解的比较少，可能因为其数学味道比较浓。SVM本质是一个优化问题，这个优化问题从建模到求解经历了多次的优化问题等价转化的过程，本文无法一一诠释，只是摘出采用LR转化为对偶问题这一个关键步骤来说明。
可见优化问题的建模和转化无论在运筹学领域还是机器学习领域都有这十分重要的地位，数学优化的核心思想并非一个简单梯度下降，一个BP算法那么简单。
参考文献
[1]Boyd S, Vandenberghe L. Convex optimization[M]. Cambridge university press, 2004
[2]Bertsekas D P. Nonlinear programming[M]. Belmont: Athena scientific, 1999.
[3]台大 林轩田 机器学习技法
|