非线性规划中的增广拉格朗日交替方向乘子法（Augmented Lagrangian Alternating Direction Method of Multipliers, AL-ADMM）基础题
字数 3801 2025-12-20 19:00:15

非线性规划中的增广拉格朗日交替方向乘子法（Augmented Lagrangian Alternating Direction Method of Multipliers, AL-ADMM）基础题

题目描述

考虑如下带有线性等式约束和可分离结构的凸非线性规划问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^n, z \in \mathbb{R}^m} \quad & f(x) + g(z) \\ \text{s.t.} \quad & A x + B z = c \end{aligned} \]

其中：

  • \(f: \mathbb{R}^n \to \mathbb{R}\) 和 \(g: \mathbb{R}^m \to \mathbb{R}\) 都是凸函数（可能非光滑）。
  • \(A \in \mathbb{R}^{p \times n}\), \(B \in \mathbb{R}^{p \times m}\), \(c \in \mathbb{R}^{p}\) 给定。
  • 问题具有可分离结构：目标函数是 \(f(x)\) 和 \(g(z)\) 之和，约束是变量 \(x\) 和 \(z\) 的线性组合。

要求：使用增广拉格朗日交替方向乘子法（AL-ADMM） 求解该问题。你需要详细解释ADMM的迭代格式推导、每一步的计算含义、算法流程，并讨论其收敛性质。

解题过程

第一步：回顾增广拉格朗日函数

对于带等式约束的优化问题，标准增广拉格朗日函数（Augmented Lagrangian）定义为：

\[\mathcal{L}_{\rho}(x, z, \lambda) = f(x) + g(z) + \lambda^T (A x + B z - c) + \frac{\rho}{2} \| A x + B z - c \|^2 \]

其中：

  • \(\lambda \in \mathbb{R}^p\) 是对偶变量（拉格朗日乘子）。
  • \(\rho > 0\) 是惩罚参数。
  • 最后一项 \(\frac{\rho}{2} \| A x + B z - c \|^2\) 是二次惩罚项，用于增强算法的鲁棒性和收敛性。

第二步：ADMM的核心思想

交替方向乘子法（ADMM）结合了对偶分解和增广拉格朗日方法的优点。其基本思想是：

  • 由于问题具有可分离结构（\(x\) 和 \(z\) 在目标函数和约束中分开），我们可以交替地优化 \(x\) 和 \(z\)，而不是同时更新。
  • 每一步只针对一个变量子集进行优化，从而将复杂问题分解为两个较简单的子问题。
  • 在每次更新变量后，立即更新对偶变量 \(\lambda\)，以促进约束满足。

第三步：推导ADMM迭代格式

ADMM的迭代分为三个步骤（给定初始点 \(z^0, \lambda^0\) 和参数 \(\rho > 0\)）：

  1. x-更新：固定 \(z^k\) 和 \(\lambda^k\)，求解关于 \(x\) 的子问题：

\[ x^{k+1} = \arg\min_{x} \left\{ f(x) + \frac{\rho}{2} \| A x + B z^k - c + \frac{\lambda^k}{\rho} \|^2 \right\} \]

推导：从增广拉格朗日函数中提取与 \(x\) 相关的项：

\[ \mathcal{L}_{\rho}(x, z^k, \lambda^k) = f(x) + g(z^k) + \lambda^{k^T} (A x + B z^k - c) + \frac{\rho}{2} \| A x + B z^k - c \|^2 \]

忽略与 \(x\) 无关的项，并利用恒等式：

\[ \lambda^{k^T}(A x) + \frac{\rho}{2} \|A x + d^k\|^2 = \frac{\rho}{2} \|A x + d^k + \frac{\lambda^k}{\rho}\|^2 - \frac{1}{2\rho} \|\lambda^k\|^2 \]

其中 \(d^k = B z^k - c\)。最终得到上述 \(x\)-更新形式。

  1. z-更新：固定 \(x^{k+1}\) 和 \(\lambda^k\)，求解关于 \(z\) 的子问题：

\[ z^{k+1} = \arg\min_{z} \left\{ g(z) + \frac{\rho}{2} \| A x^{k+1} + B z - c + \frac{\lambda^k}{\rho} \|^2 \right\} \]

