非线性规划中的交替方向乘子法基础题

题目描述：
考虑以下可分离结构的凸优化问题：

\[\begin{aligned} \min_{x, y} \quad & f(x) + g(y) \\ \text{s.t.} \quad & Ax + By = c \end{aligned} \]

其中 \(x \in \mathbb{R}^n\), \(y \in \mathbb{R}^m\), \(A \in \mathbb{R}^{p \times n}\), \(B \in \mathbb{R}^{p \times m}\), \(c \in \mathbb{R}^p\)。函数 \(f\) 和 \(g\) 是凸函数，但不一定可微。例如，设 \(f(x) = x^2\), \(g(y) = |y|\), \(A = [1]\), \(B = [1]\), \(c = 1\)，则问题变为：

\[\min_{x, y} x^2 + |y| \quad \text{s.t.} \quad x + y = 1 \]

解题过程：

1. 问题分析
   目标函数包含两个可分离的变量 \(x\) 和 \(y\)，并通过线性等式约束耦合。直接求解因绝对值函数 \(|y|\) 不可微而复杂。交替方向乘子法（ADMM）通过分解思想，将问题拆分为交替优化 \(x\) 和 \(y\) 的子问题。

2. 增广拉格朗日函数构造
   引入拉格朗日乘子 \(\lambda \in \mathbb{R}^p\) 和惩罚参数 \(\rho > 0\)，构造增广拉格朗日函数：

\[ L_\rho(x, y, \lambda) = f(x) + g(y) + \lambda^\top (Ax + By - c) + \frac{\rho}{2} \|Ax + By - c\|^2 \]

其中二次惩罚项 \(\frac{\rho}{2} \|Ax + By - c\|^2\) 增强收敛性。代入示例参数：

\[ L_\rho(x, y, \lambda) = x^2 + |y| + \lambda (x + y - 1) + \frac{\rho}{2} (x + y - 1)^2 \]

3. ADMM迭代步骤
   ADMM按以下顺序交替更新变量：
   • 步骤1：更新 \(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] \]

 示例中：  

\[ x^{k+1} = \arg\min_x \left[ x^2 + \frac{\rho}{2} \left( x + y^k - 1 + \frac{\lambda^k}{\rho} \right)^2 \right] \]

 此为二次函数求导得闭式解：

\[ x^{k+1} = \frac{\rho (1 - y^k) - \lambda^k}{2 + \rho} \]

• 步骤2：更新 \(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] \]

 示例中：

\[ y^{k+1} = \arg\min_y \left[ |y| + \frac{\rho}{2} \left( x^{k+1} + y - 1 + \frac{\lambda^k}{\rho} \right)^2 \right] \]

 利用软阈值算子（soft-thresholding）：

\[ y^{k+1} = S_{1/\rho} \left( 1 - x^{k+1} - \frac{\lambda^k}{\rho} \right) \]

 其中 $S_\kappa(a) = \text{sign}(a) \max(|a| - \kappa, 0)$.

• 步骤3：更新乘子 \(\lambda\)

\[ \lambda^{k+1} = \lambda^k + \rho (Ax^{k+1} + By^{k+1} - c) \]

 示例中：

\[ \lambda^{k+1} = \lambda^k + \rho (x^{k+1} + y^{k+1} - 1) \]

4. 收敛性与初始化

   • 迭代直至残差 \(\|Ax^{k+1} + By^{k+1} - c\| < \epsilon\) 或达到最大迭代次数。
   • 初始值可选 \(y^0 = 0\), \(\lambda^0 = 0\), \(\rho = 1\)。ADMM对凸问题保证收敛到全局最优。

5. 示例迭代演示
   取 \(\rho = 1\), \(y^0 = 0\), \(\lambda^0 = 0\)：

   • 迭代1：
     \(x^1 = \frac{1 \cdot (1 - 0) - 0}{2 + 1} = \frac{1}{3} \approx 0.333\)
     \(y^1 = S_{1} \left( 1 - 0.333 - 0 \right) = S_{1}(0.667) = \text{sign}(0.667) \max(0.667 - 1, 0) = 0\)
     \(\lambda^1 = 0 + 1 \cdot (0.333 + 0 - 1) = -0.667\)
   • 迭代2：
     \(x^2 = \frac{1 \cdot (1 - 0) - (-0.667)}{3} = \frac{1.667}{3} \approx 0.556\)
     \(y^2 = S_{1}(1 - 0.556 + 0.667) = S_{1}(1.111) = 1.111 - 1 = 0.111\)
     继续迭代直至约束残差接近0，最终解逼近 \(x^* = 0.5, y^* = 0.5\)。

ADMM通过分解和交替优化，高效处理可分离结构的非线性规划问题。