拉格朗日乘子法

拉格朗日乘子法（Lagrange Multipliers），可以将有 $d$ 个变量与 $k$ 个约束条件的最优化问题转化为具有 $d+k$ 个变量的无约束优化问题。

一、简单情况

从几何角度看，该问题的目标是在方程 $g(\boldsymbol x) = 0$ 确定的 $d-1$ 维曲面上寻找能使目标函数 $f(\boldsymbol x)$ 最小化的点，此时：

1. 对于约束曲面上的任一点 $\boldsymbol x$，该点的梯度 $\nabla g(\boldsymbol x)$ 正交于约束平面
2. 在最优点 $\boldsymbol x^*$，目标函数在该点的梯度 $\nabla f(\boldsymbol x)$ 正交于约束平面。

上述条件即函数等值线与约束曲面相切，可通过反证法证明：若梯度 $\nabla f(\boldsymbol x^*)$ 与约束曲面不正交，则仍可在约束曲面上移动该点使函数值进一步下降。

由此可知，在最优点 $\boldsymbol x^*$，梯度 $\nabla g(\boldsymbol x)$ 和 $\nabla f(\boldsymbol x)$ 的方向相同或相反，即存在 $\lambda \neq 0$ 使得：

$\lambda$ 称为拉格朗日乘子。定义拉格朗日函数：

当函数 $L(\boldsymbol x, \lambda)$ 的 Jacobian 矩阵 $J_L = \boldsymbol 0$ 时，约束条件和梯度条件同时满足。于是，原约束优化问题可转化为对拉格朗日函数 $L(\boldsymbol x, \lambda)$ 的无约束优化问题。

举个例子🌰，求椭圆 $\frac {x^2}{4} + \frac {y^2}{3} = 1$ 上到点 $(1, 1)$ 的最短距离的平方，即：

解：定义拉格朗日函数：

对应的 Jacobian 矩阵为：

可得：

可得：

可得：

可得：

根据四次方程求根公式，可解得 $x_1 \approx 1.24, x_2 \approx -1.71$。

易知 $x > 0, y > 0$，最终可求得 $x \approx 1.24, y \approx 1.36, \min f(x, y) \approx 0.19$。

上面这道题目是笔者高中的时候想到却不会解决的问题。后来大一的《工科数学分析》课程中有拉格朗日乘子法，却没有好好学习，实在惭愧。

二、不等式约束

此时最优点 $\boldsymbol x^*$ 或在 $\nabla g(\boldsymbol x) < 0$ 的区域中，可直接通过条件 $\nabla f(\boldsymbol x) = 0$ 求解，等价于将 $\lambda$ 置零后对 $\nabla _{\boldsymbol x} L(\boldsymbol x, \lambda)$ 置零得到最优点；或在边界 $\nabla g(\boldsymbol x) = 0$ 上，此时 $\nabla f(\boldsymbol x^*)$ 的方向必与 $\nabla g(\boldsymbol x^*)$ 相反，$\lambda > 0$。

整合这两种情形，必满足 $\lambda \nabla g(\boldsymbol x) = 0$。因此在约束 $g(\boldsymbol x) \le 0$ 下最小化 $f(\boldsymbol x)$，可转化为在如下约束下最小化 $L(\boldsymbol x, \lambda)$ 的拉格朗日函数：

上式称为 Karush-Kuhn-Tucker（KTT）条件。KKT 条件是原问题求解的必要条件。具体求解过程中可以分情况讨论不等式约束是否有效。

依然举个例子🌰：

解：定义拉格朗日函数：

KKT 条件为：

若 $g(x, y) = 0$，则类似简单情况求解，不再赘述；若 $g(x, y) < 0$，则 $\lambda = 0$，易知：

由上式易得 $x = 1, y = 1$，$f(x, y) = 0$。此时 $g(x, y) < 0$，条件满足。

对比可得 $x = 1, y = 1$ 时 $f(x, y)$ 为最优解。

参考文献

1. 周志华. "机器学习." 清华大学出版社，北京.
2. "Lagrange multiplier." 维基百科.
3. "Karush-Kuhn-Tucker conditions." 维基百科