拉格朗日乘数法

叁歲伎倆 2022-11-17 03:22 213阅读 0赞

> 在数学最优[问题][Link 1]中，拉格朗日乘数法（以数学家[约瑟夫·路易斯·拉格朗日][Link 2]命名）是一种寻找变量受一个或多个条件所限制的[多元函数][Link 3]的[极值][Link 4]的方法。这种方法将一个有n 个变量与k 个[约束条件][Link 5]的[最优化问题][Link 6]转换为一个有n + k个变量的方程组的极值问题，其变量不受任何约束。本文介绍拉格朗日乘数法（Lagrange multiplier）。

### 概述 ###

*  我们擅长解决的是无约束极值求解问题，这类问题仅需对所有变量求偏导，使得所有偏导数为0，即可找到所有极值点和鞍点。我们解决带约束条件的问题时便会尝试将其转化为无约束优化问题
 *  事实上如果我们可以通过g得到某个变量的表示，例如 x 1 = h ( x 2 , . . . , x n ) x\_1 = h(x\_2, ..., x\_n) x1=h(x2,...,xn)，将该式带入 y y y即可抓换为无约束优化（初高中就是这么做的，所谓消元法是也），但有的时候我们无法得到这样的表示，便需要借助拉格朗日乘数法来避免消元法的困境。

> 作为一种优化算法，拉格朗日乘数法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有 n n n个变量和 k 个 k个 k个约束条件的约束优化问题转化为含有 （ n + k ） （n+k） （n\+k）个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。

### 思想 ###

*  考虑二元函数 f ( x , y ) f(x,y) f(x,y)，在约束 g ( x , y ) = c g(x,y)=c g(x,y)=c下的极值
 *  首先我们可以绘制出 f ( x , y ) f(x,y) f(x,y)的一层层等高线，当等高线与 g ( x , y ) = c g(x,y)=c g(x,y)=c相切时即可能是该问题的极值点

![拉格朗日乘数法示意图（转自知乎）][0a97dc9fb0ee9b73e75bb14d76542888.png]

### 拉格朗日乘数法 ###

#### 单个等式约束 ####

> 考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x\_1, x\_2,...,x\_n) y=f(x1,x2,...,xn)，在等式约束 g ( x 1 , x 2 , . . . , x n ) = 0 g(x\_1, x\_2,...,x\_n)=0 g(x1,x2,...,xn)=0 下的极值点求解问题

*  在极值点，必有 y y y和 g g g法向量平行
 *   y y y的法向量为：

\[ ∂ y ∂ x 1 , ∂ y ∂ x 2 , . . . , ∂ y ∂ x n \] \[\\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_1\}\}\},\\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_2\}\}\},...,\\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_n\}\}\}\] \[∂x1∂y,∂x2∂y,...,∂xn∂y\]

*   g g g的法向量为：

\[ ∂ g ∂ x 1 , ∂ g ∂ x 2 , . . . , ∂ g ∂ x n \] \[\\frac\{ \{\\partial g\}\}\{ \{\\partial \{x\_1\}\}\},\\frac\{ \{\\partial g\}\}\{ \{\\partial \{x\_2\}\}\},...,\\frac\{ \{\\partial g\}\}\{ \{\\partial \{x\_n\}\}\}\] \[∂x1∂g,∂x2∂g,...,∂xn∂g\]

*  二者平行，则存在常数 λ \\lambda λ使得：

\[ ∂ y ∂ x 1 , ∂ y ∂ x 2 , . . . , ∂ y ∂ x n \] + λ \[ ∂ g ∂ x 1 , ∂ g ∂ x 2 , . . . , ∂ g ∂ x n \] = 0 \[\\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_1\}\}\},\\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_2\}\}\},...,\\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_n\}\}\}\] + \\lambda \[\\frac\{ \{\\partial g\}\}\{ \{\\partial \{x\_1\}\}\},\\frac\{ \{\\partial g\}\}\{ \{\\partial \{x\_2\}\}\},...,\\frac\{ \{\\partial g\}\}\{ \{\\partial \{x\_n\}\}\}\] = 0 \[∂x1∂y,∂x2∂y,...,∂xn∂y\]\+λ\[∂x1∂g,∂x2∂g,...,∂xn∂g\]=0

*  即：

