对偶问题（一）

对偶问题（一）：从拉格朗日函数到对偶问题

小象实战讲义 · 人工智能数学基础

在优化理论中，我们常常面对带有约束的复杂优化问题。直接求解这些问题可能非常困难，尤其是在约束条件众多或问题非凸时。本节将引入一个强大的工具——对偶理论。通过将原始优化问题转化为其对偶问题，我们不仅能简化计算，还能获得对问题结构更深刻的理解，甚至在经济学、机器学习等领域获得新的洞见。学完本节，你将掌握构造拉格朗日函数及其对偶问题的核心方法，理解弱对偶与强对偶的基本原理。

💡 核心导读

• 拉格朗日函数：将有约束优化问题转化为一个包含原始变量和拉格朗日乘子的增广目标函数，其思想与机器学习中的“损失+惩罚”框架一脉相承。
• 拉格朗日对偶函数：通过对拉格朗日函数关于原始变量取极小值得到，它给出了原始问题最优值的一个下界，并且总是凹函数。
• 拉格朗日对偶问题：在拉格朗日乘子非负的约束下，最大化对偶函数。无论原问题是否为凸，对偶问题总是一个凸优化问题。
• 弱对偶与强对偶：对偶问题的最优值总是原问题最优值的下界（弱对偶）。在凸问题且满足某些约束准则（如Slater条件）时，两者相等（强对偶），这为通过求解对偶问题来获取原问题最优解提供了可能。

从约束优化到拉格朗日函数

我们首先考虑一个标准形式的约束优化问题：

$$\begin{aligned} &\text{minimize} \quad f_0(x) \ &\text{subject to} \quad f_i(x) \le 0, \quad i = 1, \ldots, m \ &\qquad \qquad \quad h_i(x) = 0, \quad i = 1, \ldots, p \end{aligned}$$

其中 $x \in \mathbb{R}^n$ 是优化变量，$f_0: \mathbb{R}^n \to \mathbb{R}$ 是目标函数，$f_i: \mathbb{R}^n \to \mathbb{R}$ 定义了 $m$ 个不等式约束，$h_i: \mathbb{R}^n \to \mathbb{R}$ 定义了 $p$ 个等式约束。定义域 $D = \bigcap_{i=0}^{m} \operatorname{dom} f_i \cap \bigcap_{i=1}^{p} \operatorname{dom} h_i$。我们用 $p^{\star}$ 表示该问题的最优值。

拉格朗日函数的基本思想是将约束条件以加权和的形式“吸收”到目标函数中，从而得到一个增广的目标函数。对于上述问题，其拉格朗日函数 $L: \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}$ 定义为：

$$L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{i=1}^{p} \nu_i h_i(x)$$

其中，$\lambda_i$ 称为第 $i$ 个不等式约束对应的拉格朗日乘子，$\nu_i$ 称为第 $i$ 个等式约束对应的拉格朗日乘子。向量 $\lambda = (\lambda_1, \ldots, \lambda_m)$ 和 $\nu = (\nu_1, \ldots, \nu_p)$ 合称为拉格朗日乘子向量。

为什么这样构造？ 拉格朗日函数可以类比于机器学习中的 “损失+惩罚” 框架。考虑一个线性回归问题，为了防止过拟合，我们会在损失函数（如残差平方和）后加上一个正则化项（如系数的范数）。拉格朗日函数中的 $\sum \lambda_i f_i(x)$ 和 $\sum \nu_i h_i(x)$ 就扮演了“惩罚项”的角色：

• 对于不等式约束 $f_i(x) \le 0$，如果我们要求 $\lambda_i \ge 0$，那么当 $f_i(x) > 0$（违反约束）时，惩罚项 $\lambda_i f_i(x)$ 为正，会“抬高” $L(x, \lambda, \nu)$ 的值，使得它在最小化过程中不受欢迎。只有当 $f_i(x) \le 0$ 时，惩罚项非正，才有助于降低函数值。
• 对于等式约束 $h_i(x) = 0$，当 $h_i(x) \neq 0$ 时，惩罚项 $\nu_i h_i(x)$ 不为零，同样会阻碍 $L$ 取到极小值。

因此，通过引入拉格朗日乘子，我们将一个有约束的优化问题转化为了一个关于 $x, \lambda, \nu$ 的无约束问题（尽管 $\lambda$ 通常有非负要求）。这种思想是后续对偶理论和KKT条件的基础。

拉格朗日对偶函数

