近似点梯度法(Proximal Gradient Method)基础题
题目描述
考虑一个非线性规划问题，目标函数由两部分组成：一个光滑可微的凸函数 \(f(x)\) 和一个非光滑但简单的凸函数 \(g(x)\)，形式如下：
\[\min_x F(x) = f(x) + g(x) \]
其中，\(f(x) = \frac{1}{2} \|Ax - b\|^2\)（最小二乘项），\(g(x) = \lambda \|x\|_1\)（L1 正则化项），\(A \in \mathbb{R}^{m \times n}\)，\(b \in \mathbb{R}^m\)，\(\lambda > 0\) 是正则化参数。约束条件为 \(x \in \mathbb{R}^n\)。要求使用近似点梯度法求解该问题。
解题过程
-
问题分析
- 目标函数 \(F(x)\) 包含光滑部分 \(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 $ 是步长。该算子表示在 $ g(x) $ 和接近 $ v $ 之间权衡的最小点。
- 对于 \(g(x) = \lambda \|x\|_1\)，其近似点算子有解析解（软阈值函数）：
\[ \text{prox}_{\alpha g}(v)_i = \text{sign}(v_i) \cdot \max\{|v_i| - \lambda \alpha, 0\} \]
即对向量 $ v $ 的每个分量进行软阈值收缩。
- 算法迭代格式
- 近似点梯度法的迭代步骤为：
\[ x^{(k+1)} = \text{prox}_{\alpha_k g} \left( x^{(k)} - \alpha_k \nabla f(x^{(k)}) \right) \]
其中 $ \alpha_k $ 是步长，可通过固定步长、线搜索或自适应方法确定。
- 计算 \(f(x)\) 的梯度：
\[ \nabla f(x) = A^T(Ax - b) \]
- 具体计算步骤
- 步骤 1：初始化 \(x^{(0)}\)，设定步长 \(\alpha\)（需满足 \(\alpha \leq 1/L\)，\(L\) 是 \(\nabla f\) 的 Lipschitz 常数，这里 \(L = \|A^T A\|_2\)）。
- 步骤 2：在第 \(k\) 次迭代中：
- 计算梯度下降步：
\[ v^{(k)} = x^{(k)} - \alpha A^T(A x^{(k)} - b) \]
- 应用近似点算子（软阈值）：
\[ x^{(k+1)}_i = \text{sign}(v^{(k)}_i) \cdot \max\{|v^{(k)}_i| - \lambda \alpha, 0\}, \quad i=1,\dots,n \]
- 步骤 3：检查收敛条件（如 \(\|x^{(k+1)} - x^{(k)}\| < \epsilon\)），若未满足则返回步骤 2。
- 收敛性说明
- 当 \(f(x)\) 是凸函数且梯度 Lipschitz 连续时，算法以 \(O(1/k)\) 的速率收敛到全局最优解。若 \(f(x)\) 强凸，可达线性收敛速率。
总结
近似点梯度法通过分解目标函数，分别处理光滑和非光滑部分，有效解决了 L1 正则化等问题。其优势在于非光滑项有简单近似点算子时，迭代计算高效且易于实现。