拉格朗日乘子法
问题描述
拉格朗日乘子法（Method of Lagrange multiplier）用于解决等式约束的优化问题（Equality-Constrained Optimization）。
等式约束的优化算法：给定目标函数 $f: \mathbb{R}^m \to \mathbb{R}$ 和等式约束条件 $\mathbf{g}(\mathbf{x}) = \mathbf{c}$，其中 $\mathbf{x} \in \mathbb{R}^n$，$\mathbf{c} \in \mathbb{R}^m$。问题是找到 $\mathbf{x}^\ast$ 满足
$$ \mathbf{x}^\ast = \arg\min_\mathbf{x} f(\mathbf{x}), \quad \operatorname{subject~to} \quad \mathbf{g}(\mathbf{x}) = \mathbf{c}. $$
其中 $\mathbf{g}(\mathbf{x}^\ast) = \mathbf{c}$ 为多个等式约束条件 $g_1(\mathbf{x}^\ast) = c_1$，$g_2(\mathbf{x}^\ast) = c_2$ 等。
注：为了简单起见，我们先考虑一个限制条件 $g(\mathbf{x}) = c$。
核心思想
等高线 Level Sets：对于 $d \in \mathbb{R}$，集合 $\{\mathbf{x}: f(\mathbf{x}) = d\}$ 构成了 $f$ 的一条等高线。
- 梯度与等高线正交：函数在某一点的梯度 $\nabla f(\mathbf{x})$ 指向函数值增长最快的方向，且与该点的等高线正交。
- 约束曲面是等高线：约束 $g(\mathbf{x}) = c$ 本身也定义了一个曲面。由于其是一个等式，其可以被视作等高线，因此 $\nabla g(\mathbf{x})$ 与该曲面正交。
拉格朗日乘子法的直观理解：假设我们沿着约束曲面 $g(\mathbf{x}) = c$ 行走，寻找 $f(\mathbf{x})$ 的最高点。
- 如果我们能沿着约束曲面 $g(\mathbf{x}) = c$ 移动优化 $f(\mathbf{x})$，那我们肯定还没到最优点。
- 当我们达到 $\mathbf{x}^\ast$ 时，我们无法再沿着 $g(\mathbf{x}) = c$ 优化 $f(\mathbf{x})$，因此 $\mathbf{x}^\ast$ 处约束曲线的方向与 $f(\mathbf{x})$ 的等高线方向是相切的。
核心思想：拉格朗日乘子法的核心思想为在最优点 $\mathbf{x}^\ast$处，目标函数 $f(\mathbf{x})$ 的等高线/面与约束条件 $g(\mathbf{x}) = c$ 的曲线/面相切。用数学语言来说即两个曲面 $f(\mathbf{x}) = f(\mathbf{x}^\ast)$ 和 $g(\mathbf{x}) = c$ 相切，那么它们的法向量必然是平行的，也就是
$$ \nabla f(\mathbf{x}^*)=-\lambda\nabla g(\mathbf{x}^*) \quad \Rightarrow \quad \nabla f(\mathbf{x}^*)+\lambda\nabla g(\mathbf{x}^*)=\mathbf{0} $$
其中 $\lambda$ 是一个待定系数，表示两个向量的模长比。
拉格朗日乘子法
拉格朗日乘子法叙述：上述思想引出了一个巧妙的解决方案，我们引入一个辅助函数，称为拉格朗日函数（Lagrangian Function） ：
$$ L(\mathbf{x},\lambda)=f(\mathbf{x})+\lambda(g(\mathbf{x})-c) $$
这样我们就把前面的有约束问题转换为了对拉格朗日函数 $L(\mathbf{x}, \lambda)$ 的无约束优化问题：
$$ \begin{cases} \nabla_\mathbf{x}L(\mathbf{x},\lambda)=\nabla f(\mathbf{x})+\lambda\nabla g(\mathbf{x})=\mathbf{0} \\ \frac{\partial L}{\partial\lambda}=g(\mathbf{x})-c=0 \end{cases} $$
其中第一个式子是前一节中导出的条件，第二个式子施加了原始的约束条件 $g(\mathbf{x}) = c$。
多等式约束拉格朗日乘子法：对于多个等式约束的优化问题，我们定义拉格朗日函数为
$$ L(\mathbf{x},\boldsymbol{\lambda})=f(\mathbf{x})+\sum_{i=1}^m\lambda_i(g_i(\mathbf{x})-c_i). $$
对应的无约束优化问题为：
$$ \begin{cases} \nabla_\mathbf{x}L(\mathbf{x},\boldsymbol{\lambda})=\nabla f(\mathbf{x})+\sum_{i=1}^m\lambda_i\nabla g_i(\mathbf{x})=\mathbf{0} \\ \frac{\partial L}{\partial\lambda_i}=g_i(\mathbf{x})-c_i=0, \quad i = 1,2,\cdots, m \end{cases} $$