第六章：对偶方法与 ADMM

6.1.1 原问题与拉格朗日函数#

考虑带等式约束的优化问题（原问题，Primal Problem）：

其中 $x \in \mathbb{R}^n$ 为原始变量（primal variable），$f: \mathbb{R}^n \to \mathbb{R}$ 为目标函数，$c(x) = 0$ 为可行性条件。引入拉格朗日函数（Lagrangian）：

其中 $\lambda$ 为拉格朗日乘子。

对拉格朗日函数关于 $\lambda$ 求最大值，分两种情况：

• 若 $c(x) = 0$，则 $\lambda^\top c(x) = 0$，此时 $\max_{\lambda} \mathcal{L}(x, \lambda) = f(x)$；
• 若 $c(x) \neq 0$，则 $\lambda^\top c(x)$ 关于 $\lambda$ 是线性函数，可取到 $+\infty$。

因此：

在此基础上再对 $x$ 取最小值，$c(x) \neq 0$ 的情况因目标值为 $+\infty$ 而被自然排除。这意味着原问题等价于极小极大问题（minimax problem）：

6.1.2 对偶问题的定义#

对偶问题（Dual Problem）是将极小极大问题中求最大与求最小的顺序互换得到的：

定义对偶函数（dual function）：

其中 $\lambda$ 称为对偶变量（dual variable）。于是对偶问题简写为 $\max_{\lambda} g(\lambda)$。

当约束个数 $m$ 远小于原始变量维度 $n$（即 $m \ll n$）时，对偶变量 $\lambda \in \mathbb{R}^m$ 的维度远低于 $x \in \mathbb{R}^n$，在对偶空间中求解可以显著降低问题规模。

6.1.3 拉格朗日乘子的灵敏度解释#

最优拉格朗日乘子 $\lambda^*$ 衡量的是最优值对约束扰动的灵敏度。

设 $(x^*, \lambda^*)$ 是拉格朗日函数的驻点，则满足一阶最优性条件：

对约束施加微小扰动 $\epsilon$，将原问题改为 $\min_{x} f(x)$ s.t. $c(x) - \epsilon = 0$。此时最优解 $x^*(\epsilon)$ 和 $\lambda^*(\epsilon)$ 均成为 $\epsilon$ 的函数，拉格朗日函数变为 $\mathcal{L}(x, \lambda) = f(x) + \lambda^\top(c(x) - \epsilon)$，对应的最优性条件为：

对 $f(x^*(\epsilon))$ 关于 $\epsilon$ 求导，利用链式法则：

由式 (6.1’) 可知 $\nabla f(x^*(\epsilon)) = -\nabla c(x^*(\epsilon))^\top \lambda^*(\epsilon)$，代入得：

对式 (6.2’) 关于 $\epsilon$ 求导得 $\nabla c(x^*(\epsilon)) \frac{dx^*(\epsilon)}{d\epsilon} = I$，代入上式并在 $\epsilon = 0$ 处取值：

这说明 $\lambda_i^*$ 表示当第 $i$ 个约束 $c_i(x) = 0$ 受到单位扰动时，最优目标函数值的变化率（取负号）。$|\lambda_i^*|$ 越大，最优值对该约束的扰动越敏感。

6.1.4 弱对偶性#

定理（弱对偶性）. 原问题的最优值不小于对偶问题的最优值：

两者之差称为对偶间隙（duality gap）。

证明. 对于任意固定的 $x$ 和 $\lambda$，由最大值和最小值的定义：

因此对任意 $x, \lambda$ 均有 $\max_{\lambda} \mathcal{L}(x, \lambda) \geq \min_{x} \mathcal{L}(x, \lambda)$。对右端关于 $\lambda$ 取最大值，由于左端对任意 $\lambda$ 成立，不等式方向不变：

此时右端已是确定的数，左端仍含自由变量 $x$。再对左端关于 $x$ 取最小值，不等式仍成立：

弱对偶性对任意优化问题成立，不需要凸性或其他特殊假设。

6.1.5 强对偶性与 Slater 条件#

弱对偶性只给出了下界：对偶问题的最优值 $q^*$ 不超过原问题的最优值 $p^*$。当 $p^* = q^*$ 时——即对偶间隙为零——称强对偶性（strong duality）成立。强对偶性意味着可以通过求解对偶问题精确地获得原问题的最优值，这正是对偶方法的理论基础。

