【附件】拉格朗日乘子法-带约束优化

由于SVM的推导中几乎处处都用到了拉格朗日函数对偶问题的知识，本文讲述拉格郎日函数对偶问题是如何解决带约束条件问题的，并梳理整理在实际使用中的流程。

本文主要参考自李航-《统计学习方法》中的附录：《拉格朗日对偶性》。

问题背景

一般带约束条件的问题有如下形式：

目标函数：                                                    

约束条件：                           

该问题不仅要考虑函数求极值，还要考虑约束条件，这使得求解难度加大。因此，一般可以使用拉格朗日对偶问题方法来将该问题转换为较简单的约束条件下的优化问题，再进行求解。

一、拉格朗日乘子法-简化约束条件

本节讲述如何借助拉格朗日乘子法简化原问题中的约束条件。

1.1. 简化约束条件-思路解说

由于带约束条件的问题，不仅要考虑目标函数的最优值，还需要考虑复杂的约束条件。因此，不妨简化约束条件，简化的思路如下：

由于需要求目标函数最小值，那么，只要构造一个函数，使得它在约束条件内与目标函数一样，在约束条件外趋于无穷大，那就可以去掉约束条件，只需针对该函数进行优化。

1.2. 简化约束条件-拉格朗日乘子法

构造一个函数 ，要求在约束条件内与目标函数一致，在约束条件外趋于无穷大。

要达到这个目的，使用拉格朗日函数构造即可，方法如下：

其中，

备注 : 称为拉格朗日函数。

注意，是关于的函数，对任一个固定的，当 取不同的值，就会有不同的值，但只取其中最大的值，作为对应的函数值，因此是只关于的函数。

1.3. 验证 L(x)符合构造要求

下面我们一起来验证一下，拉格朗日乘子法构造出来的是否符合构造要求。

验证L(x)是否符合构造要求，其实就是验证它在约束条件内是否与f(x)一致，并且在约束条件外是否无穷大。

【1】验证 L(x)在约束条件内与 f(x)一致

由于在约束条件内, ，因此， 越小，越大，要取的最大值，必取最小值，即0，可知， 为0。同时，在约束条件内,  =  0 ，也即  为0，因此，在约束条件内， 。

【2】验证L(x)在约束条件外趋于无穷大

在约束条件外，即至少存在某项  或 ，此时，令对应的取无穷大 ( 或对应的取 无穷大，符号与一致 )，则 趋于无穷大，因此，在约束条件外，趋于无穷大。

1.4. 构造结果-总结

综上，总结构造结果如下，它将原问题转换为以下问题：

目标函数：  

约束条件：                                                                 

该问题也称为广义拉格朗日函数的极小极大问题。

二、利用对偶问题降低求解难度

通过构造广义拉格朗日函数的极小极大问题来替代原问题，虽然简化了约束条件，却复杂化了目标函数，使目标函数里包含了双层优化目标：min max，这就给求解增加了难度。较幸运的是，它的对偶问题，可以简化成只有一层优化目标，较易求解。因此，可通过求解对偶问题来曲线救国找到原问题的最优解。

下面详细讲解如何利用对偶问题来降低求解难度。

2.1. 转换为对偶问题

对偶问题即把原问题的min,max对调。

对偶问题如下：

目标函数：

约束条件：                                                                 

备注：该形式称为广义拉格朗日函数的极大极小问题。

2.2. 简化对偶问题

由于对偶问题的部分，在导数为0时取得最小解，即 ，对其化简后可得：

即有：

最终，对偶问题目标函数可以写成如下形式：

目标函数： 

约束条件： 

如此一来，目标函数中就去掉了min部分，只保留max部分了。

三、可以转为对偶问题求解的条件

上面我们已经得到原问题和对偶问题，如下：

原问题-目标函数：  

对偶问题-目标函数：

下面我们来讲解，在什么情况下，可以将原问题转为对偶问题进行求解。

3.1. 引理：对偶问题与原问题关系

引理1：原值必不小于对偶值

如果原问题和对偶问题都有最优值，则"原问题最优值"永大于等于"对偶问题最优值“，也即：

 

引理2：两值相等必是最优解

两函数值相等，则所对应的解必已是最优解 ：如果 , 则L(x)此时必已取得最小值，就是原问题  的最小值解，同样地,   是的最大值解。

从上面两个引理可以知道，当  时，求 L(x) 的最小值等同于求 的最大值，则求原问题，可转为求对偶问题。

3.2. 对偶问题可替代原问题的充分条件

在什么条件下，可以用对偶问题代替原问题，也即何时：

已证明，满足以下条件即可：

(1) 是凸函数。

(2) 是仿射函数(最高次数为1的多项式函数)。

(3) 是严格可执行的 (至少存在一个 x ,使所有的 )。

说明：以上条件是充分条件，即满足以上条件的，必然有，但并非必要条件，即存在其它情况，不满足以上条件，也能成立。

四、原问题与对偶问题最优解之间的关系

在求解对偶问题后，需要将对偶问题的解转换回原问题的解，本节讲解两个问题最优解之间的关系。

4.1. 原问题与对偶问题最优解的关系：KKT条件

如果满足(3.2)中的三个条件，

则对偶问题的最优解 与原问题的最优解 必能满足以下关系(KKT条件，共7条)  :

Part-1：L(x,α,β)偏导为0 :

拉格朗日函数对各个变量的偏导在最优解处为0，即：

       ------【1】    

       ------【2】   

       ------【3】   

Part-2：α_i,C_i(x^*)必有一为 0

                      ------【4】

Part-3：满足约束条件

                                  ------【5】

                                 ------【6】

                                                  ------【7】

补充：如果某组满足以上7条KKT条件，则它也必是最优解。即在“对偶问题可替代原问题的三个充分条件”下，“满足KKT条件”与"是最优解"互为充要条件。

五、实际使用-流程总结

下面总结使用拉格朗日对偶性解决带约束条件的优化问题时的实操步骤。

5.1. 原问题

含约束条件的原问题如下：

目标函数：                                          

约束条件：                

5.2. 解决带约束条件的优化问题流程

用拉格朗日对偶性解决带约束条件问题的流程和思路如下：

先判断原问题与对偶问题是否等价，若等价，则对对偶问题求解，求得 后，即可根据KKT条件，反推出 的值。一共四大步，下面具体介绍每一步的细节。

Step-1：验证是否可用对偶问题替代原问题

即验证以下三个条件

(1) 是凸函数。

(2) 是仿射函数(最高次数为1的多项式函数)。

(3) 是严格可执行的 (至少存在一个 x ,使所有的 ) 。

Step-2：写出对偶问题

可以直接写出对偶问题（广义拉格朗日函数极大极小形式 ）如下：

目标函数：

约束条件：                                                                     

Step-3：化简对偶问题

利用 来化简对偶问题中部分，将化简成 的形式，代入目标函数中，最终，对偶问题目标函数可以写成如下形式：

目标函数：

约束条件： 

Step-4：利用对偶问题的解反推原问题的解

(1) 先求得对偶问题的最优解。

(2) 然后，根据KKT条件，找出对偶问题的最优解 与原问题的最优解 的关系。

(3) 最后，整理成的形式，就可通过 获得原问题的最优解 。

结束语

本文主要参考自李航-《统计学习方法》中的附录：《拉格朗日对偶性》，如有细节不明白，请直接参阅《统计学习方法》。