近似点梯度法(Proximal Gradient Method)进阶题：非光滑复合优化问题
题目描述
考虑如下形式的非光滑复合优化问题：
\[\min_{x \in \mathbb{R}^n} \quad F(x) = f(x) + g(x) \]
其中：
- \(f(x)\) 是一个可微函数（不一定凸），且其梯度 \(\nabla f(x)\) 满足 Lipschitz 连续条件，即存在常数 \(L > 0\) 使得：
\[ \| \nabla f(x) - \nabla f(y) \| \le L \| x - y \|, \quad \forall x, y \in \mathbb{R}^n \]
- \(g(x)\) 是一个非光滑、但“简单”的凸函数，其近似点算子（proximal operator）是容易计算的。例如，\(g(x)\) 可以是 L1 范数 \(\|x\|_1\)、L2 范数 \(\|x\|_2\)、指示函数（用于表示约束）等。
目标：设计一个基于近似点梯度法（Proximal Gradient Method, PGM）的求解方案，并引入加速技术（如 FISTA 加速）以提升收敛速度，同时处理 \(f(x)\) 可能为非凸的情形。
解题过程
1. 理解问题的结构
- 目标函数 \(F(x)\) 被分解为两部分：光滑项 \(f(x)\) 和非光滑项 \(g(x)\)。
- 如果 \(f(x)\) 是凸的，该问题称为复合凸优化；如果 \(f(x)\) 非凸，则为复合非凸优化，难度更高。
- 关键思想：利用梯度下降处理 \(f(x)\)，用近似点算子处理 \(g(x)\)，交替进行。
2. 近似点算子（Proximal Operator）的定义
对于给定的 \(g(x)\) 和步长 \(t > 0\)，近似点算子定义为：
\[\text{prox}_{t g}(z) = \arg\min_{x} \left\{ g(x) + \frac{1}{2t} \| x - z \|^2 \right\} \]
这个算子可以看作是在 \(z\) 附近，用二次项正则化 \(g(x)\) 后的极小化操作。对于许多常见的 \(g(x)\)，例如 L1 范数、L2 范数、指示函数等，其近似点算子有闭式解或高效算法。
举例：若 \(g(x) = \lambda \|x\|_1\)（L1 范数，λ > 0），则近似点算子就是著名的软阈值函数：
\[[\text{prox}_{t g}(z)]_i = \text{sign}(z_i) \cdot \max(|z_i| - t\lambda, 0) \]
3. 基本近似点梯度法（PGM）的迭代格式
给定初始点 \(x^{(0)}\)，步长 \(t_k\)（通常取 \(t_k = 1/L\) 或通过线搜索确定），迭代更新为：
\[x^{(k+1)} = \text{prox}_{t_k g} \left( x^{(k)} - t_k \nabla f(x^{(k)}) \right) \]
几何解释：
- 先对光滑部分执行一步梯度下降：\(y^{(k)} = x^{(k)} - t_k \nabla f(x^{(k)})\)。
- 再对非光滑部分应用近似点算子，相当于在 \(y^{(k)}\) 附近求解一个带二次正则化的子问题。
当 \(f\) 凸且 \(t_k \in (0, 2/L]\) 时，PGM 可保证收敛到全局最优解，且目标函数值以 \(O(1/k)\) 速率下降。
4. 加速近似点梯度法（FISTA）
为了提升收敛速度，可引入 Nesterov 加速技术，得到 FISTA（Fast Iterative Shrinkage-Thresholding Algorithm）算法。迭代格式如下：
- 初始化 \(x^{(0)} = y^{(1)}\)，\(t_1 = 1\)。
- 对于 \(k \ge 1\)：
- 更新步长：\(t_{k+1} = \frac{1 + \sqrt{1 + 4 t_k^2}}{2}\)。
- 计算辅助点：\(y^{(k+1)} = x^{(k)} + \frac{t_k - 1}{t_{k+1}} (x^{(k)} - x^{(k-1)})\)（这是一个外推步，引入动量）。
- 执行近似点梯度步：
\[ x^{(k+1)} = \text{prox}_{t g} \left( y^{(k+1)} - t \nabla f(y^{(k+1)}) \right) \]
其中步长 $ t = 1/L $ 或通过线搜索确定。
FISTA 在凸情形下可将收敛速率提升至 \(O(1/k^2)\)。
5. 处理非凸 \(f(x)\)
当 \(f(x)\) 非凸时，不能保证全局最优，但 PGM 仍可收敛到临界点（stationary point）。关键修改包括：
- 采用回溯线搜索自适应确定步长 \(t_k\)，确保每次迭代目标函数值充分下降。
- 收敛准则通常设置为相邻迭代点的变化或梯度的范数小于预设阈值。
回溯线搜索步骤（以 PGM 为例）：
给定参数 \(\beta \in (0,1)\)，初始步长 \(t_0\)。
在每次迭代，尝试步长 \(t = t_k\)：
- 计算候选点：\(z = \text{prox}_{t g} (x^{(k)} - t \nabla f(x^{(k)}))\)。
- 检查下降条件（Armijo 型条件）：
\[ F(z) \le F(x^{(k)}) - \frac{1}{2t} \| z - x^{(k)} \|^2 \]
如果满足，接受 \(x^{(k+1)} = z\)；否则缩减步长 \(t := \beta t\) 并重试。
6. 完整算法流程（加速近似点梯度法，支持非凸）
输入：初始点 \(x^{(0)}\)，梯度 Lipschitz 常数估计 \(L_0\)，参数 \(\beta \in (0,1)\)，容差 \(\epsilon > 0\)。
- 初始化：\(y^{(1)} = x^{(0)}\)，\(t_1 = 1\)，\(k = 1\)。
- 重复直到收敛：
a. 设置步长 \(t = L_{k-1}\)。
b. 回溯线搜索：
循环执行：
计算候选点：
\[ x^{(k)} = \text{prox}_{t g} \left( y^{(k)} - t \nabla f(y^{(k)}) \right) \]
检查下降条件：
\[ F(x^{(k)}) \le F(y^{(k)}) - \frac{1}{2t} \| x^{(k)} - y^{(k)} \|^2 \]
若满足，跳出循环；否则令 $ t := \beta t $。
结束循环，记录最终步长 $ L_k = t $。
c. 检查收敛：若 \(\| x^{(k)} - x^{(k-1)} \| < \epsilon\)，则停止。
d. 更新辅助点（加速步骤）：
\[ t_{k+1} = \frac{1 + \sqrt{1 + 4 t_k^2}}{2} \]
\[ y^{(k+1)} = x^{(k)} + \frac{t_k - 1}{t_{k+1}} (x^{(k)} - x^{(k-1)}) \]
e. 令 \(k := k+1\)。
3. 输出：\(x^{(k)}\) 作为近似临界点。
7. 收敛性分析要点
- 凸情形：若 \(f\) 凸，FISTA 保证 \(F(x^{(k)}) - F^* \le O(1/k^2)\)，其中 \(F^*\) 是最优值。
- 非凸情形：算法产生的序列 \(\{x^{(k)}\}\) 的极限点满足临界点条件：\(0 \in \nabla f(x^*) + \partial g(x^*)\)，其中 \(\partial g\) 是次梯度。收敛速率通常为 \(o(1/k)\)。
8. 实际应用中的技巧
- 步长选择：若 \(f\) 的梯度 Lipschitz 常数 \(L\) 已知，固定步长 \(t = 1/L\) 即可；否则用回溯线搜索。
- 非光滑项 \(g(x)\) 的近似点算子：需根据具体形式设计高效计算方式（如软阈值、投影等）。
- 加速的权衡：FISTA 在凸问题中加速明显，但在非凸问题中可能震荡，有时需关闭加速（即取 \(y^{(k)} = x^{(k)}\)）。
总结
近似点梯度法通过分解目标函数为光滑与非光滑部分，利用梯度下降与近似点算子交替更新，有效处理一大类非光滑复合优化问题。引入加速技术（FISTA）可大幅提升凸问题下的收敛速度，而通过回溯线搜索可扩展至非凸情形。该算法在稀疏优化、机器学习正则化问题、信号处理等领域应用广泛。