推导与 \(x\)-更新类似，提取与 \(z\) 相关的项。

  1. 对偶变量更新：

\[ \lambda^{k+1} = \lambda^k + \rho (A x^{k+1} + B z^{k+1} - c) \]

这实际上是对偶上升（Dual Ascent）步骤：以步长 \(\rho\) 沿约束违反方向更新乘子。

第四步：算法流程

  1. 初始化：选择初始 \(z^0\), \(\lambda^0\), 惩罚参数 \(\rho > 0\)，设定容忍误差 \(\epsilon > 0\) 和最大迭代次数 \(K\)。
  2. 迭代：对于 \(k = 0, 1, 2, \dots, K-1\)：
    • 执行 \(x\)-更新，得到 \(x^{k+1}\)。
    • 执行 \(z\)-更新，得到 \(z^{k+1}\)。
    • 执行对偶变量更新，得到 \(\lambda^{k+1}\)。
    • 计算原始残差 \(r^{k+1} = A x^{k+1} + B z^{k+1} - c\) 和对偶残差 \(s^{k+1} = \rho A^T B (z^{k+1} - z^k)\)（后者的推导基于最优性条件）。
    • 如果 \(\|r^{k+1}\| \leq \epsilon\) 且 \(\|s^{k+1}\| \leq \epsilon\)，则停止迭代。
  3. 输出：近似最优解 \((x^{k+1}, z^{k+1})\)。

第五步：子问题的处理与简化

  • x-更新子问题：本质上是在最小化 \(f(x)\) 加上一个关于 \(x\) 的二次项。如果 \(f(x)\) 是简单的（例如二次函数、\(\ell_1\) 范数等），可能有闭式解或可通过近端算子高效求解。
  • z-更新子问题：类似处理。
  • 关键优势：ADMM将原问题分解为两个更小、更易处理的子问题，尤其适合 \(f\) 和 \(g\) 具有特殊结构（如可分离、有近端映射）的情形。

第六步：收敛性讨论

对于凸问题（\(f\) 和 \(g\) 为凸函数）且 \(\rho > 0\)，ADMM具有以下收敛性质：

  1. 残差收敛：原始残差 \(r^k = A x^k + B z^k - c\) 收敛到零，即约束最终被满足。
  2. 目标函数收敛：目标函数值 \(f(x^k) + g(z^k)\) 收敛到最优值。
  3. 对偶变量收敛：若原问题存在唯一对偶解，则 \(\lambda^k\) 收敛到对偶最优解；否则，\(\lambda^k\) 的某个聚点是对偶最优。
  4. 收敛速度：ADMM通常具有次线性收敛速率（\(O(1/k)\)），但对于强凸问题可能更快。

第七步：简单数值示例（示意）

假设：

  • \(f(x) = \frac{1}{2} x^2\), \(g(z) = |z|\)（绝对值，非光滑）。
  • 约束：\(x - z = 0\)（即 \(A=1, B=-1, c=0\)）。
  • 初始值：\(z^0 = 0\), \(\lambda^0 = 0\), \(\rho = 1\)。

迭代步骤：

  1. x-更新：子问题为 \(\min_x \frac{1}{2} x^2 + \frac{1}{2} \|x - z^k + \lambda^k\|^2\)，求导得闭式解：\(x^{k+1} = \frac{z^k - \lambda^k}{2}\)。
  2. z-更新：子问题为 \(\min_z |z| + \frac{1}{2} \|x^{k+1} - z + \lambda^k\|^2\)，其解可通过软阈值算子给出：\(z^{k+1} = S_{1}(x^{k+1} + \lambda^k)\)，其中 \(S_{\kappa}(a) = \operatorname{sign}(a) \max(|a| - \kappa, 0)\)。
  3. 更新 \(\lambda\)：\(\lambda^{k+1} = \lambda^k + (x^{k+1} - z^{k+1})\)。

重复直到收敛，最终 \(x^* = z^* = 0\)，\(\lambda^* = 0\)。

总结

增广拉格朗日交替方向乘子法（AL-ADMM）通过将原问题分解为交替优化的子问题，有效求解具有可分离结构的约束优化问题。其核心是三个交替步骤：更新第一个变量、更新第二个变量、更新对偶乘子。该方法结合了分解的灵活性和增广拉格朗日的鲁棒性，在信号处理、机器学习、统计学习等领域有广泛应用。

