拉格朗日乘数法

本文最后更新于：2024年5月7日下午

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

概述

我们擅长解决的是无约束极值求解问题，这类问题仅需对所有变量求偏导，使得所有偏导数为0，即可找到所有极值点和鞍点。我们解决带约束条件的问题时便会尝试将其转化为无约束优化问题
假设我们要优化 $f(\bf x)$, 对于等式约束 $g(\bf x)=0$，事实上如果我们可以得到某个变量的表示，例如 $x_1 = t(x_2, …, x_n)$，将该式带入 $f$ 即可抓换为无约束优化（初高中就是这么做的，所谓消元法是也），但有的时候我们无法得到这样的表示，便需要借助拉格朗日乘数法来避免消元法的困境。
对于不等式约束$h(\bf x) \le0$，处理起来就较为麻烦，因为不确定最终的最优解是出在不等式的边界还是内部，如果在边界上则为等式约束，在范围内则可以略去这个不等式约束，也就是说需要对不等式约束作出选择。

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

拉格朗日乘数法的思想

以可导的二元函数为例，高维时同理

等式约束

考虑处处可微的二元函数 $f(x,y)$，在可导约束 $g(x,y)=c$ 下的极值，即 $f(x,y)$ 需要在 $g(x,y)=c$ 曲线上运动，选择极值
首先我们可以绘制出 $f(x,y)$ 的一层层等高线，当等高线与 $g(x,y)=c$ 相切（导数向量共线）时即可能是该问题的极值点：

我们简单反正一下：
- 假设在 $g(x,y)=c$ 上非相切时取到极值点
- 那么 $f(x,y)$ 场在 $g(x,y)=c$ 曲线上的导数向量投影非零，即在该点周围运动时会变大也会变小
- 与该点为极值这一假设矛盾
- 因此在等式约束下，$f(x,y)$ 取极值时等高线必定与等式约束曲线相切

不等式约束

约束选择

考虑处处可微的二元函数 $f(x,y)$，在可导约束 $g_1(x,y)\le 0$ 和 $g_2(x,y)\le 0$ 下的极值，即 $f(x,y)$ 需要在两条线 $g_1(x,y)= 0$ 和 $g_2(x,y)= 0$ 的某一侧中的点中选择极值
如上图所示灰色部分为可行区域，假设当前的函数 $f$ 和上文等式约束相同， $g_1(x,y)= 0$ 和上文 $g(x,y)=c$ 曲线相同，那么事实上极值点仍然是同一个点 $A$，也就是说，此时虽然求解的是 $f(x,y)$ 在多个不等式约束下的极值求解问题，但是$g_2(x,y)$ 并没有起什么作用，起作用的是 $g_1(x,y)=0$ 的等式约束部分
拉格朗日乘数在解决不等式约束问题时，本质上做的就是选择真正有效的不等式约束（图中的$g_1$），将其当成等式约束（ $g_1(x,y)=0$），最终的解就会在选择的等式约束线上，没有被选择的不等式（$g_2$）则被放弃（就相当于没有）。

法线方向

在解决等式约束问题时，仅需等高线和曲线相切（法线共线）即可，但面对不等式约束时要求稍微严格一点

在不等式约束中，极值点的解处等高线和不等式分界曲线是相切的，同时需要优化方向必须指向可行区域相反的方向
优化方向指可以最小化或最大化 $f(x,y)$，前进时最能满足优化目标的方向为优化方向，当最大化时为导数方向，最小化时为导数的反方向

简单反证一下
- 假设 $f(x,y)$ 在不等式约束 $g_1(x,y)\le 0$ 下的解为 $A$ ，且此时两个曲线相切，但是优化方向指向可行区域
- 即此时朝着可行区域前进既可以更加优化目标，那么当前的 $A$ 自然不是最优解
在拉格朗日标准形式中，会规定$f(x)$ 的优化方式为 $\min$ ，同时不等式约束均为 $g(x) \le 0$，在这种规定下，在最优解处不等式曲线的梯度方向与$f(x)$ 的等高线的梯度方向必定共线且方向相反，这就是不等式约束前的拉格朗日系数必须非负的来源

拉格朗日乘数法

单个等式约束

考虑最小化 $n$ 元函数$y=f(x_1, x_2,…,x_n)$，在等式约束 $g(x_1, x_2,…,x_n)=0$ 下的极值点求解问题

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

$$ [\frac{{\partial y}}{{\partial {x_1}}},\frac{{\partial y}}{{\partial {x_2}}},...,\frac{{\partial y}}{{\partial {x_n}}}] $$

$g$的法向量为：

$$ [\frac{{\partial g}}{{\partial {x_1}}},\frac{{\partial g}}{{\partial {x_2}}},...,\frac{{\partial g}}{{\partial {x_n}}}] $$

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

