图的次梯度与次梯度优化 基本概念引入 在图论中，图的 次梯度 （Subgradient）是凸优化理论在图结构上的推广，用于处理目标函数不可导时的优化问题。具体来说，给定一个图 \( G = (V, E) \) 和定义在顶点集上的实值函数 \( f: V \to \mathbb{R} \)，若函数在某点不可导（如分段线性函数），其次梯度是一个集合，包含所有满足特定不等关系的方向向量。对于图上的函数，次梯度通过图的邻接关系定义局部线性逼近。 次梯度的数学定义 设 \( f \) 是图顶点集上的凸函数（例如，顶点赋权函数）。对于顶点 \( v \in V \)，其次梯度 \( \partial f(v) \) 是所有向量 \( g \in \mathbb{R}^{|V|} \) 的集合，使得对任意顶点 \( u \) 有： \[ f(u) \geq f(v) + g^T (\mathbf{1}_ u - \mathbf{1}_ v), \] 其中 \( \mathbf{1}_ x \) 表示顶点 \( x \) 的指示向量。此定义扩展了连续空间中的次梯度概念，通过图的离散结构关联顶点间的函数值变化。 次梯度与图上的优化问题 次梯度用于解决图上的非光滑优化问题，例如： 图切割问题 ：最小化顶点集划分的边权值和，目标函数不可导时需用次梯度方法。 标签传播问题 ：在半监督学习中，基于图结构的函数优化常涉及次梯度下降算法。 优化过程通过迭代更新顶点函数值： \[ f^{(k+1)}(v) = f^{(k)}(v) - \alpha_ k g_ k, \quad g_ k \in \partial f(v), \] 其中 \( \alpha_ k \) 为步长，次梯度 \( g_ k \) 指导函数值向极小值方向移动。 次梯度优化的收敛性 由于次梯度方向不一定为下降方向，算法收敛性需谨慎处理。常用技巧包括： 动态步长选择（如 \( \alpha_ k = \frac{1}{\sqrt{k}} \) 保证渐近收敛）。 结合图的拓扑约束（如拉普拉斯正则化）确保解平滑性。 对于大规模图，可并行计算各顶点的次梯度，提升效率。 应用场景 次梯度优化在图论中广泛应用于： 网络流平衡 ：优化节点负载函数，避免不可导点导致的算法失效。 图信号处理 ：基于图傅里叶变换的非平滑信号恢复。 机器学习 ：图神经网络的损失函数优化中处理ReLU激活函数的不可导性。