拉格朗日乘子法详解（Lagrange multiplier）

最近在视频的变换编码里推导最优变换（KL变换）时需要用拉格朗日乘子法，之前在机器学习的各种优化问题里也要用到这个方法，特此仔细钻研一番，总结如下：

注：这篇博客讲的很全面，这里部分参考了他的讲解。

注：本文只讲了拉格朗日函数的构造，看完本文后再去了解拉格朗日对偶函数的推导以及对偶问题。

• 核心：极值点处，函数和约束条件一定相切，梯度一定共线（同向or反向）！！！
  以此为思想基础构建拉格朗日函数，把等式约束条件和不等式约束都通过引入拉格朗日乘子（就是个系数）整合到一个新函数里，使得原本的复杂的多约束优化问题变成了最简单的无约束优化问题，直接对构造出的拉格朗日函数的所有变量（包括原本的变量 x i , i = 1 , 2 … , m x_i,i=1,2\ldots,m xi​,i=1,2…,m和新引入的乘子变量 λ k , μ j , j = 1 , 2 … , n , k = 1 , 2 … , l \lambda_k,\mu_j,j=1,2\ldots,n,k=1,2\ldots,l λk​,μj​,j=1,2…,n,k=1,2…,l）求偏导等于零，得到的就是最终解。

• 用途：求解含有等式约束的最优化问题的局部最优解！！（极值点不一定是最小点，所以不是全局最小哟）；对于含有不等式约束的问题，要用到扩展的拉格朗日乘数法，这个扩展就是KKT条件的引入，更多细节参见这篇博文。

最优化问题按照约束条件的有无和类别可分为三类：
（一） “无约束" 优化问题
直接对所有 m m m个变量求偏导，令偏导等于0，联立方程组求出来的点就可能是极值点，具体是不是那就代到原函数里看看是不是比周围的值都小就行。
∂ F x i = 0 i = 1 , 2 … , m \frac{\partial F}{x _i}=0 \quad i=1,2\ldots,m xi​∂F​=0i=1,2…,m
补充注解：

1. 偏导等于0只是极值点的必要条件，所以可能是。
2. 直观地看，极值点左右的导数一定异号，又因为函数连续，所以极值点的导数只能为0。
3. 必要条件：满足必要条件不能说明一定是；不满足则一定不是！！
4. 充分条件：满足充分条件则一定是；不满足则给出的信息为0

下面（二）（三）类优化问题都是通过构造拉格朗日函数把问题转化为第（一）类的。

（二）“等式约束” 优化问题
目标函数（待优化的函数）为 f ( x ) f(x) f(x),约束条件为 h k ( x ) , k = 1 , 2 … , l h_k(x),k=1,2\ldots,l hk​(x),k=1,2…,l，问题建模为
m i n f ( x ) s . t . h k ( x ) = 0 min f(x) \quad s.t. \quad h_k(x)=0 minf(x)s.t.hk​(x)=0
这时候我们构建拉格朗日函数：
为什么这么构建参见知乎这个回答，很好理解，就因为梯度共线：
一个等式约束欸但表示对理解共线最有帮助：
∇ f ( x ∗ ) + λ ∇ h ( x ∗ ) = 0 , x ∗ 为 极 值 点 \nabla f(x^*)+\lambda\nabla h(x^*)=0,x^*为极值点 ∇f(x∗)+λ∇h(x∗)=0,x∗为极值点
多个等式约束则表示为：
∇ f ( x ∗ ) + ∑ k = 1 l λ k ∇ h k ( x ∗ ) = 0 , x ∗ 为 极 值 点 \nabla f(x^*)+\sum_{k=1}^l\lambda_k \nabla h_k(x^*)=0,x^*为极值点 ∇f(x∗)+k=1∑l​λk​∇hk​(x∗)=0,x∗为极值点
L ( x , λ ) = f ( x ) + ∑ k = 1 l λ k h k ( x ) L(x,\lambda)=f(x)+\sum_{k=1}^l\lambda_kh_k(x) L(x,λ)=f(x)+k=1∑l​λk​hk​(x)
L ( x , λ ) L(x,\lambda) L(x,λ)即拉格朗日函数， λ k \lambda_k λk​是拉格朗日乘子.上面的公式实际上就是下面的拉格朗日函数对x求偏导的结果。

