知识点：次梯度算法

知识点概述

次梯度算法是梯度下降法向非光滑（不可微）凸优化问题的直接推广。它在每一步迭代中使用目标函数在当前点的一个次梯度（而不是梯度）来更新变量。

算法:
1. 选择初始点 $x_{0}$ 。
2. 迭代更新: $x_{k + 1} = x_{k} - α_{k} g_{k}$ ，其中 $g_{k} \in \partial f (x_{k})$ 是 $f$ 在 $x_{k}$ 处的一个任意次梯度。
与梯度下降的区别:
- 方向: 次梯度方向 $- g_{k}$ 不再保证是函数值的下降方向。因此，不能使用线搜索来寻找步长。
- 目标函数值: 迭代过程中目标函数值不一定是单调下降的。算法的收敛性是通过记录并返回历史迭代中函数值最小的那个点来保证的。
步长 $α_{k}$ 的选择:
- 由于不能线搜索，步长的选择至关重要，且必须预先设定。
- 常用的步长规则要求 $α_{k}$ 满足： $α_{k} > 0, lim_{k \to \infty} α_{k} = 0, \sum_{k = 0}^{\infty} α_{k} = \infty$ 。例如， $α_{k} = a / (b + k)$ 。
收敛性:
- 次梯度算法的收敛速度通常很慢，为次线性收敛。