非线性规划中的增广拉格朗日交替方向乘子法（Augmented Lagrangian Alternating Direction Method of Multipliers, AL-ADMM）基础题 题目描述 考虑如下带有线性等式约束和可分离结构的凸非线性规划问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n, z \in \mathbb{R}^m} \quad & f(x) + g(z) \\ \text{s.t.} \quad & A x + B z = c \end{aligned} \] 其中： \( f: \mathbb{R}^n \to \mathbb{R} \) 和 \( g: \mathbb{R}^m \to \mathbb{R} \) 都是凸函数（可能非光滑）。 \( A \in \mathbb{R}^{p \times n} \), \( B \in \mathbb{R}^{p \times m} \), \( c \in \mathbb{R}^{p} \) 给定。 问题具有可分离结构：目标函数是 \( f(x) \) 和 \( g(z) \) 之和，约束是变量 \( x \) 和 \( z \) 的线性组合。 要求：使用 增广拉格朗日交替方向乘子法（AL-ADMM） 求解该问题。你需要详细解释ADMM的迭代格式推导、每一步的计算含义、算法流程，并讨论其收敛性质。 解题过程 第一步：回顾增广拉格朗日函数 对于带等式约束的优化问题，标准增广拉格朗日函数（Augmented Lagrangian）定义为： \[ \mathcal{L}_ {\rho}(x, z, \lambda) = f(x) + g(z) + \lambda^T (A x + B z - c) + \frac{\rho}{2} \| A x + B z - c \|^2 \] 其中： \(\lambda \in \mathbb{R}^p\) 是对偶变量（拉格朗日乘子）。 \(\rho > 0\) 是惩罚参数。 最后一项 \(\frac{\rho}{2} \| A x + B z - c \|^2\) 是二次惩罚项，用于增强算法的鲁棒性和收敛性。 第二步：ADMM的核心思想 交替方向乘子法（ADMM）结合了 对偶分解 和 增广拉格朗日方法 的优点。其基本思想是： 由于问题具有可分离结构（\(x\) 和 \(z\) 在目标函数和约束中分开），我们可以 交替地 优化 \(x\) 和 \(z\)，而不是同时更新。 每一步只针对一个变量子集进行优化，从而将复杂问题分解为两个较简单的子问题。 在每次更新变量后，立即更新对偶变量 \(\lambda\)，以促进约束满足。 第三步：推导ADMM迭代格式 ADMM的迭代分为三个步骤（给定初始点 \(z^0, \lambda^0\) 和参数 \(\rho > 0\)）： x-更新 ：固定 \(z^k\) 和 \(\lambda^k\)，求解关于 \(x\) 的子问题： \[ x^{k+1} = \arg\min_ {x} \left\{ f(x) + \frac{\rho}{2} \| A x + B z^k - c + \frac{\lambda^k}{\rho} \|^2 \right\} \] 推导：从增广拉格朗日函数中提取与 \(x\) 相关的项： \[ \mathcal{L}_ {\rho}(x, z^k, \lambda^k) = f(x) + g(z^k) + \lambda^{k^T} (A x + B z^k - c) + \frac{\rho}{2} \| A x + B z^k - c \|^2 \] 忽略与 \(x\) 无关的项，并利用恒等式： \[ \lambda^{k^T}(A x) + \frac{\rho}{2} \|A x + d^k\|^2 = \frac{\rho}{2} \|A x + d^k + \frac{\lambda^k}{\rho}\|^2 - \frac{1}{2\rho} \|\lambda^k\|^2 \] 其中 \(d^k = B z^k - c\)。最终得到上述 \(x\)-更新形式。 z-更新 ：固定 \(x^{k+1}\) 和 \(\lambda^k\)，求解关于 \(z\) 的子问题： \[ z^{k+1} = \arg\min_ {z} \left\{ g(z) + \frac{\rho}{2} \| A x^{k+1} + B z - c + \frac{\lambda^k}{\rho} \|^2 \right\} \] 推导与 \(x\)-更新类似，提取与 \(z\) 相关的项。 对偶变量更新 ： \[ \lambda^{k+1} = \lambda^k + \rho (A x^{k+1} + B z^{k+1} - c) \] 这实际上是对偶上升（Dual Ascent）步骤：以步长 \(\rho\) 沿约束违反方向更新乘子。 第四步：算法流程 初始化 ：选择初始 \(z^0\), \(\lambda^0\), 惩罚参数 \(\rho > 0\)，设定容忍误差 \(\epsilon > 0\) 和最大迭代次数 \(K\)。 迭代 ：对于 \(k = 0, 1, 2, \dots, K-1\)： 执行 \(x\)-更新，得到 \(x^{k+1}\)。 执行 \(z\)-更新，得到 \(z^{k+1}\)。 执行对偶变量更新，得到 \(\lambda^{k+1}\)。 计算原始残差 \(r^{k+1} = A x^{k+1} + B z^{k+1} - c\) 和对偶残差 \(s^{k+1} = \rho A^T B (z^{k+1} - z^k)\)（后者的推导基于最优性条件）。 如果 \(\|r^{k+1}\| \leq \epsilon\) 且 \(\|s^{k+1}\| \leq \epsilon\)，则停止迭代。 输出 ：近似最优解 \((x^{k+1}, z^{k+1})\)。 第五步：子问题的处理与简化 x-更新子问题 ：本质上是在最小化 \(f(x)\) 加上一个关于 \(x\) 的二次项。如果 \(f(x)\) 是简单的（例如二次函数、\(\ell_ 1\) 范数等），可能有闭式解或可通过近端算子高效求解。 z-更新子问题 ：类似处理。 关键优势 ：ADMM将原问题分解为两个更小、更易处理的子问题，尤其适合 \(f\) 和 \(g\) 具有特殊结构（如可分离、有近端映射）的情形。 第六步：收敛性讨论 对于凸问题（\(f\) 和 \(g\) 为凸函数）且 \(\rho > 0\)，ADMM具有以下收敛性质： 残差收敛 ：原始残差 \(r^k = A x^k + B z^k - c\) 收敛到零，即约束最终被满足。 目标函数收敛 ：目标函数值 \(f(x^k) + g(z^k)\) 收敛到最优值。 对偶变量收敛 ：若原问题存在唯一对偶解，则 \(\lambda^k\) 收敛到对偶最优解；否则，\(\lambda^k\) 的某个聚点是对偶最优。 收敛速度 ：ADMM通常具有次线性收敛速率（\(O(1/k)\)），但对于强凸问题可能更快。 第七步：简单数值示例（示意） 假设： \(f(x) = \frac{1}{2} x^2\), \(g(z) = |z|\)（绝对值，非光滑）。 约束：\(x - z = 0\)（即 \(A=1, B=-1, c=0\)）。 初始值：\(z^0 = 0\), \(\lambda^0 = 0\), \(\rho = 1\)。 迭代步骤： x-更新 ：子问题为 \(\min_ x \frac{1}{2} x^2 + \frac{1}{2} \|x - z^k + \lambda^k\|^2\)，求导得闭式解：\(x^{k+1} = \frac{z^k - \lambda^k}{2}\)。 z-更新 ：子问题为 \(\min_ z |z| + \frac{1}{2} \|x^{k+1} - z + \lambda^k\|^2\)，其解可通过软阈值算子给出：\(z^{k+1} = S_ {1}(x^{k+1} + \lambda^k)\)，其中 \(S_ {\kappa}(a) = \operatorname{sign}(a) \max(|a| - \kappa, 0)\)。 更新 \(\lambda\) ：\(\lambda^{k+1} = \lambda^k + (x^{k+1} - z^{k+1})\)。 重复直到收敛，最终 \(x^* = z^* = 0\)，\(\lambda^* = 0\)。 总结 增广拉格朗日交替方向乘子法（AL-ADMM）通过将原问题分解为交替优化的子问题，有效求解具有可分离结构的约束优化问题。其核心是三个交替步骤：更新第一个变量、更新第二个变量、更新对偶乘子。该方法结合了分解的灵活性和增广拉格朗日的鲁棒性，在信号处理、机器学习、统计学习等领域有广泛应用。