非线性规划中的近似点梯度法（Proximal Gradient Method）进阶题：带有非光滑复合项与线性等式约束的凸优化问题
题目描述
考虑以下带有非光滑复合项与线性等式约束的凸优化问题：
\[\min_{x \in \mathbb{R}^n} f(x) + g(x) \quad \text{s.t.} \quad Ax = b \]
其中：
- 目标函数 \(f(x)\) 是连续可微的凸函数，其梯度 \(\nabla f(x)\) 是 \(L\)-Lipschitz 连续的（即存在常数 \(L > 0\)，使得对任意 \(x, y\)，有 \(\| \nabla f(x) - \nabla f(y) \| \le L \| x - y \|\)）。
- 函数 \(g(x)\) 是闭凸但可能非光滑的（例如 \(L_1\) 范数 \(\|x\|_1\)、核范数、指示函数等）。
- 约束为线性等式：\(A \in \mathbb{R}^{m \times n}\)，\(b \in \mathbb{R}^m\)，且 \(A\) 行满秩。
本题要求设计一种高效的数值算法来求解此问题。该问题在机器学习、信号处理和统计建模中常见（如稀疏回归、压缩感知等）。难点在于处理非光滑项和线性约束的结合，使得标准的梯度法或投影梯度法无法直接应用。
解题过程
我们将采用近似点梯度法结合增广拉格朗日框架来求解。整个算法称为近似点梯度法的增广拉格朗日形式，也称为ADMM的一种特例或线性化增广拉格朗日法。
第1步：问题转化与增广拉格朗日函数引入
原问题等价于：
\[\min_{x, z} f(x) + g(z) \quad \text{s.t.} \quad Ax = b,\ x = z \]
引入辅助变量 \(z\) 将非光滑项分离，但增加了等式约束 \(x = z\)。定义增广拉格朗日函数：
\[\mathcal{L}_{\rho}(x, z, y, \lambda) = f(x) + g(z) + y^\top (Ax - b) + \frac{\rho}{2} \|Ax - b\|^2 + \lambda^\top (x - z) + \frac{\rho}{2} \|x - z\|^2 \]
其中 \(y \in \mathbb{R}^m\)、\(\lambda \in \mathbb{R}^n\) 是拉格朗日乘子，\(\rho > 0\) 是惩罚参数。这里将两个等式约束分别惩罚并线性化，但为简化，我们通常用更紧凑的形式。
更常用的简化：将 \(Ax = b\) 和 \(x = z\) 合并处理。但实际上，我们通常用近似点梯度法直接处理 \(Ax = b\) 约束。为此，我们将 \(Ax = b\) 融入子问题求解，而非作为惩罚项。这导出了线性约束近似点梯度法的一种实现。
第2步：算法框架——线性约束近似点梯度法
由于 \(f\) 可微、\(g\) 非光滑，且约束为线性等式，我们可以将问题写为：
\[\min_x F(x) := f(x) + g(x) \quad \text{s.t.} \quad Ax = b \]
近似点梯度法的核心思想是：在每一步迭代中，构造 \(F(x)\) 的一个近似模型，并求解一个带约束的近似子问题。
- 构造近似模型：在当前迭代点 \(x_k\)，对光滑部分 \(f\) 进行一阶近似（利用梯度），对非光滑部分 \(g\) 保持原样，并加上一个正则项来控制近似误差：
\[ Q(x; x_k) = f(x_k) + \nabla f(x_k)^\top (x - x_k) + \frac{1}{2t} \|x - x_k\|^2 + g(x) \]
其中 \(t > 0\) 是步长参数，通常取 \(t \le 1/L\) 以保证下降性。
- 约束子问题：在每一步，求解带线性约束的近似点更新：
\[ x_{k+1} = \arg\min_{x} \left\{ f(x_k) + \nabla f(x_k)^\top (x - x_k) + \frac{1}{2t} \|x - x_k\|^2 + g(x) \right\} \]
\[ \text{s.t.} \quad Ax = b \]
忽略常数项 \(f(x_k) - \nabla f(x_k)^\top x_k\)，子问题等价于：
\[ x_{k+1} = \arg\min_{x} \left\{ g(x) + \frac{1}{2t} \|x - (x_k - t \nabla f(x_k))\|^2 \right\} \quad \text{s.t.} \quad Ax = b \]
这个子问题是一个带线性等式约束的近端算子计算。
第3步：子问题的求解
子问题是：
\[\min_x \ g(x) + \frac{1}{2t} \|x - u_k\|^2 \quad \text{s.t.} \quad Ax = b \]
其中 \(u_k = x_k - t \nabla f(x_k)\)。这可以看作求解约束近端映射。
解法：引入拉格朗日乘子 \(y \in \mathbb{R}^m\) 处理约束 \(Ax = b\)，得到拉格朗日函数：
\[\mathcal{L}(x, y) = g(x) + \frac{1}{2t} \|x - u_k\|^2 + y^\top (Ax - b) \]
最优性条件（KKT条件）为：
- 关于 \(x\) 的次梯度条件：\(0 \in \partial g(x) + \frac{1}{t}(x - u_k) + A^\top y\)
- 等式约束：\(Ax = b\)
为高效求解，我们采用对偶法或线性化技术。
具体步骤：
- 定义函数 \(h(x) = g(x) + \frac{1}{2t} \|x - u_k\|^2\)，则子问题是 \(\min_x h(x)\) 受限于 \(Ax = b\)。
- 当 \(g(x)\) 是简单函数（如 \(L_1\) 范数）时，其近端算子有闭式解。但这里因约束存在，无法直接应用。
- 常用技巧：在约束 \(Ax = b\) 下，将 \(x\) 表示为 \(x = x_0 + v\)，其中 \(x_0\) 是特解（满足 \(Ax_0 = b\)），\(v \in \text{Null}(A)\)（即 \(Av = 0\)）。这能将问题转化为无约束问题在零空间上求解。但对大规模问题，零空间基的显式计算成本高。
实际计算方案：采用对偶近似点梯度法（Dual Proximal Gradient Method）来求解该子问题。子问题的对偶问题是光滑的，可用梯度法求解。
- 对偶问题推导：定义 \(p(w) = g(w) + \frac{1}{2t} \|w - u_k\|^2\)，则子问题的对偶函数为 \(D(y) = -p^*(-A^\top y) - b^\top y\)，其中 \(p^*\) 是 \(p\) 的共轭函数。由于 \(p\) 是强凸的，其对偶问题有唯一解，且可通过对 \(y\) 做梯度上升求解。
- 对偶梯度上升涉及计算 \(\text{prox}_{tg}(u_k - t A^\top y)\)，这恰好是无约束近端算子，容易计算。
简化实用方案：当 \(g(x) = \|x\|_1\) 时，可引入分裂技巧，用ADMM直接解原始子问题。但为保持算法一致性，我们通常会将整个原问题的求解转化为线性约束近端梯度法的迭代，其子问题用内点迭代快速求解。
第4步：完整算法流程
我们采用近似点梯度法的增广拉格朗日形式（Proximal Gradient Method with AL），也称为线性化增广拉格朗日法，步骤如下：
- 初始化：选择初始点 \(x_0\) 满足 \(Ax_0 = b\)，初始乘子 \(y_0\)，惩罚参数 \(\rho > 0\)，步长 \(t \in (0, 1/L]\)，容差 \(\epsilon > 0\)。
- 迭代更新（对 \(k = 0, 1, 2, \dots\)）：
a. 梯度步：计算 \(v_k = x_k - t \nabla f(x_k)\)。
b. 近端-投影步：求解
\[ x_{k+1} = \arg\min_x \left\{ g(x) + \frac{1}{2t} \|x - v_k\|^2 + y_k^\top (A x - b) + \frac{\rho}{2} \|A x - b\|^2 \right\} \]
这里将约束 $ Ax = b $ 以增广拉格朗日形式加入，但该子问题仍含二次项 $ \frac{\rho}{2} \|Ax - b\|^2 $，直接解不易。为简化，我们将此二次项在 $ x_k $ 处线性化（类似近似点梯度思想），得到：
\[ x_{k+1} = \arg\min_x \left\{ g(x) + \frac{1}{2t} \|x - (x_k - t(\nabla f(x_k) + A^\top (y_k + \rho (A x_k - b)) ) \|^2 \right\} \]
该更新本质上是**无约束近端算子**：
\[ x_{k+1} = \text{prox}_{t g} \big( x_k - t( \nabla f(x_k) + A^\top (y_k + \rho (A x_k - b)) ) \big) \]
c. 乘子更新：\(y_{k+1} = y_k + \rho (A x_{k+1} - b)\)。
d. 检查收敛：若 \(\|x_{k+1} - x_k\| < \epsilon\) 且 \(\|A x_{k+1} - b\| < \epsilon\)，则停止。
- 输出：\(x_{k+1}\) 作为近似最优解。
注：这里的关键是，在更新 \(x_{k+1}\) 时，将增广拉格朗日项中的二次项线性化，从而将子问题转化为一个无约束的近端计算，大大简化了求解。该线性化技巧的合理性基于梯度 Lipschitz 假设和适当的步长选择。
第5步：收敛性说明
- 若 \(f\) 是凸函数且梯度 Lipschitz 连续，\(g\) 是闭凸函数，且步长 \(t \le 1/(L + \rho \|A^\top A\|)\)，则算法生成的序列 \(\{x_k\}\) 会收敛到原问题的最优解。
- 该收敛性结论源于近似点梯度法在约束问题中的推广，以及增广拉格朗日法的收敛性质。线性化后的子问题相当于在每一步求解一个近似点算子，其误差可控，在适当条件下整体算法收敛。
第6步：实例演示（稀疏回归问题）
考虑一个具体例子：
\[\min_x \frac{1}{2} \|Cx - d\|^2 + \mu \|x\|_1 \quad \text{s.t.} \quad A x = b \]
其中 \(C \in \mathbb{R}^{p \times n}\)，\(d \in \mathbb{R}^p\)，\(\mu > 0\)，\(A \in \mathbb{R}^{m \times n}\)，\(b \in \mathbb{R}^m\)。这里 \(f(x) = \frac{1}{2} \|Cx - d\|^2\)，\(g(x) = \mu \|x\|_1\)。
计算步骤：
- 计算梯度：\(\nabla f(x) = C^\top (Cx - d)\)。
- Lipschitz 常数 \(L = \|C^\top C\|\)（谱范数）。
- 近端算子：对 \(g(x) = \mu \|x\|_1\)，有 \(\text{prox}_{t g}(v) = \text{sign}(v) \max(|v| - t\mu, 0)\)（软阈值算子）。
- 代入上述算法框架，迭代更新公式为：
- \(v_k = x_k - t [C^\top (C x_k - d) + A^\top (y_k + \rho (A x_k - b))]\)
- \(x_{k+1} = \text{soft-threshold}(v_k, t \mu)\)
- \(y_{k+1} = y_k + \rho (A x_{k+1} - b)\)
- 选择 \(t = 1/(L + \rho \|A^\top A\|)\)，初始化 \(x_0\) 满足 \(A x_0 = b\)（例如用最小二乘解），\(y_0 = 0\)，即可迭代求解。
总结
本问题结合了非光滑复合项与线性等式约束，通过近似点梯度法的增广拉格朗日形式，将约束融入梯度更新，并利用近端算子处理非光滑项，使得每步迭代计算高效。此方法广泛应用于稀疏优化、基追踪、机器学习正则化问题等。关键是理解近似点算子的作用、线性化技巧的应用，以及收敛条件的设置。