近似点梯度法(Proximal Gradient Method)进阶题
题目描述
考虑一个非光滑优化问题：
\[\min_x f(x) + g(x) \]
其中 \(f(x)\) 是一个连续可微函数（例如 \(f(x) = \frac{1}{2} \|Ax - b\|^2\)），而 \(g(x)\) 是一个非光滑但简单的函数（例如 \(g(x) = \lambda \|x\|_1\)，即L1正则化项）。目标是通过近似点梯度法求解该问题。
解题过程
-
问题分析
- 目标函数由可微部分 \(f(x)\) 和非光滑部分 \(g(x)\) 组成。直接使用梯度下降法不可行，因为 \(g(x)\) 不可微。
- 近似点梯度法的核心思想：对可微部分 \(f(x)\) 进行梯度下降，对非光滑部分 \(g(x)\) 使用近似点算子（Proximal Operator）处理。
-
近似点算子定义
函数 \(g(x)\) 的近似点算子定义为：
\[ \text{prox}_{\alpha g}(v) = \arg\min_x \left\{ g(x) + \frac{1}{2\alpha} \|x - v\|^2 \right\} \]
其中 \(\alpha > 0\) 是步长参数。该算子通过二次正则化将非光滑问题转化为一个可求解的子问题。
- 算法步骤
近似点梯度法的迭代格式为：
\[ x^{(k+1)} = \text{prox}_{\alpha_k g} \left( x^{(k)} - \alpha_k \nabla f(x^{(k)}) \right) \]
其中 \(\alpha_k\) 是步长，可通过固定步长或线搜索确定。
- 具体实例：L1正则化最小二乘问题
设 \(f(x) = \frac{1}{2} \|Ax - b\|^2\), \(g(x) = \lambda \|x\|_1\)，则：- 梯度计算：\(\nabla f(x) = A^T(Ax - b)\)。
- 近似点算子：对于 \(g(x) = \lambda \|x\|_1\)，其近似点算子是软阈值函数：
\[ [\text{prox}_{\alpha g}(v)]_i = \text{sign}(v_i) \max\{ |v_i| - \lambda \alpha, 0 \} \]
其中 $ [\cdot]_i $ 表示向量的第 $ i $ 个分量。
-
迭代过程详解
- 初始化：选择初始点 \(x^{(0)}\)、步长 \(\alpha_0\)（需满足 \(\alpha_0 \leq 1/L\)，\(L\) 是 \(\nabla f\) 的Lipschitz常数）。
- 迭代更新：
- 计算梯度步：\(y^{(k)} = x^{(k)} - \alpha_k \nabla f(x^{(k)})\)。
- 应用近似点算子：\(x^{(k+1)} = \text{prox}_{\alpha_k g}(y^{(k)})\)。
- 收敛判断：当 \(\|x^{(k+1)} - x^{(k)}\| < \epsilon\) 时停止。
-
加速技巧
使用Nesterov加速策略（FISTA算法）提升收敛速度：- 初始化 \(x^{(0)} = z^{(0)}\), \(t_0 = 1\)。
- 迭代：
\[ \begin{aligned} x^{(k)} &= \text{prox}_{\alpha g} \left( z^{(k)} - \alpha \nabla f(z^{(k)}) \right) \\ t_{k+1} &= \frac{1 + \sqrt{1 + 4t_k^2}}{2} \\ z^{(k+1)} &= x^{(k)} + \frac{t_k - 1}{t_{k+1}} (x^{(k)} - x^{(k-1)}) \end{aligned} \]
- 关键点说明
- 近似点梯度法要求 \(f(x)\) 的梯度是Lipschitz连续的，且 \(g(x)\) 的近似点算子需易于计算（如L1范数、L2范数）。
- 对于复杂函数 \(g(x)\)，若其近似点算子无闭式解，需内嵌优化子例程，可能影响效率。
总结
近似点梯度法通过分解目标函数，结合梯度下降与近似点算子，有效处理非光滑优化问题。其核心在于利用函数结构设计高效迭代格式，并通过加速技术进一步提升性能。