当前位置：首页 > article >正文

【机器学习】数学知识：拉格朗日对偶（Lagrange Duality）

article 2025/2/13 23:01:22

拉格朗日对偶（Lagrange Duality）

1. 概念

拉格朗日对偶（Lagrange Duality）是优化理论中的一个重要方法，用于将约束优化问题转换为更易求解的对偶问题。它在凸优化、经济学、机器学习（如 SVM）等领域有广泛应用。

2. 原始问题（Primal Problem）

考虑一个标准的约束优化问题：

$\min_{x} f(x)$
$\text{s.t. } g_i(x) \leq 0, \quad i = 1, 2, ..., m$
$h_j(x) = 0, \quad j = 1, 2, ..., p$

其中：

f(x) 是目标函数
$g_i(x)$ 是不等式约束
$h_j(x)$ 是等式约束

3. 拉格朗日函数

定义 拉格朗日函数（Lagrangian）：

$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 \geq 0$ （对应不等式约束）
拉格朗日乘子 $\mu_j$ （对应等式约束）

4. 对偶函数

对偶函数定义为：

$\theta(\lambda, \mu) = \inf_{x} L(x, \lambda, \mu)$

即，对于给定的拉格朗日乘子 (λ,μ)，计算 L(x,λ,μ) 在 x 上的最小值。

5. 对偶问题（Dual Problem）

$\max_{\lambda \geq 0, \mu} \theta(\lambda, \mu)$

即，找出最优的 (λ,μ) 使得 θ(λ,μ) 取得最大值。

6. 弱对偶性和强对偶性

弱对偶性：对偶问题的最优值永远不大于原始问题的最优值：

$\max_{\lambda \geq 0, \mu} \theta(\lambda, \mu) \leq \min_{x} f(x)$
强对偶性（Slater 条件）：如果原始问题是凸优化问题，并且满足 Slater 条件（即存在严格可行解），则对偶问题的最优值等于原始问题的最优值。

7. 计算示例

考虑优化问题：

$\min_{x} x^2$
$\text{s.t. } x - 2 \leq 0$

拉格朗日函数：

$L(x, \lambda) = x^2 + \lambda (x - 2)$

对偶函数：

$\theta(\lambda) = \inf_{x} (x^2 + \lambda (x - 2))$

求导：

$\frac{d}{dx} (x^2 + \lambda (x - 2)) = 2x + \lambda = 0$

解得：

$x = -\frac{\lambda}{2}$

代入 $L(x, \lambda)$ ：

$\theta(\lambda) = \left(-\frac{\lambda}{2}\right)^2 + \lambda \left(-\frac{\lambda}{2} - 2\right)$
$= \frac{\lambda^2}{4} - \frac{\lambda^2}{2} - 2\lambda$
$=-\frac{\lambda^2}{4} - 2\lambda$