这时就成了第一类的无约束优化了，只是变量增多了 l l l个，同第一类问题，分别对 m + l m+l m+l个变量求偏导，得出来的解代入目标函数就ok了！
∂ F λ k = 0 ， 这 得 到 的 就 是 那 组 等 式 约 束 \frac{\partial F}{\lambda _k}=0 ， 这得到的就是那组等式约束 λk​∂F​=0，这得到的就是那组等式约束
∂ F x i = 0 ， 这 得 到 的 就 是 ∇ f ( x ∗ ) + ∑ k = 1 l λ k ∇ h k ( x ∗ ) = 0 \quad \frac{\partial F}{x _i}=0，这得到的就是\nabla f(x^*)+\sum_{k=1}^l\lambda_k \nabla h_k(x^*)=0 xi​∂F​=0，这得到的就是∇f(x∗)+k=1∑l​λk​∇hk​(x∗)=0
（三）“等式约束+不等式约束” 优化问题
这是最复杂也最常见的一种模型。问题建模为：
m i n f ( x ) s . t . h k ( x ) = 0 , g j ( x ) ≤ 0 j = 1 , 2 … , n ; k = 1 , 2 … , l minf(x) \quad s.t.h_k(x)=0\quad,\quad g_j(x)\leq0\quad j=1,2\ldots,n;k=1,2\ldots,l minf(x)s.t.hk​(x)=0,gj​(x)≤0j=1,2…,n;k=1,2…,l
思路一样，还是要最终转化为无约束的简单优化问题，但这里要分为两步：

1. 先把不等式约束条件转化为等式约束条件。 how？ → \to → 引入 松弛变量 / KKT乘子
2. 再把等式约束转化为无约束优化问题。 how? → \to → 同(二)，引入拉格朗日乘子

构造拉格朗日函数为：
L ( x , λ , μ ) = f ( x ) + ∑ k = 1 l λ k h k ( x ) + ∑ j = 1 n μ j g j ( x ) L(x,\lambda,\mu)=f(x)+\sum_{k=1}^l\lambda_kh_k(x)+\sum_{j=1}^n\mu_jg_j(x) L(x,λ,μ)=f(x)+k=1∑l​λk​hk​(x)+j=1∑n​μj​gj​(x)

λ k \lambda_k λk​是为等式约束引入的拉格朗日乘子
μ j \mu_j μj​是为不等式约束引入的松弛变量

至此，含不等式约束的最复杂的优化问题也转化为无约束的简单问题了，剩下的就只有求偏导了。
即最终只需要求解，解出来的就可能是极值点啦（KKT也只是必要条件）：
{ ∇ f ( x ∗ ) + ∑ k λ k ∇ h k ( x ∗ ) + ∑ j μ j ∇ g j ( x ∗ ) = 0 ( 1 ) μ j ≥ 0 ( 2 ) μ j g j ( x ∗ ) = 0 ( 3 ) h k ( x ∗ ) = 0 ( 4 ) g j ( x ∗ ) ≤ 0 ( 5 ) \left\{ \begin{aligned} \nabla f(x^*) + \sum_{k}\lambda_k\nabla h_k(x^*)+\sum_{j}\mu_j\nabla g_j(x^*)& = &0 \quad (1)\\ \mu_j & \geq & 0 \quad (2)\\ \mu_jg_j(x^*) & = & 0 \quad (3)\\ h_k(x^*) & = & 0 \quad (4)\\ g_j(x^*) & \leq & 0\quad (5)\\ \end{aligned} \right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​∇f(x∗)+k∑​λk​∇hk​(x∗)+j∑​μj​∇gj​(x∗)μj​μj​gj​(x∗)hk​(x∗)gj​(x∗)​=≥==≤​0(1)0(2)0(3)0(4)0(5)​

这里由于有不等式约束因此要引入KKT条件（Karush–Kuhn–Tucker conditions）

这个KKT可以说是很神秘很厉害了，之前学无线网络也一直在用它求解不等式优化问题，现在学机器学习，视频编码竟然还是要用，所以只要有不等式约束的优化是绕不开了，不过thank god也不算太难？（手动一个不太自信还很尴尬的微笑） 关于KKT条件，我这篇博文做了详解。