∂ y ∂ x i + λ ∂ g ∂ x i = 0 , 1 ≤ i ≤ n \\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_i\}\}\} + \\lambda \\frac\{ \{\\partial g\}\}\{ \{\\partial \{x\_i\}\}\} = 0,1 \\le i \\le n ∂xi∂y\+λ∂xi∂g=0,1≤i≤n

*  这样我们就得到了 n n n个等式方程，再加上 g ( x 1 , x 2 , . . . , x n ) = 0 g(x\_1, x\_2,...,x\_n)=0 g(x1,x2,...,xn)=0一起构成 n + 1 n+1 n\+1个方程的方程组，未知数为 \[ x 1 , x 2 , . . . , x n , λ \] \[x\_1,x\_2,...,x\_n,\\lambda\] \[x1,x2,...,xn,λ\]共 n + 1 n+1 n\+1个，方程组的解即为所有极值点和鞍点的集合，每组解中的 λ \\lambda λ即为两个平行法向量的倍数，该值在等式约束轨迹穿过 y y y的极值点时为0。

#### 多个等式约束 ####

> 原理与单个等式约束情况类似
> 
> 考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x\_1, x\_2,...,x\_n) y=f(x1,x2,...,xn)，在 m m m个等式约束( g i ( x 1 , x 2 , . . . , x n ) = 0 , 1 ≤ i ≤ m g\_i(x\_1, x\_2,...,x\_n)=0, 1 \\le i \\le m gi(x1,x2,...,xn)=0,1≤i≤m) 下的极值点求解问题

*   n n n维空间由 m m m个条件约束，会确定一个 n − m n-m n−m维的曲面，我们讨论 y y y在这个曲面上的极值问题
 *  这个曲面由 m m m个 n − 1 n-1 n−1维曲面交织而成，存在 m m m个法向量，这 m m m个法向量构成了 n − m n-m n−m维曲面的法空间
 *  在问题的极值点， y y y的法向量必然落在 n − m n-m n−m维曲面的法空间之内，也就是说 y y y的法向量可以由 n − m n-m n−m维曲面的 m m m个法向量的线性组合表示：

\[ ∂ y ∂ x 1 , ∂ y ∂ x 2 , . . . , ∂ y ∂ x n \] + ∑ i = 1 m λ i \[ ∂ g i ∂ x 1 , ∂ g i ∂ x 2 , . . . , ∂ g i ∂ x n \] = 0 \[\\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_1\}\}\},\\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_2\}\}\},...,\\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_n\}\}\}\] + \\sum\\limits\_\{i = 1\}^m \{ \{\\lambda \_i\}\[\\frac\{ \{\\partial \{g\_i\}\}\}\{ \{\\partial \{x\_1\}\}\},\\frac\{ \{\\partial \{g\_i\}\}\}\{ \{\\partial \{x\_2\}\}\},...,\\frac\{ \{\\partial \{g\_i\}\}\}\{ \{\\partial \{x\_n\}\}\}\]\} = 0 \[∂x1∂y,∂x2∂y,...,∂xn∂y\]\+i=1∑mλi\[∂x1∂gi,∂x2∂gi,...,∂xn∂gi\]=0

*  即：

∂ y ∂ x j + ∑ i = 1 m λ i ∂ g i ∂ x j = 0 , 1 ≤ j ≤ n \\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_j\}\}\} + \\sum\\limits\_\{i = 1\}^m \{ \{\\lambda \_i\}\\frac\{ \{\\partial \{g\_i\}\}\}\{ \{\\partial \{x\_j\}\}\}\} = 0,1 \\le j \\le n ∂xj∂y\+i=1∑mλi∂xj∂gi=0,1≤j≤n

*  此时我们得到了 n n n个等式方程，再加上 m m m个等式约束( g i ( x 1 , x 2 , . . . , x n ) = 0 , 1 ≤ i ≤ m g\_i(x\_1, x\_2,...,x\_n)=0, 1 \\le i \\le m gi(x1,x2,...,xn)=0,1≤i≤m) 一起构成 n + m n+m n\+m个方程的方程组，未知数为 \[ x 1 , x 2 , . . . , x n , λ 1 , λ 2 , . . . , λ m \] \[x\_1,x\_2,...,x\_n,\\lambda\_1,\\lambda\_2,...,\\lambda\_m\] \[x1,x2,...,xn,λ1,λ2,...,λm\]共 n + m n+m n\+m个，方程组的解即为所有极值点和鞍点的集合，每组解中的 λ i \\lambda\_i λi的值即为 y y y的法向量在 n − m n-m n−m维曲面的法空间中的线性组合系数。