强对偶性不是自动成立的。对于一般的非凸问题，对偶间隙通常严格为正。但对凸优化问题，在满足一定的约束品性（constraint qualification）条件下，强对偶性成立。最常用的约束品性是 Slater 条件。

定义（Slater 条件）。 对凸优化问题 $\min f(x)$ s.t. $c_i(x) \leq 0$（$i = 1, \ldots, m$），$Ax = b$，如果存在一个可行点 $\bar{x}$ 使得所有不等式约束严格成立（$c_i(\bar{x}) < 0$，$i = 1, \ldots, m$），则称 Slater 条件满足。

Slater 条件的含义非常直观：可行域不能”薄”到只贴着约束边界——它必须有”内部空间”，至少存在一个点离所有不等式约束的边界都有余量。当不等式约束中有仿射函数时，Slater 条件可以放宽：仿射约束只需要求可行（$\leq$），不需要严格可行（$<$），因为线性约束不会产生”弯曲”的边界。

定理（强对偶原理）。 若凸优化问题满足 Slater 条件，则强对偶性成立，且对偶最优解可以达到。

强对偶性的实际意义：当它成立时，原问题的 KKT 条件不仅是必要条件，还是充分条件。这使得 KKT 条件成为凸优化问题的完整最优性刻画。同时，6.3—6.5 节的对偶算法（对偶上升法、ALM、ADMM）都隐含地依赖强对偶性——只有对偶间隙为零时，对偶空间中的最优解才能恢复出原问题的最优解。

6.2.1 等式约束问题的 KKT 条件#

考虑仅含等式约束的优化问题：

其拉格朗日函数为：

对拉格朗日函数分别关于 $x$ 和 $\lambda_i$ 求梯度并令其为零，得到 KKT 条件。在最优解 $(x^*, \lambda^*)$ 处：

驻点条件：

可行性条件：

满足上述条件的点 $(x^*, \lambda^*)$ 称为 KKT 点，这组条件可以类比无约束优化中的一阶必要条件。

6.2.2 一般约束问题的 KKT 条件#

考虑同时含有等式约束和不等式约束的一般优化问题：

其中 $\mathcal{I}$ 和 $\mathcal{J}$ 分别是等式约束和不等式约束的指标集。引入两组对偶变量：$\lambda = (\lambda_1, \ldots, \lambda_{|\mathcal{I}|})^\top$ 对应等式约束，$\mu = (\mu_1, \ldots, \mu_{|\mathcal{J}|})^\top$ 对应不等式约束。拉格朗日函数为：

若 $x^*$ 是局部最优解且满足约束品性条件，则存在 $\lambda^*$ 和 $\mu^*$ 使得以下四组条件成立。约束品性是 KKT 条件成立的前提——它保证约束的梯度在最优点处提供了足够的”方向信息”来刻画可行域的局部几何。最常用的约束品性有两种：线性无关约束品性（LICQ），要求最优点处所有紧约束（$c_j(x^*) = 0$ 的不等式约束加上所有等式约束）的梯度线性无关；以及前面提到的 Slater 条件，对凸问题要求存在严格可行的内点。对于凸优化问题，Slater 条件既保证强对偶性成立，也保证 KKT 条件是最优性的充要条件。

1. 驻点条件（Stationarity）：

2. 原始可行条件（Primal Feasibility）：

3. 对偶可行条件（Dual Feasibility）：

4. 互补松弛条件（Complementary Slackness）：

6.2.3 互补松弛条件的直觉理解#

互补松弛条件 $\mu_j^* c_j(x^*) = 0$ 要求 $\mu_j^*$ 和 $c_j(x^*)$ 中至少有一个为零。可以将不等式约束想象为一堵墙，$\mu_j^*$ 是墙对最优解的反作用力。

约束不紧的情形. 设约束为 $x \leq 100$，即 $c(x) = x - 100 \leq 0$，假设最优解 $x^* = 50$。此时 $c(x^*) = -50 < 0$，最优解距离约束边界很远，即使对约束施加微小扰动，最优解仍满足新约束。该约束对最优解的形成没有实质贡献——最优解在约束边界内有充裕的自由空间。此时 $x^*$ 远离墙面，墙对它没有反作用力，故 $\mu_j^* = 0$。