在拉格朗日函数的基础上，我们定义拉格朗日对偶函数（简称对偶函数）$g: \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} \cup {-\infty}$ 为拉格朗日函数关于原始变量 $x$ 的逐点下确界：

$$g(\lambda, \nu) = \inf_{x \in D} L(x, \lambda, \nu) = \inf_{x \in D} \left( f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{i=1}^{p} \nu_i h_i(x) \right)$$

如果 $L(x, \lambda, \nu)$ 关于 $x$ 无下界，则定义 $g(\lambda, \nu) = -\infty$。

对偶函数的重要性质：

1. 凹性：对偶函数 $g(\lambda, \nu)$ 总是凹函数，即使原问题不是凸优化问题。这是因为 $g$ 是一族关于 $(\lambda, \nu)$ 的仿射函数的逐点下确界，而仿射函数的逐点下确界是凹函数。
2. 下界性质：对于任意 $\lambda \succeq 0$（即 $\lambda_i \ge 0$）和任意 $\nu$，对偶函数给出了原问题最优值 $p^{\star}$ 的一个下界，即： $$g(\lambda, \nu) \le p^{\star}$$ 证明：设 $x^{\star}$ 是原问题的一个可行点（即满足所有约束），且 $\lambda \succeq 0$。由于 $f_i(x^{\star}) \le 0$，$h_i(x^{\star}) = 0$，我们有： $$\sum_{i=1}^{m} \lambda_i f_i(x^{\star}) + \sum_{i=1}^{p} \nu_i h_i(x^{\star}) \le 0$$ 因此， $$L(x^{\star}, \lambda, \nu) = f_0(x^{\star}) + \sum_{i=1}^{m} \lambda_i f_i(x^{\star}) + \sum_{i=1}^{p} \nu_i h_i(x^{\star}) \le f_0(x^{\star})$$ 由于 $g(\lambda, \nu)$ 是 $L(x, \lambda, \nu)$ 关于 $x$ 的下确界，且 $x^{\star} \in D$，故： $$g(\lambda, \nu) \le L(x^{\star}, \lambda, \nu) \le f_0(x^{\star})$$ 上式对任意可行点 $x^{\star}$ 都成立，自然对最优解也成立，所以 $g(\lambda, \nu) \le p^{\star}$。

这个下界性质类似于数学分析中的夹逼准则：如果我们能找到越来越紧的下界，就有可能逼近甚至得到原问题的最优解。

示例：标准形式线性规划的对偶函数

考虑标准形式的线性规划问题： $$\begin{aligned} &\text{minimize} \quad c^T x \ &\text{subject to} \quad A x = b \ &\qquad \qquad \quad x \succeq 0 \end{aligned}$$ 为了写成标准形式，我们将不等式约束 $x \succeq 0$ 改写为 $-x \preceq 0$。引入拉格朗日乘子 $\nu$（对应等式约束）和 $\lambda \succeq 0$（对应不等式约束 $-x \preceq 0$），拉格朗日函数为： $$L(x, \lambda, \nu) = c^T x - \lambda^T x + \nu^T (A x - b) = -\nu^T b + (c - \lambda + A^T \nu)^T x$$ 对偶函数 $g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu)$。这是一个关于 $x$ 的线性函数，其下确界为：

• 如果 $(c - \lambda + A^T \nu) \neq 0$，则 $g(\lambda, \nu) = -\infty$。
• 如果 $(c - \lambda + A^T \nu) = 0$，则 $g(\lambda, \nu) = -\nu^T b$。

因此，该线性规划的对偶函数为： $$g(\lambda, \nu) = \begin{cases} -\nu^T b, & \text{if } c - \lambda + A^T \nu = 0 \ -\infty, & \text{otherwise} \end{cases}$$

拉格朗日对偶问题

既然对偶函数 $g(\lambda, \nu)$ 给出了原问题最优值 $p^{\star}$ 的一个下界，一个自然的问题是：所有下界中最好的（即最大的）下界是什么？ 这引出了拉格朗日对偶问题：

$$\begin{aligned} &\text{maximize} \quad g(\lambda, \nu) \ &\text{subject to} \quad \lambda \succeq 0 \end{aligned}$$

这是一个以拉格朗日乘子 $(\lambda, \nu)$ 为优化变量的优化问题。我们称原始问题为原问题，上述问题为原问题的对偶问题。

对偶问题的重要性质：