#### 单个不等式约束 ####

> 不等式约束其实是等式约束的扩展，等式约束表示一组确定的等高线（面），不等式约束则表示等高线（面）的某一边区域
> 
> 考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x\_1, x\_2,...,x\_n) y=f(x1,x2,...,xn)，在不等式约束 g ( x 1 , x 2 , . . . , x n ) ≤ 0 g(x\_1, x\_2,...,x\_n) \\le 0 g(x1,x2,...,xn)≤0 下的极值点求解问题

*  若该问题有解，那么有两种情况

1. 解在 g ( x 1 , x 2 , . . . , x n ) = 0 g(x\_1, x\_2,...,x\_n) = 0 g(x1,x2,...,xn)=0 曲面上
2. 解在 g ( x 1 , x 2 , . . . , x n ) < 0 g(x\_1, x\_2,...,x\_n) < 0 g(x1,x2,...,xn)<0 范围内

* 当解在 g ( x 1 , x 2 , . . . , x n ) = 0 g(x\_1, x\_2,...,x\_n) = 0 g(x1,x2,...,xn)=0 曲面上时，说明该不等式对 y y y取最小值的区域进行了限制，最终解落在了 y y y和约束相切的位置，那么此时二者的法向量方向必然相反（否则 y y y会在 g ( x 1 , x 2 , . . . , x n ) < 0 g(x\_1, x\_2,...,x\_n) < 0 g(x1,x2,...,xn)<0 范围内找到更小的值），按照等式情况构建方程：

* 便有结论： λ ≥ 0 \\lambda \\ge 0 λ≥0
 * 当解在 g ( x 1 , x 2 , . . . , x n ) < 0 g(x\_1, x\_2,...,x\_n) < 0 g(x1,x2,...,xn)<0 范围内时，事实上这个不等式没有对 y y y的求解起到约束作用，此时相当于 λ = 0 \\lambda = 0 λ=0
 * 而且两种情况下分别有 g ( x 1 , x 2 , . . . , x n ) = 0 g(x\_1, x\_2,...,x\_n) = 0 g(x1,x2,...,xn)=0和 λ = 0 \\lambda = 0 λ=0，也就是二者必有一方为0
 * 因此对于单个不等式约束的拉格朗日乘数法，仅需增加限制条件： λ ≥ 0 \\lambda \\ge 0 λ≥0和 λ g ( x 1 , x 2 , . . . , x n ) = 0 \\lambda g(x\_1, x\_2,...,x\_n) = 0 λg(x1,x2,...,xn)=0

#### 多个不等式约束 ####

> 考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x\_1, x\_2,...,x\_n) y=f(x1,x2,...,xn)，在 m m m个不等式约束( g i ( x 1 , x 2 , . . . , x n ) ≤ 0 , 1 ≤ i ≤ m g\_i(x\_1, x\_2,...,x\_n)\\le0, 1 \\le i \\le m gi(x1,x2,...,xn)≤0,1≤i≤m) 下的极值点求解问题

*  本质上与单个不等式约束相同，只是数量变多了
 *  此情况下需要在等式拉格朗日乘数法基础上增加条件：

λ i ≥ 0 , 1 ≤ i ≤ m λ i g i = 0 , 1 ≤ i ≤ m \\begin\{aligned\} \\lambda\_i &\\ge 0,1 \\le i \\le m\\\\ \\lambda\_ig\_i &= 0,1 \\le i \\le m \\end\{aligned\} λiλigi≥0,1≤i≤m=0,1≤i≤m

### 算法描述 ###

*  基于上述原理，提出了拉格朗日乘数法：

1.  考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x\_1, x\_2,...,x\_n) y=f(x1,x2,...,xn)，在 m 1 m\_1 m1个等式约束( g i ( x 1 , x 2 , . . . , x n ) = 0 , 1 ≤ i ≤ m 1 g\_i(x\_1, x\_2,...,x\_n)=0, 1 \\le i \\le m\_1 gi(x1,x2,...,xn)=0,1≤i≤m1) 、 m 2 m\_2 m2个不等式约束( h j ( x 1 , x 2 , . . . , x n ) ≤ 0 , 1 ≤ j ≤ m 2 h\_j(x\_1, x\_2,...,x\_n)\\le0, 1 \\le j \\le m\_2 hj(x1,x2,...,xn)≤0,1≤j≤m2) 下的极值点求解问题
2.  加入常数 λ , μ \\lambda,\\mu λ,μ构造方程：