约束紧的情形. 同样的约束，但 $x^* = 100$。此时 $c(x^*) = 0$，最优解恰在约束边界上。对 $x$ 施加任何正向扰动都会突破约束变得不可行，最优解没有自由活动空间。此时 $x^*$ 贴在墙上，反作用力 $\mu_j^* > 0$，而 $c_j(x^*) = 0$。

两种情况下乘积 $\mu_j^* c_j(x^*)$ 均为零——$\mu_j^*$ 与 $c_j(x^*)$ 互为”互补”：一个非零时另一个必为零。这同时解释了对偶可行条件 $\mu_j^* \geq 0$ 的来源：反作用力的方向始终指向可行域内侧。

6.3.1 从原问题到对偶问题#

考虑带等式约束的优化问题：

其拉格朗日函数为 $\mathcal{L}(x, \lambda) = f(x) + \lambda^\top (Ax - b)$。原问题等价于 $\min_{x} \max_{\lambda} \mathcal{L}(x, \lambda)$。交换极小极大的顺序得到对偶问题 $\max_{\lambda} \min_{x} \mathcal{L}(x, \lambda)$，其中对偶函数为：

原问题对 $x$ 做梯度下降（求最小值沿负梯度方向更新），对偶问题则对 $\lambda$ 做梯度上升（求最大值沿梯度方向更新）：

6.3.2 对偶函数梯度的计算#

设在给定 $\lambda$ 下，内层极小问题的最优解为 $x^*$，则 $g(\lambda) = f(x^*) + \lambda^\top (Ax^* - b)$。对 $\lambda$ 求梯度得到：

对偶函数关于 $\lambda$ 的梯度恰好是约束残差 $Ax^* - b$。当原问题约束被精确满足时（$Ax^* = b$），梯度为零，对偶变量不再更新。

6.3.3 算法步骤#

对偶上升法（Dual Ascent Method）由两步交替迭代组成：

第一步固定当前对偶变量 $\lambda^k$，对拉格朗日函数关于 $x$ 求极小，得到 $x^{k+1}$——它正是对偶函数定义中 $\min_x \mathcal{L}(x, \lambda^k)$ 的最优解。第二步利用 $\nabla g(\lambda^k) = Ax^{k+1} - b$ 沿梯度方向做上升更新。

6.3.4 对偶上升法的局限性#

对偶上升法将约束优化问题转化为对偶空间中的无约束极大化问题，但有一个根本性缺陷：当目标函数 $f(x)$ 为线性函数时，算法无法给出最优解。

设 $f(x) = c^\top x$，则拉格朗日函数为：

第一步要求关于 $x$ 对上式取极小，但 $(c + A^\top \lambda)^\top x$ 关于 $x$ 是线性的：若系数 $c + A^\top \lambda \neq 0$，线性函数在无约束下沿某一方向趋于 $-\infty$，极小值不存在；若系数恰为零，目标退化为常数 $-\lambda^\top b$，任意 $x$ 都是极小解。无论哪种情况，$\arg\min_x$ 都无法给出确定的 $x^{k+1}$，算法失效。

对偶上升法失效的根本原因在于：标准拉格朗日函数关于 $x$ 的极小问题可能没有有限解。解决方案是在拉格朗日函数中添加二次罚项 $\frac{\beta}{2}\|Ax - b\|^2$，使子问题始终具有唯一解。这就是增广拉格朗日函数法的核心思想。

6.4.1 增广拉格朗日函数#

考虑等式约束优化问题：

其中 $f: \mathbb{R}^n \to \mathbb{R}$，$A \in \mathbb{R}^{m \times n}$，$b \in \mathbb{R}^m$。增广拉格朗日函数（Augmented Lagrangian Function）定义为：

其中 $\langle \lambda, Ax - b \rangle$ 是标准拉格朗日函数中的乘子项，$\frac{\beta}{2}\|Ax - b\|^2$ 称为增广项（二次罚项），$\beta > 0$ 为罚参数。

增广拉格朗日函数与标准拉格朗日函数的区别仅在于增广项。在可行点处（$Ax = b$），增广项为零，两者一致。增广项的作用在于：即使 $f(x)$ 为线性函数，增广后的子问题因包含二次项而具有有限最优解，从而克服了 6.3.4 节中对偶上升法的缺陷。

