机器学习基础：拉格朗日乘子法

在凸优化问题中，拉格朗日乘子法是最常用的方法之一。

先看个例题：求目标函数 $\mathrm{f}(\mathrm{x},\mathrm{y})={\mathrm{x}}^2+{\mathrm{y}}^2$，在约束条件$\mathrm{xy}=3$下的最小值。

这是一个典型的约束优化问题，根据我们中学知识，首先想到的是一个变量用另外一个变量进行替换，再带入目标函数就可以求出极值。

将$y=\frac{3}{x}$带入$\mathrm{f}(\mathrm{x},\mathrm{y})={\mathrm{x}}^2+{\mathrm{y}}^2$ ，可得 $\mathrm{f}(\mathrm{x})={\mathrm{x}}^2+\frac{9}{{\mathrm{x}}^2}，然后求\mathrm{f}(\mathrm{x})$的最小值。
这就变成了求一元函数的无约束极值。求导，${\mathrm{f}}^{\prime }(\mathrm{x})=0$的点即为极值点。推导可得，在点$(\sqrt{3},\sqrt{3})$和点$(-\sqrt{3},-\sqrt{3})$处，$\mathrm{f}(\mathrm{x},\mathrm{y})$的最小值为6 。

更直观一些，将 ${\mathrm{x}}^2+{\mathrm{y}}^2=\mathrm{c}$的曲线族画出来，如图所示，当曲线族中的圆与$xy=3$ 曲线相切时，切点到原点的距离最短。也就是说，$f(x,y)=c$的等高线和双曲线$g(x,y)$相切时，可以得到上述优化问题的一个极值。那么，当$\mathrm{f}(\mathrm{x},\mathrm{y})$和$\mathrm{g}(\mathrm{x},\mathrm{y})$ 相切时，$x,y$的值是多少呢? 该如何求解呢?

在讨论梯度概念时，梯度与等高线的关系描述如下：函数$z=f(x,y)$ 在点$(x_0,y_0)$梯度方向与过点$(x_0,y_0)$的等高线$f(x,y)=c$在这点的法线方向相同，且从数值较低的等高线指向数值较高等高线，而梯度的模等于函数在这个法线方向的方向导数。这个法线方向就是方向导数取得最大值的方向。

