形式陈述
设 是实内积空间理路内积空间Inner product space带正定对称双线性形式或正定 Hermitian 半双线性形式的向量空间。上的 proper 凸函数理路凸函数Convex function函数在任意凸组合处不超过相同权重下函数值的凸组合。,且 。若向量 对所有 都满足
则称 是 在 处的次梯度。所有次梯度组成次微分
若 在 的开邻域 Fréchet 可微,且导数可由空间内向量表示为 ,则 。这种表示在有限维或 Hilbert 空间由Riesz 表示定理理路Hilbert 空间 Riesz 表示定理Riesz representation theorem for Hilbert spacesHilbert 空间上的每个连续线性泛函都唯一由与某向量取内积表示。保证存在;一般不完备内积空间不能省略表示条件。对 proper 凸函数,
因为次梯度不等式在 时正是全局最小性。次微分可以为空;在有限维中,proper 凸函数在定义域相对内部的点具有非空次微分,但定义域边界没有这一无条件保证。
直觉
普通梯度用切平面描述光滑图像的局部一阶变化;次梯度要求更强:对应的仿射平面必须从下方支撑整张凸图像。尖点可能容纳一整束支撑斜率,所以“次梯度”通常不是唯一向量。它也不是任意方向导数:方向导数描述沿某个方向怎样变化,次梯度则同时对所有 给出一条全局下界。正因为约束是全局的,包含零斜率便足以认证全局最优。
相对内部为什么有支撑斜率
这里仅证明有限维结论,且不额外假定 闭。固定 ,把仿射包平移为 ,在 中选正交坐标。若 ,定义域只有 ,零向量已是次梯度。否则可取 ,使以 为中心、坐标半宽 的闭盒完全包含于定义域。令 为有限个顶点函数值的最大值;凸性使盒内 ,且 。对 ,令 。点 在盒内,沿线段的凸性给
再由 是 与 的中点,得到
因此 在 相对于仿射包连续。
现在在 中取上图像的闭包 。刚才的连续性保证 是其边界点:每个 都有邻域与上图像不交。对这个闭凸集使用支撑超平面定理理路分离与支撑超平面定理Separating hyperplane theorem · Supporting hyperplane theorem用线性泛函分开凸集或在其边界处构造全局支撑超平面。,选非零法向量 ,使
上图像向上封闭,故 。若 ,定义域中 的相对邻域包含每个小方向及其反向,迫使 ,矛盾。因此 ,代入 得相对次梯度 。把这个 中的向量视作环境空间向量,就得到对全部 的支撑;域外值为 ,不等式自动成立。这里先闭包、再排除竖直支撑,避免把未闭上图像直接送入闭集版本的定理。
例子与边界
对 ,当 时 ,当 时为 。在尖点 ,不等式 对所有 成立恰要求 ,故
区间包含零,所以零点是全局最小点;这比给 人为指定一个“导数”更准确。
这一整个区间在稀疏优化中不可替换成单个零。在有限维欧氏空间取 ,对 ,零坐标的最优性要求 ,非零坐标才要求它等于 。在Lasso 的完整证书算例理路Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标,并用可行对偶值认证剩余优化误差。中,最优解 的残差相关性是 :第二个次梯度分量为 ,恰好能与光滑项抵消。若硬把零处的次梯度定成零,反而会错拒这个最优解。
边界处次微分确实可能为空。令 (),并在 取 ;这是 proper 闭凸函数。若 ,则对所有 要有 ,即 ,不存在有限 能对趋近零的所有 成立。非凸函数也有 Clarke 次微分等广义概念,但它们使用不同定义与演算规则,不属于本页对象。
不完备空间还会带来另一种空次微分。令 为有限支撑实序列,赋予 内积,取连续线性函数 。由Cauchy–Schwarz 不等式理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积,且等号精确刻画线性相关。,,所以它处处 Fréchet 可微。若有 ,对任意增量 同时使用 与 ,就必须有 ;代入标准基得到 ,这不属于 。因此没有原空间内的梯度向量或次梯度,尽管导数作为连续线性泛函完全存在。
推论与应用
Fenchel–Young 不等式理路凸共轭与 Fenchel–Young 不等式Convex conjugate · Fenchel conjugate · Fenchel–Young inequality以线性函数的最佳配对代价定义共轭,并导出原变量与对偶变量间的基本不等式。取等当且仅当 ,这把支撑斜率与对偶变量精确对应。对凸约束集 ,指标函数 的次微分是法锥。精确的约束最优性条件是 ;满足次微分求和规则的资格条件后,才能进一步拆成 。近端算子理路近端算子Proximal operator · Proximity operator在降低凸函数值与保持靠近输入点之间取得精确平衡的单值算子。的最优性条件 又把不可微最小化转成一个次微分关系。次梯度法、稀疏正则化和凸对偶都依赖这一接口,但非光滑处的次梯度不唯一意味着算法还需要明确选择规则与步长条件。
对 ,原对偶证书理路Fenchel 对偶与原对偶单调包含Fenchel duality · Primal-dual monotone inclusion从复合凸问题的相对内部资格推出对偶乘子,以两份 Fenchel 等号认证最优,再构造极大单调系统并手算完整预解轨道。要求同一个 满足 与 。相对内部资格加上原最优点存在,才保证这种分解证书存在;该页沿用 的边界例子,算出零间隙却没有最优乘子的对偶,说明次微分在边界为空会怎样影响最优性表示。
凸回归理路有限设计的凸最小二乘回归Convex least squares regression · Multivariate convex regression · 凸回归的有限证书将凸函数类上的加权平方拟合精确化为逐对支撑平面约束,证明拟合值唯一、交付全局乘子证书,并区分非等距斜率约束、未见点延拓与统计风险。把每个训练点的次梯度当作插值见证:对全部成立,就可用这些仿射函数的最大值构造一个全空间凸延拓。即使训练高度唯一,见证仍可不同,未见点的预测也可改变;仅有两个端点零高度时,零函数与任意深的V形函数都合法。因此需要把选择延拓的规则与求训练高度的优化问题分别写清楚。
参考资料
-
R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press, 1970,§§23–25,尤其 Theorem 23.4 的相对内部存在性。
-
Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004,§3.1.3 and §5.5, first-order conditions and optimality。
-
S. Boyd、J. Duchi、M. Pilanci、L. Vandenberghe,Subgradients,2022-04-13,§§1–2.3,页 1–3:全局支撑、内部非竖直支撑与零次梯度。本文另展开相对仿射包的连续性及闭包步骤,完整覆盖原声明的有限维相对内部。