z = f ( x 1 , x 2 , . . . , x n ) + ∑ i = 1 m 1 λ i g i ( x 1 , x 2 , . . . , x n ) + ∑ j = 1 m 2 μ j h j ( x 1 , x 2 , . . . , x n ) z = f(\{x\_1\},\{x\_2\},...,\{x\_n\}) + \\sum\\limits\_\{i = 1\}^\{ \{m\_1\}\} \{ \{\\lambda \_i\}\{g\_i\}(\{x\_1\},\{x\_2\},...,\{x\_n\})\} + \\sum\\limits\_\{j = 1\}^\{ \{m\_2\}\} \{ \{\\mu \_j\}\{h\_j\}(\{x\_1\},\{x\_2\},...,\{x\_n\})\} z=f(x1,x2,...,xn)\+i=1∑m1λigi(x1,x2,...,xn)\+j=1∑m2μjhj(x1,x2,...,xn)

1.  对所有变量求偏导，并令导数为0：

∂ z ∂ x i = 0 ∂ y ∂ x k + ∑ i = 1 m 1 λ i ∂ g ∂ x k + ∑ j = 1 m 1 μ j ∂ h ∂ x k = 0 \\begin\{aligned\} \\frac\{ \{\\partial z\}\}\{ \{\\partial \{x\_i\}\}\} &= 0\\\\ \\frac\{ \{\\partial y\}\}\{ \{\\partial \{x\_k\}\}\} + \\sum\\limits\_\{i = 1\}^\{ \{m\_1\}\} \{ \{\\lambda \_i\}\\frac\{ \{\\partial g\}\}\{ \{\\partial \{x\_k\}\}\}\} + \\sum\\limits\_\{j = 1\}^\{ \{m\_1\}\} \{ \{\\mu \_j\}\\frac\{ \{\\partial h\}\}\{ \{\\partial \{x\_k\}\}\}\} \{\\rm\{ \}\} &= 0 \\end\{aligned\} ∂xi∂z∂xk∂y\+i=1∑m1λi∂xk∂g\+j=1∑m1μj∂xk∂h=0=0

> 其中： 1 ≤ k ≤ n 1 \\le k \\le n 1≤k≤n

1.  将上述 n n n个方程与 m 1 m\_1 m1个等式约束方程 g i ( x 1 , x 2 , . . . , x n ) = 0 , 1 ≤ i ≤ m 1 g\_i(x\_1, x\_2,...,x\_n)=0, 1 \\le i \\le m\_1 gi(x1,x2,...,xn)=0,1≤i≤m1 联立
2.  将上述 n + m 1 n+m\_1 n\+m1个方程与 μ j h j = 0 , 1 ≤ j ≤ m 2 \\mu\_j h\_j=0, 1 \\le j \\le m\_2 μjhj=0,1≤j≤m2联立，得到 n + m 1 + m 2 n+m\_1+m\_2 n\+m1\+m2个方程
3.  加上限制条件 μ j ≥ 0 \\mu\_j \\ge 0 μj≥0， h j ≤ 0 h\_j \\le 0 hj≤0 , 1 ≤ j ≤ m 2 , 1 \\le j \\le m\_2 ,1≤j≤m2
4.  在限制条件下解 n + m 1 + m 2 n+m\_1+m\_2 n\+m1\+m2元方程即可得到极值点与鞍点集合
5.  从所有解中筛选出极值点

### KKT条件 ###

*  上述 n + m 1 + m 2 n+m\_1+m\_2 n\+m1\+m2元方程与限制条件即为`KKT条件`
 *  `KKT`条件是拉格朗日函数取极值时的必要条件