6.4.2 ALM 算法#

将对偶上升法中的标准拉格朗日函数替换为增广拉格朗日函数，并取步长 $\alpha = \beta$，得到 ALM 算法：

第一步对 $x$ 求解带二次罚项的子问题；第二步按梯度上升方向更新乘子 $\lambda$，步长取为罚参数 $\beta$。

6.4.3 KKT 条件分析#

原问题 (P) 在最优点 $(x^*, \lambda^*)$ 处的 KKT 条件为：

对于增广拉格朗日函数，对 $\lambda$ 求梯度时增广项 $\frac{\beta}{2}\|Ax - b\|^2$ 不含 $\lambda$，视为常数，因此条件 (II) 对两种拉格朗日函数均成立。在最优点处 $Ax^* - b = 0$，对 $x$ 求梯度时增广项的贡献 $\beta A^\top(Ax^* - b) = 0$，条件 (I) 同样不受增广项影响。

在 ALM 第一步中，$x^{k+1}$ 是子问题的最优解。对增广拉格朗日函数关于 $x$ 求梯度并令其为零：

将乘子更新公式 $\lambda^{k+1} = \lambda^k + \beta(Ax^{k+1} - b)$ 代入，得：

式 (IV) 表明每一步迭代中，$(x^{k+1}, \lambda^{k+1})$ 自动满足 KKT 驻点条件 (I) 的形式。剩余需要证明的是可行性条件 $Ax^{k+1} - b \to 0$。

6.4.4 收敛性证明#

假设 $f$ 为凸函数且连续可微，$(x^k, \lambda^k)$ 由 ALM 生成。设 $(x^*, \lambda^*)$ 为满足 KKT 条件的最优点。需要证明 $Ax^{k+1} - b \to 0$（可行性收敛）与 $\lambda^k \to \lambda^*$（乘子收敛）。

由乘子更新公式：

因此证明可行性收敛等价于证明 $\lambda^{k+1} - \lambda^k \to 0$。

构造 Lyapunov 函数. 考虑 $\|\lambda^{k+1} - \lambda^*\|^2$ 的递推。通过加减 $\lambda^k$ 并展开：

对内积项做加减处理，将 $\lambda^k$ 替换为 $\lambda^{k+1}$，利用恒等式整理得：

利用凸性处理内积项. 由 (V) 式，$\lambda^{k+1} - \lambda^k = \beta(Ax^{k+1} - b)$；又由 $Ax^* = b$，故 $Ax^{k+1} - b = A(x^{k+1} - x^*)$。将内积项中的替换并利用 $\langle Av, w \rangle = \langle v, A^\top w \rangle$：

由条件 (I) 和 (IV)：$A^\top \lambda^* = -\nabla f(x^*)$，$A^\top \lambda^{k+1} = -\nabla f(x^{k+1})$，因此：

代入得：

由凸函数的梯度单调性（$f$ 凸 $\Rightarrow$ $\nabla f$ 为单调算子），对任意 $x, y$ 有 $\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq 0$。取 $x = x^{k+1}$，$y = x^*$，得到 $\langle x^{k+1} - x^*, \nabla f(x^*) - \nabla f(x^{k+1}) \rangle \leq 0$，从而：

建立单调递减不等式. 代回得：

移项得：

求和论证. 对 (VII) 从 $k = 0$ 到 $K$ 求和，右侧为 telescoping sum：

右端为有限常数，$K \to \infty$ 时级数收敛，通项必趋于零：$\|\lambda^{k+1} - \lambda^k\| \to 0$。

收敛结论. 由 (V) 式：$\|Ax^{k+1} - b\| = \frac{1}{\beta}\|\lambda^{k+1} - \lambda^k\| \to 0$，可行性残差趋于零。由 (VI) 式，$\{\|\lambda^k - \lambda^*\|^2\}$ 单调递减且非负，因此收敛，从而 $\lambda^k \to \lambda^*$。在适当条件下进一步可推出 $x^k \to x^*$。

当 $f$ 为凸函数时，KKT 条件是最优性的充分条件，因此 ALM 的聚点满足 KKT 条件即为全局最优解。若 $f$ 为强凸函数，最优解 $x^*$ 唯一；若 $f$ 仅为凸函数，最优解可能不唯一，但所有聚点均满足 KKT 条件。