1. 凸性：由于对偶函数 $g$ 是凹函数，且约束 $\lambda \succeq 0$ 是凸的，因此对偶问题总是一个凸优化问题（最大化凹函数等价于最小化凸函数）。这一性质与原始问题是否为凸无关，为求解非凸问题提供了一条可能的途径。
2. 最优值与最优解：对偶问题的最优值记为 $d^{\star}$。使得 $g(\lambda, \nu)$ 达到最大值 $d^{\star}$ 的乘子 $(\lambda^{\star}, \nu^{\star})$ 称为最优拉格朗日乘子。

示例：标准形式线性规划的对偶问题

基于前面求得的对偶函数 $g(\lambda, \nu)$，其线性规划的对偶问题为： $$\begin{aligned} &\text{maximize} \quad g(\lambda, \nu) \ &\text{subject to} \quad \lambda \succeq 0 \end{aligned}$$ 由于当 $c - \lambda + A^T \nu \neq 0$ 时 $g = -\infty$，我们只关心 $g$ 有有限值的情况，即 $c - \lambda + A^T \nu = 0$。此时 $g(\lambda, \nu) = -\nu^T b$。因此，对偶问题等价于： $$\begin{aligned} &\text{maximize} \quad -\nu^T b \ &\text{subject to} \quad c - \lambda + A^T \nu = 0 \ &\qquad \qquad \quad \lambda \succeq 0 \end{aligned}$$ 由等式约束得 $\lambda = c + A^T \nu$，结合 $\lambda \succeq 0$，等价于 $c + A^T \nu \succeq 0$。同时，将目标函数改为最小化 $\nu^T b$（最大化 $-\nu^T b$ 等价于最小化 $\nu^T b$），我们得到线性规划对偶问题的标准形式： $$\begin{aligned} &\text{minimize} \quad \nu^T b \ &\text{subject to} \quad A^T \nu + c \succeq 0 \end{aligned}$$ 变量为 $\nu$。注意，原问题的变量个数 $n$ 对应了对偶问题中不等式约束的个数，而原问题的等式约束个数 $p$ 对应了对偶问题的变量维度。当原问题约束很多（$n$ 很大）而变量相对较少时，求解其对偶问题（变量少，约束多）可能在计算上更高效。

弱对偶与强对偶

根据对偶函数的下界性质，我们可以立即得到一个重要的不等式关系，称为弱对偶性：

$$d^{\star} \le p^{\star}$$

即对偶问题的最优值 $d^{\star}$ 不超过原问题的最优值 $p^{\star}$。差值 $p^{\star} - d^{\star}$ 称为对偶间隙。弱对偶性总是成立，即使原问题非凸。

一个更理想的情况是强对偶性，即对偶间隙为零：

$$d^{\star} = p^{\star}$$

强对偶性意味着我们可以通过求解（通常更简单的）对偶问题来获得原问题的最优值。然而，强对偶性并非总是成立。

强对偶性成立的充分条件（对于凸问题）： 如果原问题是凸优化问题，即：

• $f_0, f_1, \ldots, f_m$ 是凸函数。
• $h_1, \ldots, h_p$ 是仿射函数（即 $h_i(x) = a_i^T x - b_i$）。 并且满足某些约束准则，则强对偶性成立。

一个常用且简单的约束准则是 Slater条件：

存在一个严格可行点 $x \in \operatorname{relint} D$，使得： $$> f_i(x) < 0, \quad i = 1, \ldots, m, \quad \text{且} \quad h_i(x) = 0, \quad i = 1, \ldots, p >$$ 其中 $\operatorname{relint} D$ 表示定义域 $D$ 的相对内部。

Slater条件要求不等式约束被严格满足（取 < 0 而非 ≤ 0）。如果部分不等式约束 $f_i$ 是仿射函数，条件可以放宽为改进的Slater条件：对于仿射不等式约束，只要求 $f_i(x) \le 0$；对于非线性凸不等式约束，仍要求 $f_i(x) < 0$。

总结：对于一个凸优化问题，如果存在一个（改进的）Slater点，则强对偶性成立。这为许多实际问题（如线性规划、二次规划等）中通过求解对偶问题来获取原问题解提供了理论保证。

📝 动手练一练

1. 构造拉格朗日函数：考虑以下优化问题： $$\begin{aligned} &\text{minimize} \quad x_1^2 + x_2^2 \ &\text{subject to} \quad x_1 + x_2 \ge 1 \ &\qquad \qquad \quad x_1 \ge 0 \end{aligned}$$ 请将其不等式约束改写为“≤ 0”的标准形式，并写出对应的拉格朗日函数 $L(x, \lambda)$。

