次梯度

因为我在实际中需要用到次梯度的一些性质，这里对次梯度的概念做一个整理，以下是对书<<最优化:建模、算法与理论>>(刘浩洋、户将、李勇锋、文再文编著)中关于次梯度的一些记录笔记。

2.7.1 次梯度的定义

定义 2.21 (次梯度)

g为函数f在点x处的一个次梯度

$$f(y) \geq f(x) + g^T(y-x), \forall y\in \textbf{dom} f.$$

定理 2.16 (次梯度存在性)

设f为凸函数，dom $f$ 为其定义域.如果 x $\in$ intdom $f$，则 $\partial f(x)$ 是非空的，其中intdom $f$的含义是集合 dom $f$的所有内点.

例 2.15 ($\mathbb{l}_2$ 范数的次微分)

2.7.2 次梯度的性质

定理 2.17 设 $f$ 是凸函数，则 $\partial f(x)$ 有如下性质:

(1) 对任何 x ∈ dom f ，∂ f (x) 是一个闭凸集(可能为空集);
(2) 如果 x ∈ intdom f，则 ∂f(x) 非空有界集.

6.3 次梯度算法

$x^{k+1} = x^k - \alpha_k g^k, g^k\in\partial f(x^k)$, $\alpha_k > 0$为步长.

• 固定步长 $\alpha_k = \alpha$.
• 固定$\lVert x^{k+1} - x^k \rVert$, 即$\alpha_k \lVert g^k \rVert$为常数.
• 消失步长$\alpha_k \rightarrow 0$ 且 $\sum_{k=0}^{\infty} \alpha_k = +\infty$
• 选取$\alpha_k$使其满足某种线搜索准则.
  相比可微凸函数的梯度的一阶条件，次梯度显然不能用这个一阶条件作为算法的停机条件。

6.3.2 收敛性分析

假设6.1 对无约束优化问题,目标函数$f(x)$满足:

1. f为凸函数
2. f至少存在一个有限的极小值点 $x^*$, 且$f(x^*) > -\infty$;
3. f为利普希茨连续的,即$|f(x) - f(y)| \leq G\lVert x - y \rVert, \forall x,y \in \mathcal{R}^n$, $G$为利普希茨常数.

引理6.2 $f$为利普希茨连续的,当且仅当$f$的次梯度有界.

不同步长下的收敛性

定理 6.5 (次梯度算法的收敛性)