1 基本概念
子梯度法是一类面向不可微凸优化问题的迭代方法。它的基本思想是：当目标函数在某一点没有传统意义上的梯度时，仍然可以选取一个“足够像下降方向”的向量，推动迭代点向更优区域移动。由于这类方法不要求函数处处光滑，因此在处理绝对值、最大值、范数正则项等问题时尤其常见。
1.1 不可微优化问题
不可微优化问题指的是目标函数在部分或全部定义域内不具备导数，但依然希望找到最小值或近似最优解的优化任务。此类问题在实际建模中十分常见，例如含有绝对值项、分段函数、最大算子或稀疏正则项的模型。尽管函数没有平滑导数，若其满足凸性，仍可借助凸分析中的工具进行系统处理。
1.2 子梯度与次微分
在不可微凸函数的研究中，子梯度和次微分是核心概念。它们在形式上类似于梯度及其集合化表达，但适用于更广泛的非光滑场景。通过这些概念，可以描述函数在某一点附近的局部线性下界特征，从而为迭代更新提供方向信息。
1.2.1 子梯度的定义
对于凸函数 \(f(x)\)，若向量 \(g\) 满足 \[ f(y)\ge f(x)+g^T(y-x) \] 对所有 \(y\) 都成立，则称 \(g\) 是 \(f\) 在点 \(x\) 处的一个子梯度。直观上，子梯度给出了一条支撑函数图像的线性下界。若函数在该点可微，则其唯一子梯度就是 обыч的梯度。
1.2.2 次微分集合
某点处所有子梯度构成的集合称为次微分，记作 \(\partial f(x)\)。当函数在该点可微时，次微分集合退化为单点集合；当函数不可微时，次微分可能包含多个向量。次微分集合为算法提供了可选的更新方向，使得优化过程能够在非光滑区域继续推进。
1.3 子梯度法的核心思想
子梯度法与梯度下降法的更新形式相近，但将梯度替换为某个子梯度。典型做法是沿着负子梯度方向迭代，并结合步长控制逐步逼近最优解。由于子梯度未必总是严格的下降方向，算法通常依赖多次迭代和适当步长设计来累积优化效果。
1.4 与梯度下降法的关系
子梯度法可以看作梯度下降法在非光滑情形下的推广。两者都属于一阶方法，核心都在于利用局部信息构造更新方向。区别在于，梯度下降法要求目标函数可微，因而通常具有更稳定、更快的收敛表现；子梯度法适用范围更广，但收敛速度往往较慢，对步长选择也更敏感。
2 数学基础
子梯度法建立在凸分析和非光滑分析的基础之上。要理解其正确性和收敛性质，需要先掌握凸函数的结构特征、不可微点附近的广义导数概念，以及最优解所满足的一阶条件。
2.1 凸函数的性质
凸函数具有良好的几何结构，其图像不会“向上凹陷”，这使得局部信息能够较可靠地反映整体趋势。对于凸优化而言，这类性质极大简化了最优性判断与算法分析。
2.1.1 凸性与局部最优
在凸优化中，局部最优解就是全局最优解。这一性质非常关键，因为它意味着只要算法能够在局部持续改进，最终逼近的目标就是全局最优值，而不必担心陷入非全局极小点。子梯度法正是借助这一特征，在非光滑但凸的场景中发挥作用。
2.1.2 支撑超平面
凸函数在任一点处都存在支撑超平面或支撑线性下界。该几何图像与子梯度的定义密切相关：子梯度可以理解为支撑超平面的法向量。正是这种线性下界结构，使得不可微函数仍然能够被局部线性化处理。
2.2 非光滑分析
非光滑分析研究函数在不可微点附近的性质，并尝试用广义概念替代经典导数。对于子梯度法而言，这一理论提供了严格的数学基础。
2.2.1 可微性与不可微点
函数在大多数点可微，但在某些尖点、折点或分段拼接处可能失去导数。例如绝对值函数在零点处不可微，最大函数在多个分支相等时也可能不可微。子梯度法正是在这些点上使用次微分信息继续推进优化。
2.2.2 子导数与广义导数
子导数和广义导数是描述非光滑函数局部变化的工具。它们不一定是单值对象，而可能表现为集合、区间或方向性信息。不同理论体系中定义略有差异，但共同目标都是为不可微优化提供可操作的微分替代物。
2.3 最优性条件
最优性条件用于判断一个点是否可能是最优解。在凸优化中，一阶条件尤其简洁，并且与次微分直接相关。
2.3.1 一阶最优条件
对于凸函数 \(f\)，点 \(x^\*\) 是最优解的充要条件之一是 \[ 0 \in \partial f(x^\*) \] 这表示零向量属于该点的次微分集合。换言之，如果某点存在“平衡”的子梯度结构，使得没有任何方向能够显著降低函数值，那么该点就是最优点。
2.3.2 零点判别
零点判别是最优性条件的直接表达：当次微分包含零向量时，目标函数在该点附近无法再通过一阶信息继续下降。该判别在算法中常用于判断是否接近最优解，也为终止准则设计提供了理论参考。
3 算法形式
子梯度法的实现通常较为直接，但不同步长策略、投影机制和变体设计会明显影响其数值表现。实际应用中，算法结构往往围绕“计算子梯度—更新迭代点—必要时进行投影”这一主线展开。
3.1 基本迭代公式
基本子梯度法的迭代形式通常写为 \[ x_{k+1}=x_k-\alpha_k g_k \] 其中 \(g_k\) 是在当前点选取的一个子梯度，\(\alpha_k\) 是步长。若问题带有约束，还可能在更新后对新点进行投影处理。该形式简洁，适合大规模和结构化问题。
3.2 步长策略
步长决定了每一步更新的幅度，是子梯度法成败的关键因素之一。步长过大可能导致震荡，过小则会使收敛过慢，因此常需结合问题特征进行设计。
3.2.1 固定步长
固定步长实现简单，便于编码和分析，但通常只适用于对精度要求不高或迭代轮数有限的场景。若步长长期不变，算法可能在最优点附近来回摆动，难以进一步逼近精确解。
3.2.2 递减步长
递减步长是最常见的选择之一。随着迭代进行，步长逐步减小，可以在前期快速探索、后期细致收敛之间取得平衡。常见形式包括按迭代次数倒数缩放的规则。该策略对理论收敛分析也较友好。
3.2.3 自适应步长
自适应步长会根据当前迭代状态动态调整更新幅度，例如依据函数值变化、历史梯度信息或局部几何特征修正步长。这类方法通常更灵活，但实现复杂度也更高，需要额外机制防止步长波动过大。
3.3 投影子梯度法
当问题带有约束条件时，单纯的子梯度更新可能会把迭代点带出可行域。投影子梯度法通过投影操作将点拉回约束集合，从而保持可行性。
3.3.1 约束集上的投影
投影是指将一个点映射到距离最近的可行点。若约束集为凸集，则投影通常唯一，并且具有良好性质。投影步骤使算法能够处理盒约束、球约束、简单单纯形约束等多种形式。
3.3.2 可行域保持
在每次更新后进行投影，可以确保迭代点始终位于可行域内。这对于工程优化和资源分配问题非常重要，因为中间解也往往必须满足实际约束。投影机制使子梯度法更适合直接应用于有约束模型。
3.4 变体与扩展
为了改善原始子梯度法收敛较慢的问题，研究者提出了多种变体。这些方法通常在稳定性、历史信息利用或方向修正方面作出改进。
3.4.1 重球法
重球法在更新中加入动量或惯性项，使当前迭代不仅受即时子梯度影响，也受历史方向影响。其目标是加快搜索并减少震荡。不过，在非光滑问题中，动量项若设置不当，也可能带来额外不稳定性。
3.4.2 聚合子梯度法
聚合子梯度法会综合多个历史子梯度的信息，以形成更平滑、更稳健的更新方向。它常用于大规模问题或分布式环境中，能够在一定程度上缓解单步子梯度噪声较大的缺点。
4 收敛性分析
子梯度法的理论研究重点之一是其收敛性质。总体而言，它能保证在合适条件下逼近最优解，但速度通常不如光滑优化方法理想。对于工程应用来说，理解其收敛特征有助于合理设置迭代预算与步长策略。
4.1 收敛速度
子梯度法通常被认为具有较典型的次线性收敛特征，即误差下降速度随迭代次数增加而逐渐减缓。这意味着它适合获得可接受的近似解，但不擅长高精度快速求解。
4.1.1 次线性收敛特征
在很多标准设定下，子梯度法的最优值误差常与迭代次数的平方根或其倒数相关，体现出比线性收敛更慢的行为。虽然单步进展有限，但其实现简单、适用面广，仍使其在大规模问题中具有实际价值。
4.1.2 误差界估计
误差界通常用来描述当前迭代点与最优解之间的距离或目标值差距。分析中会引入函数值上界、梯度范数界和可行域直径等量，建立迭代误差的定量估计。这些界限为步长选择与停止条件提供了依据。
4.2 步长对收敛的影响
步长设置直接决定子梯度法是否稳定以及最终能达到何种精度。步长过大可能使误差来回震荡，过小则会使算法进展迟缓。递减步长通常更利于理论收敛，而自适应步长则更偏向实践性能优化。
4.3 有界性与稳定性
若目标函数或约束集满足一定有界条件，迭代点序列更容易保持稳定，不会无限发散。稳定性分析通常关注子梯度的上界、步长序列以及投影操作是否足以抑制数值波动。对于非光滑问题，这些因素尤其重要。
4.4 最优解逼近性质
在适当假设下，子梯度法生成的迭代序列可以使目标值逐步逼近最优值。虽然单个迭代点未必总是单调改进，但经过平均化处理或选取最佳历史点后，常能得到更稳健的逼近效果。这也是很多实际算法采用“平均迭代”或“最优历史点输出”的原因。
5 典型应用
子梯度法的应用范围很广，凡是含有非光滑结构且又具有凸性或近似凸性的模型，都可能成为其用武之地。
5.1 稀疏优化
稀疏优化旨在得到尽可能少的非零变量，这在信号恢复、特征选择和模型压缩中十分常见。由于稀疏约束常可通过 \(L_1\) 范数表达，因此子梯度法常被用于此类问题。
5.1.1 L1 正则化
L1 正则化通过加入绝对值惩罚项鼓励参数稀疏化。该项在零点处不可微，因此非常适合用子梯度法处理。尽管后来出现了近端方法等更高效的策略，子梯度法仍是理解这类模型的基础工具之一。
5.1.2 特征选择
在统计学习中，特征选择希望从大量变量中筛出少数重要特征。含 L1 惩罚的目标函数可以在训练过程中自动压缩不重要参数，而子梯度法可直接用于求解这类带非光滑项的优化模型。
5.2 支持向量机
支持向量机是经典的分类方法，其优化问题通常包含铰链损失或间隔相关的非光滑项，因此常与子梯度法相结合。
5.2.1 损失函数优化
SVM 的损失函数往往不是处处可微，但具有凸性。子梯度法能够直接处理铰链损失带来的折点结构，在大样本训练中具有实现简洁的优势。
5.2.2 间隔最大化
支持向量机的目标之一是最大化分类间隔。该问题在几何上对应寻找分隔超平面，并通过约束和损失共同确定最优解。子梯度法适合在这一框架下进行迭代求解。
5.3 信号处理
在信号恢复、去噪和压缩采样中，经常出现非光滑目标函数，例如绝对值惩罚、稀疏先验或鲁棒损失。子梯度法因此成为该领域常用的基础优化工具。
5.3.1 去噪模型
去噪模型通常希望在保留信号结构的同时抑制噪声。若目标中包含鲁棒损失或总变差项，就会产生不可微结构。子梯度法可以对这类模型进行逐步求解。
5.3.2 压缩感知
压缩感知强调用较少观测重建稀疏信号，优化模型通常带有 L1 惩罚或相关非光滑正则项。子梯度法在概念上简单，适合解释稀疏恢复问题的基本求解思路。
5.4 资源分配与调度
在资源有限的系统中，如何在多个任务之间分配预算、时间或带宽，往往可归结为约束优化问题。子梯度法常用于求解这些带有成本与约束的模型。
5.4.1 约束优化
很多资源分配问题的可行域是凸的，但目标函数可能并不光滑。投影子梯度法可在满足约束的前提下不断调整分配方案，使结果逐渐接近最优。
5.4.2 成本最小化
成本最小化模型常包含分段费用、阶梯惩罚或稀疏使用成本，这些结构往往导致函数不可微。子梯度法能够直接处理这种形式，因此在调度与管理问题中具有实用性。
6 算法实现与计算细节
子梯度法虽然思想简单，但在实际实现时仍需处理终止条件、数值误差和计算开销等问题。合理的工程设计能显著提升算法的可用性。
6.1 终止准则
终止准则用于判断迭代是否可以结束。由于子梯度法常不追求严格的点态收敛，终止条件通常基于迭代次数、目标值改变量或近似最优性指标。
6.1.1 迭代次数上限
最常见的终止方式是预先设定最大迭代次数。此方法简单可靠，适合在时间预算明确的应用中使用，也便于与其他算法公平比较。
6.1.2 目标值变化阈值
当连续若干次迭代的目标值变化小于给定阈值时，可认为算法已进入平台区或接近稳定状态。这种方式比单纯的迭代次数更贴近实际优化质量，但对噪声较敏感。
6.2 数值稳定性
数值稳定性主要涉及步长过大导致震荡、子梯度范数过大引发溢出，以及投影误差累积等问题。实际实现中常需对变量进行归一化、截断或平滑处理，以减少不必要的数值波动。
6.3 复杂度分析
子梯度法每步迭代的计算通常较轻，主要成本来自子梯度求取和投影操作。因此，它特别适合维度较高但单步计算需求较低的问题。若投影本身代价高，则整体效率会明显下降。
6.4 伪代码结构
标准伪代码一般包括：初始化点、循环计算子梯度、按步长更新、必要时投影、检查终止条件。由于结构简明，子梯度法常作为入门优化算法出现在教材与基础库实现中，也便于与其他方法组合使用。
7 相关方法比较
子梯度法在优化领域并非唯一选择。根据目标函数的光滑性、约束形式以及精度要求，研究者往往会选取更合适的替代方法。
7.1 与梯度下降法比较
梯度下降法要求可微，因而在光滑问题上通常更稳定、更容易获得较快收敛。子梯度法则能处理不可微函数，适用范围更广，但代价是更新方向更粗糙、收敛速度较慢。两者在形式上相似，但适用边界不同。
7.2 与近端梯度法比较
近端梯度法常用于“光滑项 + 非光滑项”的复合优化结构。相较于直接使用子梯度法，它通常能更好地利用问题分解，因而在稀疏学习中表现更佳。子梯度法的优势在于概念更直接、实现更统一。
7.3 与牛顿法比较
牛顿法依赖二阶信息，在光滑且结构良好的问题上可能获得很快的局部收敛。然而它对可微性和海森矩阵性质要求较高，且每步计算成本大。子梯度法不需要二阶导数，适合非光滑和大规模场景，但精度提升较慢。
7.4 与坐标下降法比较
坐标下降法每次只优化一个或少数变量，适合具有坐标可分结构的问题。子梯度法则更强调整体方向更新。对于某些稀疏问题，坐标下降可能更高效；而在复杂约束或统一非光滑结构下，子梯度法更易实现。
8 历史与发展
子梯度法的发展与凸优化、非光滑分析和运筹学的成熟密切相关。它作为一阶方法家族中的重要成员，长期在理论研究和工程实践中占据稳定位置。
8.1 理论起源
子梯度方法的思想源于对凸函数支撑结构的研究，以及对不可微优化可行性的探索。随着凸分析理论逐步完善，研究者开始系统地将次微分用于优化迭代，形成了早期的子梯度算法框架。
8.2 经典研究成果
经典成果主要集中在收敛条件、步长规则和误差估计等方面。相关研究表明，在适当假设下，子梯度法可以稳定逼近最优解，并可通过平均化、投影和变步长策略改善实际表现。这些结论奠定了其在现代优化中的基础地位。
8.3 现代优化中的应用演进
随着机器学习和大规模数据分析的发展，子梯度法的应用从传统运筹优化扩展到稀疏学习、分类模型和信号恢复等领域。尽管近端方法、加速方法和分布式算法不断涌现，子梯度法仍因其通用性强、实现简单而被广泛作为基础方案或教学起点使用。