\{ ∇ f + ∑ i m 1 λ i ∇ g i + ∑ j m 2 μ j ∇ h j = 0 g i = 0 , h j ≤ 0 , μ j ≥ 0 , μ j h j = 0 \\left\\\{\\begin\{array\}\{l\} \\nabla f+\\sum\_\{i\}^\{m\_1\} \\lambda\_\{i\} \\nabla g\_\{i\}+\\sum\_\{j\}^\{m\_2\} \\mu\_\{j\} \\nabla h\_\{j\}=0 \\\\ g\_\{i\}=0, \\\\ h\_\{j\} \\leq 0, \\\\ \\mu\_\{j\} \\geq 0, \\\\ \\mu\_\{j\} h\_\{j\}=0\\\\ \\end\{array\}\\right. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧∇f\+∑im1λi∇gi\+∑jm2μj∇hj=0gi=0,hj≤0,μj≥0,μjhj=0

> 其中  i ∈ \{ 1 , 2 , ⋯   , m 1 \} i \\in \\\{ 1,2, \\cdots, m\_1\\\} i∈\{ 1,2,⋯,m1\} ， j ∈ \{ 1 , 2 , ⋯   , m 2 \} j \\in \\\{ 1,2, \\cdots, m\_2\\\} j∈\{ 1,2,⋯,m2\}

*  总结一下所有条件的含义：

<table> 
 <thead> 
 <tr> 
 <th>内容</th> 
 <th>含义</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> ∇ f + ∑ i m 1 λ i ∇ g i + ∑ j m 2 μ j ∇ h j = 0 \nabla f+\sum_{i}^{m_1} \lambda_{i} \nabla g_{i}+\sum_{j}^{m_2} \mu_{j} \nabla h_{j}=0 ∇f+∑im1λi∇gi+∑jm2μj∇hj=0</td> 
 <td>求解极值需要在各个自变量方向上导数为0</td> 
 </tr> 
 <tr> 
 <td> g i = 0 g_{i}=0 gi=0</td> 
 <td>等式约束</td> 
 </tr> 
 <tr> 
 <td> h j ≤ 0 h_{j} \le 0 hj≤0</td> 
 <td>不等式约束</td> 
 </tr> 
 <tr> 
 <td> μ j ≥ 0 \mu_{j} \geq 0 μj≥0</td> 
 <td>不等式约束时的两种情况： 1. 不等式约束无效( μ j = 0 \mu_{j} = 0 μj=0) 2. 不等式分界面法向量与原函数法向量方向相反( μ j &gt; 0 \mu_{j} &gt; 0 μj&gt;0)</td> 
 </tr> 
 <tr> 
 <td> μ j h j = 0 \mu_{j} h_{j}=0 μjhj=0</td> 
 <td>不等式约束时的两种情况： 1. 不等式约束无效，极值点在 h j &lt; 0 h_{j} &lt; 0 hj&lt;0范围内 ( μ j = 0 \mu_{j} = 0 μj=0) 2. 不等式约束有效，极值点在 h j = 0 h_{j} = 0 hj=0曲面上( h j = 0 h_{j} = 0 hj=0)</td> 
 </tr> 
 </tbody> 
</table>

### 参考资料 ###

*  https://baike.baidu.com/item/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0%E6%B3%95/8550443?fr=aladdin
 *  https://www.zhihu.com/question/38586401
 *  https://www.zhihu.com/question/359162625
 *  https://www.zhihu.com/question/23311674/answer/468804362
 *  https://blog.csdn.net/johnnyconstantine/article/details/46335763

[Link 1]: https://baike.baidu.com/item/%E9%97%AE%E9%A2%98/1067365
[Link 2]: https://baike.baidu.com/item/%E7%BA%A6%E7%91%9F%E5%A4%AB%C2%B7%E8%B7%AF%E6%98%93%E6%96%AF%C2%B7%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5/7070424
[Link 3]: https://baike.baidu.com/item/%E5%A4%9A%E5%85%83%E5%87%BD%E6%95%B0/2498728
[Link 4]: https://baike.baidu.com/item/%E6%9E%81%E5%80%BC/5330918
[Link 5]: https://baike.baidu.com/item/%E7%BA%A6%E6%9D%9F%E6%9D%A1%E4%BB%B6/1046571
[Link 6]: https://baike.baidu.com/item/%E6%9C%80%E4%BC%98%E5%8C%96%E9%97%AE%E9%A2%98/9632567
[0a97dc9fb0ee9b73e75bb14d76542888.png]: /images/20221022/c9dddea91ae74f03806835888147bc48.png