$$ [\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 $$

即：

$$ \frac{{\partial y}}{{\partial {x_i}}} + \lambda \frac{{\partial g}}{{\partial {x_i}}} = 0,1 \le i \le n $$

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

多个等式约束

原理与单个等式约束情况类似

考虑最小化 $n$ 元函数$y=f(x_1, x_2,…,x_n)$，在$m$个等式约束($g_i(x_1, x_2,…,x_n)=0, 1 \le i \le m$) 下的极值点求解问题

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

$$ [\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 $$

即：

$$ \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 $$

此时我们得到了$n$个等式方程，再加上$m$个等式约束($g_i(x_1, x_2,…,x_n)=0, 1 \le i \le m$) 一起构成$n+m$个方程的方程组，未知数为$[x_1,x_2,…,x_n,\lambda_1,\lambda_2,…,\lambda_m]$共$n+m$个，方程组的解即为所有极值点和鞍点的集合，每组解中的$\lambda_i$的值即为$y$的法向量在$n-m$维曲面的法空间中的线性组合系数。

单个不等式约束

不等式约束其实是等式约束的扩展，等式约束表示一组确定的等高线（面），不等式约束则表示等高线（面）的某一边区域

考虑最小化 $n$ 元函数 $y=f(x_1, x_2,…,x_n)$，在不等式约束$g(x_1, x_2,…,x_n) \le 0$ 下的极值点求解问题

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

解在 $g(x_1, x_2,…,x_n) = 0$ 曲面上
解在$g(x_1, x_2,…,x_n) < 0$ 范围内

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

$$ \frac{{\partial y}}{{\partial {x_i}}} + \lambda \frac{{\partial g}}{{\partial {x_i}}} = 0,1 \le i \le n $$

便有结论：$\lambda \ge 0$
当解在$g(x_1, x_2,…,x_n) < 0$ 范围内时，事实上这个不等式没有对 $y$ 的求解起到约束作用，此时相当于$\lambda = 0$
而且两种情况下分别有 $g(x_1, x_2,…,x_n) = 0$和$\lambda = 0$，也就是二者必有一方为0
因此对于单个不等式约束的拉格朗日乘数法，仅需增加限制条件： $\lambda \ge 0$和$\lambda g(x_1, x_2,…,x_n) = 0$
此 $\lambda$ 的物理含义为：
- $\lambda=0$：该不等式约束没有发挥限制作用
- $\lambda>0$： $f$ 函数等高线和不等式曲线相切的法线模长的比例

多个不等式约束

考虑最小化 $n$ 元函数$y=f(x_1, x_2,…,x_n)$，在$m$个不等式约束($g_i(x_1, x_2,…,x_n)\le0, 1 \le i \le m$) 下的极值点求解问题

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

$$ \begin{aligned} \lambda_i &\ge 0,1 \le i \le m\\ \lambda_ig_i &= 0,1 \le i \le m \end{aligned} $$

算法描述

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

考虑$n$元函数$y=f(x_1, x_2,…,x_n)$，在$m_1$个等式约束($g_i(x_1, x_2,…,x_n)=0, 1 \le i \le m_1$) 、$m_2$个不等式约束($h_j(x_1, x_2,…,x_n)\le0, 1 \le j \le m_2$) 下的极值点求解问题
加入常数$\lambda,\mu$构造方程：

$$ 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})} $$

对所有变量求偏导，并令导数为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} $$

其中：$1 \le k \le n$

将上述$n$个方程与$m_1$个等式约束方程$g_i(x_1, x_2,…,x_n)=0, 1 \le i \le m_1$ 联立
将上述$n+m_1$个方程与$\mu_j h_j=0, 1 \le j \le m_2$联立，得到$n+m_1+m_2$个方程
加上限制条件$\mu_j \ge 0$，$h_j \le 0$$, 1 \le j \le m_2$
在限制条件下解$n+m_1+m_2$元方程即可得到极值点与鞍点集合
从所有解中筛选出极值点

拉格朗日方程的本质

算法中很神奇的地方是引入了拉格朗日方程

$$ 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})} $$

此步骤的本质是需要选择不等式约束，加入切线模长比例这一事实上存在的量来构造可解的方程
形式上为在$\lambda,\mu$ 可变的情况下最大化拉格朗日函数 $z$，同时满足 $\mu \geq0$

$$
\max_{\lambda,\mu;\mu\geq0} z
$$

那么对 $\lambda, \mu$ 求偏导，可以看到 $\lambda$ 的导数为 0，我们做不了什么
$\mu$ 的导数非正，那么：
当导数为负时为了最大化 $z$ 需要令 $\mu$ 尽可能小，而 $\mu \geq 0$，因此 $\mu=0$
当导数为 0 时该约束就变成了等式约束，但需要限定法线方向，因此 $\mu > 0$
这就达到了介绍思想时的目的，个人觉得此时最大化 $z$ 仅仅因为这种优化可以达到目的，是一种凑出来但是确实很巧妙的形式
在完成在$\lambda,\mu$ 下最大化 $z$ 后，$z$ 又变回了 $f$ （因为其余项都变为了0）
此时再按照原始目标在原始定义域 $\bf x$ 上进行最小化即可，因此原始拉格朗日问题的过程为：

$$
{\bf x}^*=\min_{\bf x} \max_{\lambda,\mu;\mu\geq0} z
$$

KKT条件

上述$n+m_1+m_2$元方程与限制条件即为KKT条件
KKT条件是拉格朗日函数取极值时的必要条件

$$ \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. $$

其中 $i \in { 1,2, \cdots, m_1}$ ，$j \in { 1,2, \cdots, m_2}$

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

内容	含义
$\nabla f+\sum_{i}^{m_1} \lambda_{i} \nabla g_{i}+\sum_{j}^{m_2} \mu_{j} \nabla h_{j}=0$	求解极值需要在各个自变量方向上导数为0
$g_{i}=0$	等式约束
$h_{j} \le 0$	不等式约束
$\mu_{j} \geq 0$	不等式约束时的两种情况： 1. 不等式约束无效($\mu_{j} = 0$) 2. 不等式分界面法向量与原函数法向量方向相反($\mu_{j} > 0$)
$\mu_{j} h_{j}=0$	不等式约束时的两种情况： 1. 不等式约束无效，极值点在$h_{j} < 0$范围内 ($\mu_{j} = 0$) 2. 不等式约束有效，极值点在$h_{j} = 0$曲面上($h_{j} = 0$)