Larangian Multiplier Method

背景#

在优化问题中，我们经常需要在满足若干约束条件的前提下，寻找目标函数的极值。典型形式是：

\begin{aligned} &\min_{x\in\mathbb{R}^n} && f(x) \\ &\text{s.t.} && g_i(x) = 0,\quad i=1,\dots,m. \end{aligned}

直接在可行域内搜索往往困难——可行域可能非常复杂。拉格朗日乘子法提供了一种将约束”合并”到目标函数中的技巧，使问题转化为无约束优化，便于求解。

Lagrangian 乘子法#

引入乘子（Lagrange multipliers） $\lambda = (\lambda_1,\dots,\lambda_m)$ ，构造拉格朗日函数：

\mathcal{L}(x,\lambda) = f(x) - \sum_{i=1}^m \lambda_i\,g_i(x).

然后，在 $\mathbb{R}^{n+m}$ 空间中同时对 $(x,\lambda)$ 求偏导数，得到一阶条件（驻点条件）：

\begin{cases} \nabla_x \mathcal{L}(x,\lambda) = \nabla f(x) - \sum_{i=1}^m \lambda_i\,\nabla g_i(x) = 0,\\ \nabla_\lambda \mathcal{L}(x,\lambda) = -\bigl(g_1(x),\dots,g_m(x)\bigr)^\top = 0. \end{cases}

简化为：

$\nabla f(x) = \sum_{i=1}^m \lambda_i\,\nabla g_i(x)$
$g_i(x) = 0,\;i=1,\dots,m$

在满足这些条件的 $(x^*, \lambda^*)$ 处， $x^*$ 是目标函数 $f(x)$ 在约束集上的驻点（可能是极小点、极大点或鞍点）。为找到最小值点，可采用以下方法：

将求得的各个 $x^*$ 代入原函数 $f(x)$ ，计算函数值并比较，确定全局最小值点。
理论上，满足约束优化问题的驻点 $(x^*, \lambda^*)$ 必定是对偶问题 $\max_{\lambda} \min_{x} \mathcal{L}(x, \lambda)$ 的解。

理论解释#

直观理解：乘子 $\lambda_i$ 表示第 $i$ 个约束对目标函数在最优点处的”边际影响力”。
等价性：若 $f$ 与每个 $g_i$ 在解附近足够光滑，且 $\nabla g_1,\dots,\nabla g_m$ 在解处线性无关，则解必为上述驻点之一。
必要性：在约束极值点处，目标函数梯度必须在约束集的切空间内——即与切空间正交的向量（约束梯度）能线性组合出目标梯度。
最优性判定：通过拉格朗日函数的海森矩阵在可行方向上的正定性/负定性可判断局部极值性质。

为什么最优解一定满足 $\nabla f(x^) = \sum_{i=1}^m \lambda_i \nabla g_i(x^)$ ？#

这个条件的另一层含义就是在 $x^*$ 处，目标函数 $f(x)$ 与约束函数 $g_i(x)$ 的线性组合后的曲线相切。设想极值点不在相切的位置取到，而在图中某处等高线与约束线相交的点。好，沿着约束曲线向前走一点，目标函数值就会继续下降，这就说明了 $x^*$ 不是极值点。因此，必须等高线与约束线相切，才能保证 $x^*$ 是极值点。

KKT 条件（Karush–Kuhn–Tucker）#

当问题含有不等式约束时，拉格朗日乘子法推广为KKT条件：

\begin{aligned} &\min_x && f(x)\\ &\text{s.t.} && g_i(x) = 0,\;i=1,\dots,m,\\ & && h_j(x) \le 0,\;j=1,\dots,p. \end{aligned}

对应的KKT拉格朗日函数形式为：

\mathcal{L}(x,\lambda,\mu) = f(x) - \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \mu_j h_j(x)

存在乘子 $\lambda_i$ （等式）与 $\mu_j\ge0$ （不等式），使得：

可行性： $g_i(x^*)=0,\;h_j(x^*)\le0$
驻点条件： $\nabla f(x^*) = \sum_i \lambda_i \,\nabla g_i(x^*) + \sum_j \mu_j \,\nabla h_j(x^*)$
互补松弛： $\mu_j\,h_j(x^*)=0,\;j=1,\dots,p$
乘子非负性： $\mu_j\ge0$

