次梯度法 基本概念与动机 在凸优化中，梯度下降法要求函数可微，但实际问题中许多凸函数不可微（如L1范数、最大值函数）。次梯度法扩展了梯度概念，用于解决不可微凸函数的优化问题。次梯度定义为：若函数 \( f: \mathbb{R}^n \to \mathbb{R} \) 是凸函数，则向量 \( g \in \mathbb{R}^n \) 是 \( f \) 在点 \( x \) 的次梯度，当且仅当对所有 \( y \) 满足 \[ f(y) \geq f(x) + g^T (y-x). \] 次梯度可能不唯一，所有次梯度的集合称为次微分，记作 \( \partial f(x) \)。 次梯度的性质与计算 可微函数在点 \( x \) 的次微分仅包含梯度 \( \nabla f(x) \)； 对于绝对值函数 \( f(x) = |x| \)，在 \( x=0 \) 处的次微分是区间 \( [ -1,1 ] \)； 最大值函数 \( f(x) = \max\{f_ 1(x), f_ 2(x)\} \) 在点 \( x \) 的次微分是活跃函数（达到最大值的函数）的梯度的凸包。 次梯度法迭代格式 次梯度法的更新规则为： \[ x^{(k+1)} = x^{(k)} - \alpha_ k g^{(k)}, \quad g^{(k)} \in \partial f(x^{(k)}), \] 其中 \( \alpha_ k > 0 \) 是步长。与梯度下降法不同，次梯度法的负次梯度方向不一定是下降方向，因此需动态调整步长。 步长选择策略 为保证收敛，步长需满足以下条件之一： 固定小步长 ： \( \alpha_ k = \alpha \)（收敛到次优邻域）； 递减步长 ：如 \( \alpha_ k = \frac{1}{k} \) 或 \( \alpha_ k = \frac{1}{\sqrt{k}} \)（保证收敛但速度较慢）； Polyak步长 ：若已知最优值 \( f^* \)，则 \( \alpha_ k = \frac{f(x^{(k)}) - f^* }{\|g^{(k)}\|^2} \)。 收敛性分析 次梯度法收敛速度为 \( O(1/\sqrt{k}) \)（对于非光滑函数），慢于梯度下降法的 \( O(1/k) \)。若函数是强凸且光滑的，可恢复线性收敛，但一般需结合其他技术（如近似梯度）。 应用场景与扩展 L1正则化问题 ：如LASSO回归； 支持向量机 ：处理不可微的合页损失函数； 分布式优化 ：结合次梯度的分布式迭代； 近端梯度法 ：对非光滑部分使用次梯度，光滑部分使用梯度，提升效率。