非线性规划中的交替方向乘子法(ADMM)进阶题
题目描述
考虑一个带有可分离结构的非线性规划问题：
最小化 \(f(x) + g(y)\)
满足约束 \(Ax + By = c\)，
其中 \(x \in \mathbb{R}^n\)，\(y \in \mathbb{R}^m\)，\(A\) 和 \(B\) 是矩阵，\(c\) 是向量。函数 \(f\) 和 \(g\) 是非线性凸函数，但可能不可微（如 \(f(x) = \|x\|_1\)，\(g(y) = \frac{1}{2}\|y\|^2\)）。目标是利用交替方向乘子法（ADMM）求解该问题，并分析其收敛性。
解题过程
- 问题转化与增广拉格朗日函数
ADMM的核心思想是将原问题分解为两个子问题，交替优化。首先引入增广拉格朗日函数：
\[ L_\rho(x, y, \lambda) = f(x) + g(y) + \lambda^\top (Ax + By - c) + \frac{\rho}{2} \|Ax + By - c\|^2, \]
其中 \(\lambda\) 是拉格朗日乘子，\(\rho > 0\) 是惩罚参数。增广项 \(\frac{\rho}{2} \|Ax + By - c\|^2\) 确保收敛性。
- ADMM迭代步骤
每轮迭代包含三个步骤（交替优化 \(x\) 和 \(y\)，更新乘子 \(\lambda\)）：- x-子问题：固定 \(y^k\) 和 \(\lambda^k\)，求解
\[ x^{k+1} = \arg\min_x \left( f(x) + \frac{\rho}{2} \left\| Ax + By^k - c + \frac{\lambda^k}{\rho} \right\|^2 \right). \]
若 $ f $ 不可微，此步骤可能需近似方法（如软阈值算子处理 $ \|x\|_1 $）。
- y-子问题：固定 \(x^{k+1}\) 和 \(\lambda^k\)，求解
\[ y^{k+1} = \arg\min_y \left( g(y) + \frac{\rho}{2} \left\| Ax^{k+1} + By - c + \frac{\lambda^k}{\rho} \right\|^2 \right). \]
- 乘子更新：
\[ \lambda^{k+1} = \lambda^k + \rho (Ax^{k+1} + By^{k+1} - c). \]
该步骤对偶变量 $ \lambda $ 沿约束违反方向调整。
-
收敛性分析
- 若 \(f\) 和 \(g\) 是闭凸函数，且拉格朗日函数有鞍点，则ADMM收敛到最优解。
- 收敛速率通常为 \(O(1/k)\)（\(k\) 为迭代次数），但实际性能依赖 \(\rho\) 的选择。自适应调整 \(\rho\)（如根据原始残差和对偶残差比例）可加速收敛。
-
实例验证
假设 \(f(x) = |x|\)（L1范数），\(g(y) = y^2\)，约束为 \(x - y = 0\)。- x-子问题：通过软阈值算子解 \(x^{k+1} = S_{1/\rho}(y^k - \lambda^k / \rho)\)，其中 \(S_\kappa(a) = \text{sign}(a) \max(|a| - \kappa, 0)\)。
- y-子问题：解二次函数 \(y^{k+1} = \frac{\rho(x^{k+1} + \lambda^k / \rho)}{2 + \rho}\)。
- 迭代至残差 \(|x^k - y^k|\) 小于阈值。
总结
ADMM通过分解问题为简单子问题，高效处理不可微函数和可分离结构。其优势在于子问题常有解析解或易求解形式，适用于大规模优化。