拉格朗日对偶问题
-
基本动机
在约束优化问题中，直接处理约束可能很困难。拉格朗日对偶的核心思想是将原始约束问题转化为一个无约束或约束更简单的对偶问题，通过构建拉格朗日函数，引入对偶变量（拉格朗日乘子）来松弛约束。对偶问题提供原始问题最优值的下界（对于最小化问题），帮助估计解的质量或设计优化算法。 -
拉格朗日函数的构造
考虑原始问题：
\[ \min f(x) \quad \text{s.t.} \quad g_i(x) \leq 0, \ h_j(x) = 0, \]
其中 \(x \in \mathbb{R}^n\)，不等式约束 \(g_i(x) \leq 0\) 和等式约束 \(h_j(x)=0\)。拉格朗日函数定义为：
\[ L(x, \lambda, \nu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \nu_j h_j(x), \]
\(\lambda_i \geq 0\) 和 \(\nu_j\) 是对偶变量。函数 \(L\) 将目标函数和约束的加权结合，通过调整乘子来惩罚约束违反。
- 拉格朗日对偶函数
对偶函数 \(g(\lambda, \nu)\) 是拉格朗日函数关于原始变量 \(x\) 的下确界：
\[ g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu). \]
对偶函数是凹函数（无论原始问题是否凸），且对任意 \(\lambda \geq 0\)，\(g(\lambda, \nu)\) 总是原始问题最优值 \(p^*\) 的下界（即 \(g(\lambda, \nu) \leq p^*\)）。这一性质称为弱对偶性。
- 拉格朗日对偶问题
对偶问题是最大化对偶函数：
\[ \max_{\lambda \geq 0, \nu} g(\lambda, \nu). \]
对偶问题的最优值 \(d^*\) 满足 \(d^* \leq p^*\)。当 \(d^* = p^*\) 时，称为强对偶性成立，此时可以通过对偶问题获得原始问题的最优解。强对偶性在凸问题且满足斯莱特条件（存在内点满足约束）时通常成立。
- 应用与意义
对偶问题常比原始问题更易求解，例如约束被转化为目标函数中的线性项。在算法设计中，对偶问题可推导出分解方法（如对偶分解），或用于构造停止准则（通过对偶间隙 \(p^* - d^*\) 判断最优性）。在支持向量机、经济学和分布式优化中均有重要应用。