2. 验证弱对偶性（数值实验）：对于问题1，假设我们取一组拉格朗日乘子 $\lambda_1 = 0.5, \lambda_2 = 0.3$（请确保符号正确）。编写Python代码，通过数值优化（如 scipy.optimize.minimize）近似计算该乘子下的对偶函数值 $g(\lambda)$。再通过几何观察或求解KKT条件（如果已学）找出原问题的最优值 $p^{\star}$ 的近似值。验证是否满足 $g(\lambda) \le p^{\star}$。

参考答案：

1. 改写约束：$x_1 + x_2 \ge 1 \Rightarrow -x_1 - x_2 + 1 \le 0$；$x_1 \ge 0 \Rightarrow -x_1 \le 0$。 拉格朗日函数：$L(x, \lambda) = x_1^2 + x_2^2 + \lambda_1(-x_1 - x_2 + 1) + \lambda_2(-x_1)$，其中 $\lambda_1, \lambda_2 \ge 0$。

2. 以下Python代码演示了如何数值计算对偶函数值：

   import numpy as np
   from scipy.optimize import minimize
   
   # 定义拉格朗日函数 L(x, lambda)
   def lagrangian(x, lambda_vec):
       # 不等式约束: -x1 - x2 + 1 <= 0, -x1 <= 0
       f1 = -x[0] - x[1] + 1
       f2 = -x[0]
       # 目标函数 + 惩罚项
       return x[0]**2 + x[1]**2 + lambda_vec[0]*f1 + lambda_vec[1]*f2
   
   # 给定拉格朗日乘子
   lambda_val = np.array([0.5, 0.3])
   
   # 通过优化求解 inf_x L(x, lambda)
   # 初始点
   x0 = np.array([0.5, 0.5])
   # 使用无约束优化方法寻找使L最小的x
   res = minimize(lambda x: lagrangian(x, lambda_val), x0, method='BFGS')
   x_opt = res.x
   g_lambda = res.fun  # 这就是近似的 g(lambda)
   
   print(f"对于 lambda = {lambda_val}:")
   print(f"  使得 L 最小的 x ≈ {x_opt}")
   print(f"  对偶函数值 g(lambda) ≈ {g_lambda:.6f}")
   
   # 原问题的最优解可以通过解析或观察得到：在约束 x1+x2>=1 和 x1>=0 下最小化 x1^2+x2^2
   # 几何上，这是圆到半平面的距离，最优解在点(0.5, 0.5)，最优值 p* = 0.5
   p_star = 0.5
   print(f"\n原问题最优值 p* = {p_star}")
   print(f"验证弱对偶性: g(lambda) = {g_lambda:.6f} <= p* = {p_star} ? {g_lambda <= p_star + 1e-6}")

   运行上述代码，你将看到计算出的 $g(\lambda)$ 确实小于等于 $p^{\star}$，验证了弱对偶性。

本章小结

本节我们深入探讨了对偶理论的起点，为理解如何通过“另一面”来求解优化问题奠定了基础。

要点回顾：

• 拉格朗日函数 $L(x, \lambda, \nu)$ 将有约束问题转化为无约束形式，其惩罚项思想与正则化相通。
• 拉格朗日对偶函数 $g(\lambda, \nu)$ 是 $L$ 关于 $x$ 的极小值，它总是凹函数，并提供了原问题最优值 $p^{\star}$ 的下界。
• 拉格朗日对偶问题 旨在最大化 $g(\lambda, \nu)$（约束 $\lambda \succeq 0$），它总是一个凸优化问题，这为求解非凸原问题提供了可能路径。
• 弱对偶性 $d^{\star} \le p^{\star}$ 恒成立；强对偶性 $d^{\star} = p^{\star}$ 在凸问题且满足Slater条件时成立，此时对偶问题的最优解能揭示原问题的最优解。

行动清单：

1. 动手推导：任选一个简单的带约束优化问题（如本节练习题），完整写出其拉格朗日函数、对偶函数，并尝试表述其对偶问题。
2. 代码验证：使用Python的优化库（如SciPy）数值计算给定乘子下的对偶函数值，并与原问题最优值比较，直观感受弱对偶性。
3. 联想对比：思考拉格朗日函数中的“损失+惩罚”框架与你所知的机器学习正则化方法（如Lasso、Ridge回归）之间的联系，加深对乘子 $\lambda$ 作为“惩罚权重”的理解。

掌握了对偶问题的基本构造和性质，我们将在下一节探讨如何从对偶解恢复原问题解的关键——KKT最优性条件，并看到对偶理论在支持向量机等经典算法中的直接应用。

— 小象教研组