A 拉格朗日乘数法

A1 单等式约束条件的拉格朗日乘数法

要求极值点的 $N$ 元目标函数为 $f(\boldsymbol x)$($f: \R^N \to \R$),存在单个约束条件为 $\phi(\boldsymbol x) = 0$ ($\phi: \R^N \to \R$),要求二者都拥有连续的一阶导数。

引入拉格朗日乘子 $\lambda$,作拉格朗日函数:

$$ F(\boldsymbol x, \lambda) = f(\boldsymbol x)+\lambda \phi(\boldsymbol x) $$

寻求令 $F(\boldsymbol x, \lambda)$ 一阶导数全为 $0$ 的驻点 $\boldsymbol x^, \lambda^$,即求解如下 $N+1$ 个方程构成的方程组:

$$ \begin{cases}

\frac{\partial F(\boldsymbol x, \lambda)}{\partial \boldsymbol x} = \frac{\partial f(\boldsymbol x)}{\partial \boldsymbol x} + \lambda \frac{\partial \phi(\boldsymbol x)}{\partial \boldsymbol x} = \boldsymbol 0 \\

\frac{\partial F(\boldsymbol x, \lambda)}{\partial \lambda} = \phi(\boldsymbol x) = 0

\end{cases} \tag{*} $$

Untitled

解方程组得到驻点 $\boldsymbol x^, \lambda^$,其中 $\boldsymbol x^*$ 即为 $f(\boldsymbol x)$ 在 $\phi(\boldsymbol x)=0$ 时的极值点。

拉格朗日乘数法的根本是大括号($(*)$ 式)内的两个公式,其中第一个式子表示满足目标函数 $f$ 的一阶导数和约束函数 $\phi$ 的一阶导数共线的所有 $\boldsymbol x$ 位置,第二个式子表示满足约束条件的所有 $\boldsymbol x$ 位置,能同时符合这两个条件的 $\boldsymbol x$ 位置,即为求得的极值点。

举一个 $N=2$ 的例子,其中 $f$ 是一个平面,直接用蓝绿色平面表示;$\phi=0$ 是椭圆抛物面截出的一个等高线,是单位圆,下图展示的是其沿 $z$ 轴无限延长构成一个圆柱面的结果。

$$ f(x, y) = x + \frac 12 y, \ \ \ \phi(x, y) = x^2+y^2 - 1 = 0 $$

Untitled

然后我们考察平面上的等高线性质,如下图。

黄色线条是目标函数 $f$ 的等高线,蓝色线条是约束函数 $\phi$ 的等高线(其中 $\phi=0$ 用蓝色实线标注,我们要找的就是蓝色实线上的极值点)。$f, \phi$ 均具有导数(又叫梯度),如 A 处为 $\phi$ 在此处的梯度 $\phi'$,B 处为 $f$ 在此处的梯度 $f'$。可以发现,两者在绿色所示线上有共线关系(如 C, D 点处所示)(实际会写作 $f' + \lambda \phi' = 0$)。即在 $\phi=0$(蓝色实线)上、又满足梯度共线关系(绿色实线)的点,即为所求的极值点。

下面解释为什么满足这两个条件即为所求的极值点。暂不考虑 $\phi'=\boldsymbol 0$ 的点,即 $\phi'$ 一定存在方向,那么沿着方向或反着方向走一定会脱离 $\phi=0$,只有相对于 $\phi'$ 的方向微元左右走才能保持在 $\phi=0$ 的等高线上。而由于 $f'$ 和 $\phi'$ 共线,说明要么 $f'=0$,此处为 $f$ 的驻点,对各个方向而言 $f$ 不变;要么 $f'$ 与 $\phi'$ 同方向,其对此处微元左右方向而言 $f$ 不变,是极值点,因而它会是 $\phi=0$ 等高线上的极值点。

Untitled

将此例拓展到 $N=3$ 的三维空间中,$f$ 仍然根据一个恒定的梯度 $f'$ 递增,$\phi=0$ 表示一个球面(如在 $\phi(x, y, z) = x^2 + y^2 + z^2 - 1$ 时取单位圆),空间各处的梯度 $\phi'$ 垂直球心向外。可以看到,仍然是只有在 C, D 处时,存在梯度 $f', \phi'$ 共线,据此取到球面上的极值点。

Untitled

总之要注意的是,一个 $\phi(\boldsymbol x) = 0$ 只是一个 $N$ 维高维空间中的超平面或超曲面。

A2 多等式约束条件的拉格朗日乘数法

可以看到,对于 $N=3$ 的例子,约束条件构成一个面,但完全还可以再来一个条件 $\psi=0$(如紫红色所示),让约束条件取两个条件的交集,图形上即是两个面所交出的一条环线,发生了自由度的降低。

Untitled

但是此环线上就显然不存在梯度 $\phi'$ 与 $f'$ 共线一说了(只发生在 C, D 点上),更别提 $\psi'$ 又是另一个恒定量,和 $f'$ 永不共线,所以现在不能用共线做评判基准了。

这种情况下,在环线上的情况就要相应「放松」,最终得到的说法是,$f'$ 应该能由 $\phi', \psi'$ 线性表出,即 $f' = \lambda_1\phi' + \lambda_2\psi'$(实际会写作 $f' + \boldsymbol \lambda^{\rm T} \boldsymbol \phi' = 0$)。只能看图意会一下了。

Untitled

据此,将一般情形的结论介绍如下。

要求极值点的 $N$ 元目标函数为 $f(\boldsymbol x)$($f: \R^N \to \R$),存在一组 $K$ 个约束条件 $\phi_1(\boldsymbol x)=\phi_2(\boldsymbol x)=\cdots=\phi_K(\boldsymbol x)=0$ 记为 $\boldsymbol \phi(\boldsymbol x) = \boldsymbol 0$($\boldsymbol \phi: \R^N \to \R^K$),要求 $f(\boldsymbol x)$ 和 $\phi_k(\boldsymbol x)$ 都拥有连续的一阶导数。

引入拉格朗日乘子 $\boldsymbol \lambda=[\lambda_1, \lambda_2, \cdots, \lambda_K]^{\rm T}$,作拉格朗日函数:

$$ F(\boldsymbol x, \boldsymbol \lambda) = f(\boldsymbol x) + \boldsymbol \lambda^{\rm T} \boldsymbol \phi(\boldsymbol x) $$

寻求令 $F(\boldsymbol x, \boldsymbol \lambda)$ 一阶导数全为 $0$ 的驻点 $\boldsymbol x^, \boldsymbol \lambda ^$,即求解如下 $N+K$ 个方程构成的方程组:

$$ \begin{cases}

\frac{\partial F(\boldsymbol x, \boldsymbol \lambda)}{\partial \boldsymbol x} =

\frac{\partial f(\boldsymbol x)}{\partial \boldsymbol x} + \frac{\partial \boldsymbol \phi^{\rm T}(\boldsymbol x)}{\partial \boldsymbol x} \cdot \boldsymbol \lambda = \boldsymbol 0 \\

\frac{\partial F(\boldsymbol x, \boldsymbol \lambda)}{\partial \boldsymbol \lambda} = \boldsymbol \phi(\boldsymbol x) = \boldsymbol 0

\end{cases} $$