知识点：次梯度

知识点概述

次梯度是梯度概念在不可微凸函数上的推广。一个凸函数在某点可能没有唯一的梯度，但它一定存在至少一个次梯度，所有次梯度的集合构成了次微分。

定义2.24 (次梯度) 对于凸函数 $f : R^{n} \to R$ ，向量 $g \in R^{n}$ 称为 $f$ 在点 $x \in dom f$ 处的次梯度，如果

f (z) \geqslant f (x) + g ^ {\mathrm {T}} (z - x), \quad \forall z \in \mathbf {d o m} f.

$函数 $f$ 在点 $x$ 处的所有次梯度的集合称为 $f$ 在 $x$ 处的次微分，记作 $\partial f(x)$ 。$

定义: 向量 $g$ 是 $f$ 在 $x$ 点的次梯度，如果由点 $(x, f (x))$ 和梯度 $g$ 定义的仿射函数是 $f$ 的一个全局下支撑。
次微分: 在点 $x$ 的所有次梯度的集合 $\partial f (x)$ 称为次微分。次微分是一个非空的闭凸集。
与梯度的关系:
- 如果函数 $f$ 在点 $x$ 处可微，那么其次微分集合中只包含一个元素，就是该点的梯度 $\nabla f (x)$ 。
- 如果函数在某点不可微（例如绝对值函数 $f (x) = ∣ x ∣$ 在 $x = 0$ 处），其次微分可能包含多个向量（例如 $∣ x ∣$ 在 $x = 0$ 的次微分是区间 $[- 1, 1]$ ）。

最优性条件: 对于无约束凸优化问题， $x^{*}$ 是最优解的充要条件是 $0 \in \partial f (x^{*})$ 。这是梯度为零条件向非光滑函数的推广。
次梯度算法: 一种简单的非光滑凸优化算法，它在每一步迭代时使用一个任意的次梯度来代替梯度进行更新。