1 次梯度的基本定义
次梯度是对凸函数“导数/梯度仍能发挥作用”的一种推广。对一个凸函数 \(f:\mathbb{R}^n\to \mathbb{R}\)（允许取值为无穷大以表达约束），当 \(x\) 处不可导时，次梯度用一组向量来刻画：它们能给出一个不等式形式的“局部线性下界”，从而仍能定义可用于优化的下降方向或下降性判断。
1.1 次梯度与切平面不等式
1.1.1 凸函数的支持超平面视角
对凸函数 \(f\)，在任意点 \(x\) 都存在（在适当条件下）一种“支持超平面”：某个仿射函数 \[ \ell(y)=f(x)+g^\top (y-x) \] 满足对所有 \(y\)： \[ f(y)\ge \ell(y). \] 这里的 \(g\) 就是 \(f\) 在点 \(x\) 的一个次梯度。该不等式意味着：以 \(x\) 为“触点”的线性函数不会穿到图像下方，只能在局部从下方“托住”凸图形。
1.1.2 从导数到次梯度的类比
若 \(f\) 在 \(x\) 可导，则梯度 \( \nabla f(x)\) 满足一阶凸性不等式： \[ f(y)\ge f(x)+\nabla f(x)^\top (y-x). \] 这时次梯度集合退化为单元素集合，即 \[ \partial f(x)=\{\nabla f(x)\}. \] 因此次梯度可以视作“不可导时一阶信息的替代品”：不再用唯一的斜率，而是用一族能同时保持下界性质的斜率。
1.2 次梯度集合（次微分）
次梯度集合也称次微分，记作 \(\partial f(x)\)。它强调“同一函数、同一处点、可能对应多条支持超平面”，从而自然对应非光滑结构。
1.2.1 次微分映射 \(\partial f(x)\)
凸分析中对任意点 \(x\)，次微分定义为满足下式的不等式族的全部向量： \[ \partial f(x)=\left\{g\in\mathbb{R}^n\mid f(y)\ge f(x)+g^\top (y-x),\ \forall y\right\}. \] 若该集合为空，通常表示 \(x\) 不在合适的“有效域”或函数在该点不存在对应的支持超平面（更一般情形下与闭性、适当性条件有关）。
1.2.2 多值性与可导情形的退化
当 \(f\) 在某点形成“折角”或“拐点”，支持超平面不再唯一。此时 \(\partial f(x)\) 可能是一个凸集，里面包含多种斜率向量，反映了“局部变化率并不唯一”的几何事实。相反，若函数在该点光滑，次微分便收缩为单一梯度。
1.3 凸与非凸情形的适用边界
1.3.1 为什么主要针对凸函数
次梯度的核心不等式 \(f(y)\ge f(x)+g^\top(y-x)\) 依赖于凸性。凸性保证“支持超平面从下方托住图像”，使得由不等式导出的算法更新具有理论可控性（例如用它来证明目标值下降、或给出最优性条件的充分性/必要性）。
1.3.2 非光滑点的行为直觉
即便不讨论严格非凸性，非光滑点可用直觉理解为：函数的局部线性逼近可能存在多种“合法斜率”。次梯度集合恰好收集所有能给出有效下界的斜率，因此在折角附近它仍能提供一阶方向信息；不同次梯度对应不同“触碰方向”，共同约束了可能的下降行为。
2 相关性质与计算规则
次梯度不仅是定义层面的工具，也具备明确的几何性质与可计算的规则。它们使得在工程优化中可以把抽象概念转化为实际可实现的算法步骤。
2.1 次梯度的几何性质
2.1.1 有界性、闭性与凸锥结构
对许多凸函数，\(\partial f(x)\) 在几何上是良态集合：它通常是闭的凸集；在局部有效域内还常伴随有界性或与紧性条件相联系。更进一步，在一些结构化情形下，次微分与法向锥（normal cone）或可形成凸锥的对象对应，从而允许用锥分析语言描述其性质。
2.1.2 方向导数与次梯度关系
次梯度与方向导数之间存在紧密联系。对给定方向 \(d\)，方向导数（在适当条件下）可由次微分给出上确界或下确界表达。直观上，\(\partial f(x)\) 为所有“可能的线性下界斜率”集合，因此对方向 \(d\) 的增长/下降速率由其中某些内积值决定，这种关系常用于证明收敛与估计误差。
2.2 典型可计算情形
2.2.1 绝对值函数与分段线性函数
| 以一维函数 \(f(t)= | t | \) 为例： |
|---|
- 当 \(t>0\)，函数可导，\(\partial f(t)=\{1\}\)；
- 当 \(t<0\)，\(\partial f(t)=\{-1\}\)；
- 当 \(t=0\)，折点处支持超平面不唯一，次微分为区间：
\[ \partial f(0)=[-1,1]. \] 这体现了多值性：折角处的“可能斜率”形成一个连续范围。分段线性函数同理：在每段内部次梯度固定为对应斜率，而在分界处由左右斜率张成区间或更一般的凸组合集合。
2.2.2 范数、核范数与 ℓp 范数
| 对范数 \( \|x\|\) 的次梯度计算通常依赖于“与单位球的切触”。以 |
|---|
\[
| f(x)=\|x\|_2 |
|---|
\] 为例，当 \(x\neq 0\) 时： \[
| \partial f(x)=\left\{\frac{x}{\|x\|_2}\right\}. |
|---|
\] 在 \(x=0\) 时次微分为单位球： \[
| \partial f(0)=\{g:\|g\|_2\le 1\}. |
|---|
\] 对于一般的 \(\ell_p\) 范数或核范数（例如矩阵情形的奇异值和），次微分通常可由“归一化的对应向量/算子”以及在零奇异值或多重奇异值处的凸组合来描述。实践中，这类公式常被用来实现非光滑问题的迭代求解。
2.3 常见运算的次梯度法则
次微分并不像普通导数那样具备单一链式法则，但在凸情形下可用一组兼容的规则完成计算。
2.3.1 仿射变换与复合结构
若 \(f\) 为凸，考虑仿射变换 \(y=Ax+b\)，则 \[ g\in \partial f(y)\quad \Rightarrow\quad A^\top g\in \partial (f(Ax+b)). \] 该规则保证线性映射不会破坏次梯度的支持超平面含义，只需用伴随矩阵把“斜率”拉回原空间。
复合结构在满足凸性与可计算性条件时可进一步处理，例如对外层为非减凸函数的复合、或对内层为仿射变换的情形，次微分可用子链规则（通常涉及乘以某个标量子梯度集合）表达。
2.3.2 和、最大值（max）与指示函数
- 和：若 \(f,h\) 为凸且满足常见的资格条件（如相对内部点存在），则次微分满足“加法”关系：
\[ \partial (f+h)(x)\approx \partial f(x)+\partial h(x), \] 其精确形式是集合和，常通过包含关系或资格条件下的等式体现。
- 最大值：若
\[ F(x)=\max_i f_i(x), \] 则在给定 \(x\) 处，激活的索引集合 \(I(x)=\{i: f_i(x)=F(x)\}\) 会决定次微分来源。直观上，只有“达到最大值”的分量对应的支持超平面才可能产生有效次梯度。
- 指示函数：对可行域 \(C\)，定义指示函数
\[ \delta_C(x)= \begin{cases} 0,&x\in C\\ +\infty,&x\notin C \end{cases} \] 则 \(\partial \delta_C(x)\) 与法向锥直接相关。将约束并入目标函数后，次梯度法能够自然地把“可行性”转化为与法向锥相关的项。
3 与凸分析工具的联系
次梯度并非孤立概念，它与凸集几何、对偶性与共轭变换等核心工具形成闭环：从几何得到不等式，从不等式得到对偶，再回到优化算法的可证明性。
3.1 法向锥与法线向量解释
3.1.1 凸集边界的法向量
对凸集 \(C\)，边界点的“外法线”并不总是唯一，它们组成法向锥。将指示函数 \(\delta_C\) 纳入框架后，次微分 \(\partial \delta_C(x)\) 等价于法向锥的某种描述：任何次梯度对应的支持超平面都在该点“把函数或约束从外侧撑住”。因此，次梯度集合常被理解为：在非光滑边界上，哪些方向可以作为有效的法线力量。
3.1.2 KKT 思想的非光滑版雏形
在约束优化中，经典的KKT条件可看作“可行性 + 拉格朗日乘子平衡 + 一阶必要性”。当目标或约束存在非光滑性，梯度会被次梯度替代，法向锥替代梯度的直观平衡。其结构形式仍体现“支持/法向”与“互补”这类几何关系，只是精确表述会使用次微分与对偶锥。
3.2 凸共轭与次梯度对应
3.2.1 次梯度—共轭对偶的基本关系
凸共轭（Legendre–Fenchel变换）把函数与其对偶函数联系起来。对凸闭函数 \(f\)，共轭 \(f^*\) 定义为 \[ f^*(s)=\sup_x \{ s^\top x - f(x)\}. \] 次梯度与共轭满足一个关键对应：若 \(g\in \partial f(x)\)，则 \[ x\in \partial f^*(g), \] 并且在这种对应关系下通常伴随“等号成立”的对偶间断条件，即支持超平面正好实现最大化。
3.2.2 单位化例子：如何从对偶回到原问题
在很多算法与理论中，会利用“从对偶取回”的机制：先在对偶空间求解近似或最优性，再通过次梯度对应回到原空间。直观上，共轭把“斜率信息”转成“变量信息”，次梯度则是这两种信息的桥梁。对于范数类问题，对偶通常具备更简单的结构（例如核范数与算子范数之间的关系），从而让计算更高效。
3.3 支撑函数与次梯度
3.3.1 支撑函数的次梯度意义
给定凸集 \(C\)，其支撑函数定义为 \[ h_C(u)=\sup_{x\in C} u^\top x. \] 它在给定方向 \(u\) 上取到的最大值与“支撑点”有关。支撑函数的次梯度与该方向上达到支撑的点集相连：次梯度告诉我们，在方向 \(u\) 下，哪些原空间点可以实现最大投影。因此，支撑函数为次梯度提供了一个“从几何到导数式不等式”的统一视角。
3.3.2 凸锥与几何对偶
支撑函数、法向锥与凸锥对偶之间存在标准联系：一个锥的对偶锥刻画与之相容的非负内积方向。次梯度与这些几何对象的互译，使得很多收敛证明能够用“锥分离/投影”类工具完成，而不是依赖显式光滑性。
4 次梯度法与优化应用
次梯度法用于处理凸但可能不可导的问题。它通过在每一步选择一个次梯度（或其近似）构造更新，从而在缺少梯度信息时仍能推进搜索。
4.1 次梯度法的基本步骤
4.1.1 更新规则与步长选择
最基本的无约束次梯度法形式为： \[ x_{k+1}=x_k-\alpha_k g_k, \] 其中 \(g_k\in \partial f(x_k)\) 是在当前点取到的次梯度，\(\alpha_k>0\) 为步长。步长选择决定了理论收敛速率与实际表现：步长若衰减得合适，常能保证子序列或整体产生收敛；若步长过大可能振荡，过小则收敛缓慢。
在实践中，常见做法包括固定步长（在某些误差容忍或目标范围下）或递减步长（与目标的界、子梯度有界性相关）。
4.1.2 投影算子与可行域约束
若优化存在约束 \(x\in C\)，则通常使用投影来维持可行性： \[ x_{k+1}= \Pi_C(x_k-\alpha_k g_k), \] 其中 \(\Pi_C\) 为到集合 \(C\) 的最近点投影。该操作把“沿次梯度方向的更新”限制在可行域内，使约束处理变得几何化。对于凸集，投影算子通常具有良好的非扩张性质，从而便于收敛分析。
4.2 收敛性与复杂度概览
4.2.1 亚梯度/次梯度的收敛条件
对于凸目标，次梯度法常能保证以某种意义趋向最优值（例如最优函数值或最优性残差趋近）。典型的理论条件包括：
- 次梯度有界性或满足可控增长；
- 步长序列的和与平方和满足特定关系（例如衰减以平衡“进展”和“噪声/不确定性”）；
- 若考虑加速或更强收敛形式，则需要进一步结构假设（如平滑度、强凸性或误差界等）。
由于次梯度法缺少光滑性带来的精细信息，其收敛速度通常以次线性为主；不过在需要处理非光滑结构时，这种方法仍非常有用。
4.2.2 误差界与实际停止准则
实际停止常用“函数值差距”“次梯度范数”“可行性残差”等指标。理论上，若存在误差界或结构化条件，可以把这些指标与最优性距离联系起来，从而得到更可解释的终止准则。即便没有强结构，基于上界的停止规则仍能提供工程可行性。
4.3 变体与改进
4.3.1 加速/平均化策略的思路
针对基本次梯度法收敛偏慢的问题，常见改进包括：
- 平均化：对迭代点或次梯度加权平均，提升函数值意义下的稳定性；
- 加速思想：在保证凸性框架下引入类似动量或更精细的权重更新，使收敛界在某些设置下更理想。此类方法通常仍需要额外的假设或参数调节。
这些策略通常不改变“用次梯度而非梯度”的核心，只是改善误差传播方式。
4.3.2 组合优化与分块次梯度（概念层面）
在组合优化中，目标往往由多个凸项构成，例如范数正则化与损失函数的和。分块次梯度或坐标式更新的基本思想是：并非每次都更新全部变量，而是选择部分块或子问题更新，以降低每步计算成本或利用结构稀疏性。其理论分析通常依赖分块的 Lipschitz/界估计或更一般的误差界框架，并与投影算子、近端映射等工具结合使用。