根据梯度与等高线的关系描述，上面问题中$f(x,y)$和$g(x,y)$相切时，它们的切线相同，即法向量是相互平行的，因此，可以得到$▽f(x,y)=-\lambda \cdot ▽g(x,y)$ 。分别求偏导，并且加上约束条件 $xy=3$，可以得到方程组：
$$\{\begin{array}{l}\frac{\partial f}{\partial x}=-\lambda \frac{\partial g}{\partial x}\\ \frac{\partial f}{\partial y}=-\lambda \frac{\partial g}{\partial y}\\ xy=3\end{array}$$
即:

$$\{\begin{array}{l}2x=-\lambda y\\ 2y=-\lambda x\\ xy=3\end{array}$$
求解结果:$\mathrm{x}=\sqrt{3},\mathrm{y}=\sqrt{3},\lambda =-2$ 或者 $\mathrm{x}=-\sqrt{3},\mathrm{y}=-\sqrt{3},\lambda =-2$ 通过上述例子引入拉格朗日乘子法的基本原理，即通过引入拉格朗日乘子$\lambda$ 将原来的约束优化问题转化为无约束的方程组问题。

一般步骤

1. 求解函数$\mathrm{u}=\mathrm{f}(\mathrm{x},\mathrm{y},\mathrm{z},\mathrm{t})$ 在条件$\phi (\mathrm{x},\mathrm{y},\mathrm{z},\mathrm{t})=0,\psi (\mathrm{x},\mathrm{y},\mathrm{z},\mathrm{t})=0$下极值。
2. 构造函数:$\mathrm{F}\left(\mathrm{x},\mathrm{y},\mathrm{z},\mathrm{t},{\lambda }_1,{\lambda }_2\right)=\mathrm{f}(\mathrm{x},\mathrm{y},\mathrm{z},\mathrm{t})+{\lambda }_1\cdot \phi (\mathrm{x},\mathrm{y},\mathrm{z},\mathrm{t})+{\lambda }_2\cdot \psi (\mathrm{x},\mathrm{y},\mathrm{z},\mathrm{t})$ ，其中，${\lambda }_1$、${\lambda }_2$ 为拉格朗日乘子
3. 通过对构造函数求偏导为 0 列出方程组。
4. 求出方程组的解，带入即可得目标函数的极值。

【例】已知目标函数为$\mathrm{V}(\mathrm{x},\mathrm{y},\mathrm{z})=\mathrm{xyz}$，在约束条件$2\mathrm{xy}+2\mathrm{xz}+2\mathrm{yz}=12$下，求体积$\mathrm{V}$的最大值。
解: $F(x,y,z,\lambda )=x^3{y}^{2}z+\lambda \cdot (x+y+z-12)$

求偏导可得方程组
$$\{\begin{array}{l}3x^2{y}^{2}z+\lambda =0\\ 2x^{3}yz+\lambda =0\\ x^3{y}^2+\lambda =0\\ x+y+z-12=0\end{array}$$
解得唯一驻点 (6,4,2), $u_{\mathrm{mux}}=6912$ 。

由凸优化问题我们知道：

例如要求解${\min }_{x}f(x)$，那么就是解方程 $\nabla f(x)=0$，最终的 $x^{\ast }$ 为最优解。

那么当有约束条件怎么呢？

拉格朗日法就是把一个有约束问题转换成一个无约束问题

优化问题一般有以下几种形式
$$\begin{array}{cllllll}{\min }_x& f_0(x)& {\min }_x& f_0(x)& {\max }_x& f_0(x)& \\ \text{ s.t. }& f_i(x)\le 0,i=1,\dots ,m& \text{ s.t. }& f_i(x)\ge 0,i=1,\dots ,m& \text{ s.t. }& f_i(x)\le 0,i=1,\dots ,m& \\ & h_i(x)=0,i=1,\dots ,p& & h_i(x)=0,i=1,\dots ,p& & h_i(x)=0,i=1,\dots ,p& \end{array}$$
最常用的是第一种，求最小值，约束为小于等于。

对于仅含等式约束的优化问题：
$$\begin{array}{cl}\min & f(\mathbf{x})\\ \text{ s.t. }& h_i(\mathbf{x})=0i=1,2,\dots ,n\end{array}$$
其中自变量 $\mathbf{x}\in {\mathbb{R}}^n,f(\mathbf{x})$ 和 $h_i(\mathbf{x})$ 均有连续的一阶偏导数。首先列出其拉格朗日函数：

$$L(\mathbf{x},\mathbf{\lambda })=f(\mathbf{x})+\sum _{i=1}^n{\lambda }_i{h}_i(\mathbf{x})$$

其中$\mathbf{\lambda }={\left({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\right)}^{\mathrm{T}}$ 为拉格朗日乘子。然后对拉格朗日函数关于 $\mathbf{x}$ 求偏导，并令导数等于0再搭配约束条件 $h_i(\mathbf{x})=0$ 解出 $\mathbf{x}$, 求解出的所有$\mathbf{x}$ 即为上述优化问题的所有可能极值点。

拉格朗日函数与原始问题的关系
$$\begin{array}{cl}{\min }_x& f_0(x)\\ \text{ s.t. }& f_i(x)\le 0,i=1,\dots ,m\\ & h_i(x)=0,i=1,\dots ,p\end{array}$$
对应上面优化问题可以写为如下形式：
$$\begin{array}{rl}\mathcal{L}(x,\lambda ,\nu )& =f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x)\\ \text{ s.t. }& {\lambda }_i\ge 0,i=1,\dots ,m\end{array}$$
${\lambda }_i$和$v_i$是两个拉格朗日乘子，由于$f_i(x)$是不等式约束，所以${\lambda }_i$有约束条件必须大于0；$h_i(x)$是等式约束，$v_i$没有约束。

上面式子等价于这个式子：
$$\begin{array}{rl}{\min }_x{\max }_{\lambda ,v}& \mathcal{L}(x,\lambda ,\nu )\\ \text{ s.t. }& {\lambda }_i\ge 0,i=1,\dots ,m\end{array}$$
【证明两式等价：】

记
$$\begin{gathered} {\theta }_p(x)=\underset{\lambda ,v}{\max }\mathcal{L}(x,\lambda ,\nu ) \\ s.t.{\lambda }_i\ge 0,i=1,\dots ,m \end{gathered}$$
则${\theta }_P(x)$y有以下性质：
$${\theta }_P(x)=\{\begin{array}{ll}{f}_0(x)& \text{ for }x\text{ that satisfied the origin constraint }\\ +\infty & \text{ otherwise }\end{array}$$
验证上述性质：

1. 若存在 x 使得某个 $f_i(x)>0$ 则我们可令 $0\le {\lambda }_i$ $\to +\infty$ , 进而有 ${\theta }_p(x)=+\infty$
2. 若存在 x 使得某个 $h_i(x)\ne 0$ 则我们可令 $v_i{h}_i(x)\to +\infty$ , 进而有 ${\theta }_p(x)=+\infty$
3. 若 x ∈ { x ∣ ∀ i , v i , λ i ≥ 0 , λ i f i ( x ) ≤ 0 , v i h i ( x ) = 0 } x \in\left\{x \mid \forall i, v_{i}, \lambda_{i} \geq 0, \lambda_{i} f_{i}(x) \leq 0, v_{i} h_{i}(x)=0\right\} x∈{x∣∀i,vi​,λi​≥0,λi​fi​(x)≤0,vi​hi​(x)=0} 则有 ${\max }_{\lambda ,v}\mathcal{L}(x,\lambda ,\nu )=f_0(x)$