在凸优化问题中，这些条件不仅必要，而且充分。

实例：约束最小二乘#

问题：

\min_{x\in\mathbb{R}^2}\; \frac{1}{2}\|x\|^2,\quad \text{s.t. } x_1 + 2x_2 - 3 = 0.

构造拉格朗日函数：

\mathcal{L}(x,\lambda) = \tfrac12(x_1^2 + x_2^2) - \lambda (x_1 + 2x_2 - 3).

求解一阶条件：

\begin{cases} \nabla_{x_1}\mathcal{L} = x_1 - \lambda = 0 \quad\Rightarrow\quad x_1 = \lambda,\\ \nabla_{x_2}\mathcal{L} = x_2 - 2\lambda = 0 \quad\Rightarrow\quad x_2 = 2\lambda,\\ \nabla_{\lambda}\mathcal{L} = -(x_1 + 2x_2 - 3)=0 \quad\Rightarrow\quad \lambda + 2(2\lambda) - 3 = 0. \end{cases}

解得 $5\lambda = 3$ ，故 $\lambda = 3/5$ ，进而

x^* = \bigl(\tfrac{3}{5},\,\tfrac{6}{5}\bigr).

代入原函数可验证此为全局最优解。

对偶问题#

考虑一般约束优化问题：

\begin{aligned} &\min_{x\in\mathbb{R}^n} && f(x) \\ &\text{s.t.} && g_i(x) = 0,\quad i=1,\dots,m,\\ & && h_j(x) \le 0,\quad j=1,\dots,p. \end{aligned}

构造拉格朗日函数，引入乘子 $\lambda_i \in \mathbb{R}$ 和 $\mu_j \ge 0$ ：

\mathcal{L}(x, \lambda, \mu) = f(x) - \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \mu_j h_j(x)

注意：对不等式约束使用 $+$ 号，确保违背约束时（ $h_j(x) > 0$ ），惩罚项 $\mu_j h_j(x)$ 可通过增大 $\mu_j$ 使惩罚达到 $+\infty$ 。

定义对偶函数：

q(\lambda, \mu) = \min_{x} \mathcal{L}(x, \lambda, \mu)

对偶函数的特性：

对给定的乘子 $\lambda, \mu$ ， $q(\lambda, \mu)$ 是拉格朗日函数关于 $x$ 的最小值
若 $\mu_j < 0$ ，则约定 $q(\lambda, \mu) = -\infty$
对任何满足约束的 $x^*$ ，若 $\mu \ge 0$ ，则 $q(\lambda, \mu) \leq f(x^*)$

由此定义对偶问题：

\max_{\lambda, \mu} \quad q(\lambda, \mu) \quad \text{subject to } \mu_j \ge 0, \; j=1,\dots,p

对偶问题的最优值必定不大于原始问题的最优值，这称为弱对偶性。在特定条件下（如凸优化问题），还可能成立强对偶性。

利用对偶性求解原始问题#

对偶问题不仅提供了原始问题最优值的下界，在满足强对偶性条件时，还可以用于求解原始问题：

解对偶问题：求解 $\max_{\lambda, \mu \geq 0} q(\lambda, \mu)$ ，得到最优对偶变量 $(\lambda^*, \mu^*)$ 。
从对偶恢复原始解：当原始问题为凸问题且满足Slater条件（存在严格可行点）时，我们可以：
- 若对偶函数 $q(\lambda^*, \mu^*)$ 在某点 $x^*$ 取得最小值，则 $x^*$ 即为原始问题的最优解
- 通过求解方程 $\nabla_x \mathcal{L}(x, \lambda^*, \mu^*) = 0$ 得到原始问题的最优解 $x^*$
互补松弛性质：在最优点处， $\mu_j^* h_j(x^*) = 0$ 提供了关于活跃约束的重要信息：
- 若 $\mu_j^* > 0$ ，则必有 $h_j(x^*) = 0$ （约束紧绷）
- 若 $h_j(x^*) < 0$ ，则必有 $\mu_j^* = 0$ （约束不起作用）

这种方法在某些情况下比直接求解原始问题更有效，特别是当对偶问题结构更简单或维度更低时。

背景#