近似点梯度法(Proximal Gradient Method)进阶题
题目描述
考虑如下复合优化问题：
\[\min_{x \in \mathbb{R}^n} f(x) + g(x) \]
其中 \(f(x)\) 是可微函数（可能非凸），梯度 \(\nabla f\) 满足 Lipschitz 连续条件，常数 \(L > 0\)；\(g(x)\) 是不可微函数（例如 L1 范数、指示函数等），但需是闭凸函数。
具体实例：
\[f(x) = \frac{1}{2} \|Ax - b\|^2_2, \quad g(x) = \lambda \|x\|_1 \]
其中 \(A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, \lambda > 0\)。要求推导近似点梯度法的迭代格式，分析其收敛性，并解释近端算子的作用。
解题过程
-
问题分解与挑战
目标函数由可微部分 \(f(x)\) 和不可微部分 \(g(x)\) 组成。若直接使用梯度下降法，由于 \(g(x)\) 不可微，无法计算整体梯度。近似点梯度法的核心思想是：对可微部分 \(f\) 进行梯度下降，对不可微部分 \(g\) 通过近端算子处理。 -
近端算子定义
函数 \(g\) 的近端算子定义为：
\[ \text{prox}_{\alpha g}(v) = \arg\min_{x} \left\{ g(x) + \frac{1}{2\alpha} \|x - v\|^2 \right\} \]
其意义是：在 \(v\) 附近寻找一个点 \(x\)，使得 \(g(x)\) 较小，同时 \(x\) 不过分远离 \(v\)。参数 \(\alpha\) 控制权衡强度。
- 迭代格式推导
- 对可微部分 \(f\)，在当前迭代点 \(x_k\) 处构造二次近似：
\[ f(x) \approx f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2\alpha} \|x - x_k\|^2 \]
其中 $ \alpha $ 为步长，需满足 $ \alpha \leq 1/L $ 以确保收敛。
- 整体目标函数的近似为：
\[ Q(x, x_k) = f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2\alpha} \|x - x_k\|^2 + g(x) \]
- 通过最小化 \(Q(x, x_k)\) 得到下一迭代点：
\[ x_{k+1} = \arg\min_{x} \left\{ g(x) + \frac{1}{2\alpha} \|x - (x_k - \alpha \nabla f(x_k))\|^2 \right\} \]
对比近端算子定义，可得迭代格式：
\[ x_{k+1} = \text{prox}_{\alpha g} (x_k - \alpha \nabla f(x_k)) \]
该步骤称为“梯度步”与“近端步”的结合。
- 实例求解（L1 正则化问题）
对于 \(g(x) = \lambda \|x\|_1\)，其近端算子为软阈值函数：
\[ [\text{prox}_{\alpha g}(v)]_i = \text{sign}(v_i) \cdot \max\{|v_i| - \lambda \alpha, 0\} \]
迭代过程：
- 梯度步：计算 \(\nabla f(x_k) = A^T(Ax_k - b)\)，得到 \(v_k = x_k - \alpha A^T(Ax_k - b)\)。
- 近端步：对 \(v_k\) 的每个分量应用软阈值操作，得到 \(x_{k+1}\)。
-
收敛性分析
- 若 \(f\) 为凸函数且梯度 Lipschitz 连续（常数为 \(L\)），当步长 \(\alpha \in (0, 1/L]\) 时，算法以 \(O(1/k)\) 的速率收敛到全局最优解。
- 若 \(f\) 非凸但满足 Kurdyka-Łojasiewicz 性质，算法仍可收敛到临界点。
- 收敛性依赖近端算子的非扩张性（Nonexpansiveness），确保迭代稳定性。
-
近端算子的作用
- 可处理不可微函数：将不可微优化转化为一系列可求解的近端子问题。
- 保持稀疏性：在 L1 正则化中，软阈值操作直接产生稀疏解。
- 数值稳定性：近端算子通过二次项保证子问题强凸，避免数值震荡。
总结
近似点梯度法通过分解目标函数，结合梯度下降与近端算子，高效处理复合优化问题。其核心优势在于将复杂问题转化为可计算的迭代步骤，同时保持理论上的收敛保证。