知识点：无约束不可微问题最优性条件

知识点概述

对于不可微的凸函数，梯度的概念被次梯度取代。最优性条件也从“梯度为零”推广为“零是次微分的一个元素”。

背景: 许多重要的凸函数（如 $ℓ_{1}$ 范数 $∥ x ∥_{1}$ 、Hinge损失）在某些点是不可微的，因此无法使用基于梯度的最优性条件。
一阶充要条件:
- 内容: 对于一个（不一定可微的）凸函数 $f$ ，点 $x^{*}$ 是其全局最优解的充要条件是 $0 \partial f (x^{*})$ 。
- 直观: 在最优解 $x^{*}$ 处，至少存在一个次梯度为零向量。这意味着我们可以从 $x^{*}$ 画出一条“水平”的支撑超平面，整个函数图像都在该超平面的上方。
与可微情况的联系: 如果函数 $f$ 在 $x^{*}$ 点可微，那么其次微分 $\partial f (x^{*})$ 只包含一个元素，即梯度 $\nabla f (x^{*})$ 。此时， $0 {\nabla f (x^{*})}$ 就退化为 $\nabla f (x^{*}) = 0$ ，与可微情况的一阶必要条件一致。
复合优化问题: 对于复合优化问题 $min F (x) = f (x) + g (x)$ （ $f$ 光滑， $g$ 非光滑凸），最优性条件为 $0\nabla f (x^{*}) + \partial g (x^{*})$ ，或者等价地， $- \nabla f (x^{*}) \partial g (x^{*})$ 。

算法终止条件: 次梯度下降等算法的终止条件可以是找到一个点的次梯度范数足够小。
邻近梯度法: 求解复合优化问题的邻近梯度算法，其不动点方程 $x^{*} = prox_{γ g} (x^{*} - γ \nabla f (x^{*}))$ 正是源于最优性条件 $- \nabla f (x^{*}) \partial g (x^{*})$ 。