6.4.5 ALM 与 PPA 的等价关系#

对偶函数为 $g(\lambda) = \min_x [\,f(x) + \langle \lambda, Ax - b \rangle\,]$，对偶问题为 $\max_\lambda g(\lambda)$，等价地写成极小化形式 $\min_\lambda [-g(\lambda)]$，记为 (D)。

对 (D) 应用邻近点算法（Proximal Point Algorithm, PPA），步长取 $\alpha = \beta$：

取负号并转为 $\max$：

由 PPA 的隐式梯度迭代形式，(PPA) 等价于：

设在 $\lambda = \lambda^{k+1}$ 处，内层极小化问题的最优解为 $x^{k+1}$，则由 Danskin 定理，$\nabla g(\lambda^{k+1}) = Ax^{k+1} - b$。代入 ($\star$)：

这恰好是 ALM 的乘子更新公式。因此：

这一等价关系揭示了 ALM 的深层结构：ALM 并非仅仅是在拉格朗日函数上加罚项的启发式方法，而是对偶空间中邻近点算法的严格等价形式。这为 ALM 的收敛性提供了来自 PPA 理论的另一条证明路径，也为 ADMM 的推导提供了理论基础。

6.5.1 ALM 处理可分问题的困难#

考虑目标函数可分的约束优化问题：

其中 $f$ 和 $g$ 分别是关于 $x$ 和 $y$ 的函数，目标函数在变量上是可分离的。增广拉格朗日函数为：

若直接使用 ALM，需同时对 $(x, y)$ 求极小。但二次罚项 $\frac{\beta}{2}\|Ax + By - c\|^2$ 中 $x$ 和 $y$ 存在耦合项，无法将两个变量的求解分离，导致子问题求解复杂。

6.5.2 ADMM 的迭代格式#

交替方向乘子法（Alternating Direction Method of Multipliers, ADMM）的核心思想是：不同时对 $x$ 和 $y$ 求极小，而是交替固定一个变量优化另一个，类似于数值线性代数中的 Gauss-Seidel 迭代。迭代格式如下：

第一步固定 $y = y^k$ 关于 $x$ 求极小；第二步将刚算出的 $x^{k+1}$ 代入，固定 $x = x^{k+1}$ 关于 $y$ 求极小；第三步更新对偶变量 $\lambda$。“用上一步最新结果”的策略正是 Gauss-Seidel 迭代的思想。

6.5.3 ADMM 的缩放形式（Scaled Form）#

在实际实现中，ADMM 更常写成缩放形式（scaled form）。定义缩放对偶变量 $u = \lambda / \beta$，则增广拉格朗日函数中的线性项和二次项可以合并：

于是 ADMM 的三步迭代简化为：

缩放形式的优点是每个子问题只需要处理一个二次项 $\frac{\beta}{2}\|\cdot\|^2$，不再出现线性项和二次项的混合，编程实现更简洁。$u$ 的更新也变得更直观——它直接累加约束残差 $Ax^{k+1} + By^{k+1} - c$。

6.5.4 实际使用中的参数选取#

罚参数 $\beta$ 的选择。 $\beta$ 控制了约束满足的”惩罚力度”与子问题求解难度之间的平衡。$\beta$ 过小时约束收敛慢（需要更多迭代才能使 $Ax + By \approx c$），$\beta$ 过大时子问题的条件数变差（二次罚项主导了目标函数，子问题求解变慢）。实践中常用的策略包括：取 $\beta = 1$ 或 $\beta = 1/n$（$n$ 为变量维度）作为初始值；或者采用自适应策略——当原始残差 $\|Ax^{k+1} + By^{k+1} - c\|$ 远大于对偶残差 $\beta\|B(y^{k+1} - y^k)\|$ 时增大 $\beta$，反之减小。

停机准则。 实际中常同时监控两个残差：原始残差 $r^k = Ax^k + By^k - c$（衡量约束满足程度）和对偶残差 $s^k = \beta A^\top B(y^k - y^{k-1})$（衡量目标函数的最优性）。当两者均小于预设阈值时停止迭代。

6.5.5 收敛性证明（凸情形）#

以下假设 $f$ 和 $g$ 均为凸函数。