非线性规划中的交替方向乘子法（Alternating Direction Method of Multipliers, ADMM）基础题
题目描述
考虑以下带线性等式约束的凸优化问题：
\[\min_{x, z} \quad f(x) + g(z) \]
\[ \text{s.t.} \quad Ax + Bz = c \]
其中，\(x \in \mathbb{R}^n\)，\(z \in \mathbb{R}^m\)，\(A \in \mathbb{R}^{p \times n}\)，\(B \in \mathbb{R}^{p \times m}\)，\(c \in \mathbb{R}^p\)。函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 和 \(g: \mathbb{R}^m \to \mathbb{R}\) 都是凸函数，但不一定光滑（例如可能包含L1正则项或指示函数）。要求使用交替方向乘子法（ADMM）求解该问题，并解释其每一步的物理意义和更新规则。
解题过程循序渐进讲解
步骤1：理解问题结构与ADMM思想
ADMM是一种旨在将原问题分解为更易求解子问题的算法。它结合了对偶分解（Dual Decomposition）和增广拉格朗日方法（Augmented Lagrangian Method）的优点。
- 原问题：由于约束 \(Ax + Bz = c\) 将变量 \(x\) 和 \(z\) 耦合在一起，直接求解可能困难。
- 核心思想：通过引入对偶变量（拉格朗日乘子）和增广项，将问题分解为交替更新 \(x\)、\(z\) 和乘子的三个子问题。每个子问题只依赖于部分变量，从而简化计算。
步骤2：构造增广拉格朗日函数
首先，定义拉格朗日乘子向量 \(y \in \mathbb{R}^p\)。增广拉格朗日函数为：
\[L_\rho(x, z, y) = f(x) + g(z) + y^T (Ax + Bz - c) + \frac{\rho}{2} \|Ax + Bz - c\|_2^2 \]
其中：
- \(y^T (Ax + Bz - c)\) 是标准拉格朗日项。
- \(\frac{\rho}{2} \|Ax + Bz - c\|_2^2\) 是增广项，\(\rho > 0\) 为惩罚参数。
- 增广项的作用：改善收敛性，使函数在约束违反时增加二次惩罚，同时保持凸性。
步骤3：ADMM迭代格式
ADMM通过以下三步交替更新变量（第 \(k\) 次迭代）：
- 更新 \(x\)：
\[ x^{k+1} = \arg\min_{x} L_\rho(x, z^k, y^k) \]
即固定 \(z^k\) 和 \(y^k\)，最小化关于 \(x\) 的部分：
\[ x^{k+1} = \arg\min_{x} \left( f(x) + \frac{\rho}{2} \|Ax + Bz^k - c + \frac{1}{\rho} y^k \|_2^2 \right) \]
这里利用了配方技巧：将增广拉格朗日函数中的线性项与二次项合并为平方形式（忽略与 \(x\) 无关的常数）。
- 更新 \(z\)：
\[ z^{k+1} = \arg\min_{z} L_\rho(x^{k+1}, z, y^k) \]
固定 \(x^{k+1}\) 和 \(y^k\)，最小化关于 \(z\) 的部分：
\[ z^{k+1} = \arg\min_{z} \left( g(z) + \frac{\rho}{2} \|Ax^{k+1} + Bz - c + \frac{1}{\rho} y^k \|_2^2 \right) \]
- 更新对偶变量 \(y\)：
\[ y^{k+1} = y^k + \rho (Ax^{k+1} + Bz^{k+1} - c) \]
这是对偶变量的梯度上升步骤，步长为 \(\rho\)。物理意义：根据当前约束违反量 \(Ax^{k+1} + Bz^{k+1} - c\) 调整乘子，以逐步满足等式约束。
步骤4：具体化例子便于理解
假设一个简单实例：
- \(f(x) = \frac{1}{2} \|x\|_2^2\)（凸且光滑）
- \(g(z) = \lambda \|z\|_1\)（凸但不光滑，例如L1正则化，\(\lambda > 0\)）
- 约束：\(x - z = 0\)（即 \(A = I\)，\(B = -I\)，\(c = 0\)）
此时增广拉格朗日函数为：
\[L_\rho(x, z, y) = \frac{1}{2} \|x\|_2^2 + \lambda \|z\|_1 + y^T (x - z) + \frac{\rho}{2} \|x - z\|_2^2 \]
ADMM迭代变为：
- 更新 \(x\)：
\[ x^{k+1} = \arg\min_{x} \left( \frac{1}{2} \|x\|_2^2 + \frac{\rho}{2} \|x - z^k + \frac{1}{\rho} y^k \|_2^2 \right) \]
这是一个二次函数最小化问题，可直接求导得闭式解：
\[ x^{k+1} = \frac{\rho (z^k - \frac{1}{\rho} y^k)}{1 + \rho} = \frac{\rho z^k - y^k}{1 + \rho} \]
- 更新 \(z\)：
\[ z^{k+1} = \arg\min_{z} \left( \lambda \|z\|_1 + \frac{\rho}{2} \|x^{k+1} - z + \frac{1}{\rho} y^k \|_2^2 \right) \]
这是一个Lasso问题，其解可通过软阈值（soft-thresholding）算子给出：
\[ z^{k+1} = S_{\lambda / \rho} \left( x^{k+1} + \frac{1}{\rho} y^k \right) \]
其中软阈值算子定义为：\(S_\kappa(a) = \text{sign}(a) \max(|a| - \kappa, 0)\)（按分量作用）。
- 更新 \(y\)：
\[ y^{k+1} = y^k + \rho (x^{k+1} - z^{k+1}) \]
步骤5：收敛条件与参数选择
- 停止准则：通常基于原始残差 \(r^k = Ax^k + Bz^k - c\) 和对偶残差 \(s^k = \rho A^T B (z^k - z^{k-1})\) 的范数是否小于给定容差。
常用条件：
\[ \|r^k\|_2 \leq \epsilon^{\text{pri}} \quad \text{且} \quad \|s^k\|_2 \leq \epsilon^{\text{dual}} \]
其中 \(\epsilon^{\text{pri}}\) 和 \(\epsilon^{\text{dual}}\) 根据问题尺度设定。
- 参数 \(\rho\)：影响收敛速度。可固定（如 \(\rho = 1\)）或采用自适应策略（根据残差比例调整）。
步骤6：算法总结与特点
- 分解性：ADMM将耦合问题分解为交替求解 \(x\) 和 \(z\) 的子问题，每个子问题可能因 \(f\) 或 \(g\) 的特殊结构而有高效解法（如近端算子、闭式解等）。
- 适用性：尤其适合目标函数可分离且约束为线性的凸优化问题，广泛应用于机器学习、信号处理、分布式优化等领域。
- 收敛性：对于凸问题，在较温和条件下（如 \(f, g\) 闭凸且拉格朗日函数有鞍点），ADMM能保证收敛到全局最优解。
通过以上步骤，你可以理解ADMM的基本框架、迭代更新规则及其在实际简单例子中的应用。