Skip to content

定义Definition

次梯度与次微分

施工中 · 内容逐步修订

Subgradient · Subdifferential

以全局仿射下界刻画凸函数在不可微点的支撑斜率集合。

形式陈述 ​

设 f:X→R∪{+∞} 是实内积空间上的 proper 凸函数,且 x∈domf。若向量 g 对所有 y∈X 都满足

f(y)≥f(x)+⟨g,y−x⟩,

则称 g 是 f 在 x 处的次梯度。所有次梯度组成次微分

∂f(x)={g:f(y)≥f(x)+⟨g,y−x⟩ 对所有 y}.

若 f 在 x 的开邻域 Fréchet 可微,且导数可由空间内向量表示为 Df(x)[h]=⟨∇f(x),h⟩,则 ∂f(x)={∇f(x)}。这种表示在有限维或 Hilbert 空间由Riesz 表示定理保证存在;一般不完备内积空间不能省略表示条件。对 proper 凸函数,

0∈∂f(x)⟺x∈argminf,

因为次梯度不等式在 g=0 时正是全局最小性。次微分可以为空;在有限维中,proper 凸函数在定义域相对内部的点具有非空次微分,但定义域边界没有这一无条件保证。

直觉

普通梯度用切平面描述光滑图像的局部一阶变化;次梯度要求更强:对应的仿射平面必须从下方支撑整张凸图像。尖点可能容纳一整束支撑斜率,所以“次梯度”通常不是唯一向量。它也不是任意方向导数:方向导数描述沿某个方向怎样变化,次梯度则同时对所有 y 给出一条全局下界。正因为约束是全局的,包含零斜率便足以认证全局最优。

相对内部为什么有支撑斜率 ​

这里仅证明有限维结论,且不额外假定 f 闭。固定 x∈ri(domf),把仿射包平移为 x+E,在 E 中选正交坐标。若 dim⁡E=0,定义域只有 x,零向量已是次梯度。否则可取 r>0,使以 x 为中心、坐标半宽 r 的闭盒完全包含于定义域。令 M 为有限个顶点函数值的最大值;凸性使盒内 f≤M,且 M≥f(x)。对 0<‖h‖∞≤r,令 t=‖h‖∞/r。点 x±h/t 在盒内,沿线段的凸性给

f(x±h)≤f(x)+t(M−f(x)).

再由 x 是 x+h 与 x−h 的中点,得到

|f(x+h)−f(x)|≤t(M−f(x))⟶0.

因此 f 在 x 相对于仿射包连续。

现在在 (x+E)×R 中取上图像的闭包 C=epi(f|x+E)―。刚才的连续性保证 (x,f(x)) 是其边界点:每个 (x,f(x)−ε) 都有邻域与上图像不交。对这个闭凸集使用支撑超平面定理,选非零法向量 (a,b),使

⟨a,y−x⟩+b(t−f(x))≥0((y,t)∈C).

上图像向上封闭,故 b≥0。若 b=0,定义域中 x 的相对邻域包含每个小方向及其反向,迫使 a=0,矛盾。因此 b>0,代入 t=f(y) 得相对次梯度 −a/b。把这个 E 中的向量视作环境空间向量,就得到对全部 y∈domf 的支撑;域外值为 +∞,不等式自动成立。这里先闭包、再排除竖直支撑,避免把未闭上图像直接送入闭集版本的定理。

例子与边界

对 f(x)=|x|,当 x>0 时 ∂f(x)={1},当 x<0 时为 {−1}。在尖点 x=0,不等式 |y|≥gy 对所有 y 成立恰要求 g∈[−1,1],故

∂|⋅|(0)=[−1,1].

区间包含零,所以零点是全局最小点;这比给 |x| 人为指定一个“导数”更准确。

这一整个区间在稀疏优化中不可替换成单个零。在有限维欧氏空间取 λ≥0,对 P(x)=‖Ax−b‖2/2+λ‖x‖1,零坐标的最优性要求 AjT(b−Ax)∈λ[−1,1],非零坐标才要求它等于 λsign(xj)。在Lasso 的完整证书算例中,最优解 (1,0) 的残差相关性是 (1,1/2):第二个次梯度分量为 1/2,恰好能与光滑项抵消。若硬把零处的次梯度定成零,反而会错拒这个最优解。

边界处次微分确实可能为空。令 f(x)=−x(x≥0),并在 x<0 取 +∞;这是 proper 闭凸函数。若 g∈∂f(0),则对所有 y>0 要有 −y≥gy,即 g≤−1/y,不存在有限 g 能对趋近零的所有 y 成立。非凸函数也有 Clarke 次微分等广义概念,但它们使用不同定义与演算规则,不属于本页对象。

不完备空间还会带来另一种空次微分。令 X=c00 为有限支撑实序列,赋予 ℓ2 内积,取连续线性函数 f(x)=∑n≥1xn/n。由Cauchy–Schwarz 不等式,|f(x)|≤‖x‖2(∑n≥1n−2)1/2,所以它处处 Fréchet 可微。若有 g∈∂f(x),对任意增量 h 同时使用 h 与 −h,就必须有 ⟨g,h⟩=f(h);代入标准基得到 gn=1/n,这不属于 c00。因此没有原空间内的梯度向量或次梯度,尽管导数作为连续线性泛函完全存在。

推论与应用

Fenchel–Young 不等式取等当且仅当 g∈∂f(x),这把支撑斜率与对偶变量精确对应。对凸约束集 C,指标函数 δC 的次微分是法锥。精确的约束最优性条件是 0∈∂(f+δC)(x);满足次微分求和规则的资格条件后,才能进一步拆成 0∈∂f(x)+NC(x)。近端算子的最优性条件 (x−y)/λ∈∂f(y) 又把不可微最小化转成一个次微分关系。次梯度法、稀疏正则化和凸对偶都依赖这一接口,但非光滑处的次梯度不唯一意味着算法还需要明确选择规则与步长条件。

对 f(x)+g(Ax),原对偶证书要求同一个 y 满足 −ATy∈∂f(x) 与 y∈∂g(Ax)。相对内部资格加上原最优点存在,才保证这种分解证书存在;该页沿用 −x 的边界例子,算出零间隙却没有最优乘子的对偶,说明次微分在边界为空会怎样影响最优性表示。

凸回归把每个训练点的次梯度当作插值见证:θj≥θi+ζiT(xj−xi)对全部i,j成立,就可用这些仿射函数的最大值构造一个全空间凸延拓。即使训练高度唯一,见证ζi仍可不同,未见点的预测也可改变;仅有两个端点零高度时,零函数与任意深的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:全局支撑、内部非竖直支撑与零次梯度。本文另展开相对仿射包的连续性及闭包步骤,完整覆盖原声明的有限维相对内部。

关系图谱49 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系