动机
Hessian 正定时,牛顿(Newton)步最小化局部二次模型,但离中心太远时模型可能不准确;Hessian 不定时,无约束二次模型甚至可能无下界。信赖域把线搜索的问题倒过来:先限制模型可信的移动距离,再比较预测改善与实际改善。若两者差距太大,便缩小区域重试。
限制于球内令任何连续二次模型都取得最小值,即使存在负曲率。实用算法未必需要精确解此子问题;也可要求至少取得负梯度方向所提供下降量的一定比例。本节分清精确模型解、廉价的受保障 Cauchy 步,以及推导一阶收敛所需的假设。这些结论均不保证非凸目标的全局最小值。
定义
定义 10.1.1
(信赖域模型、预测下降量与吻合比率)
在 xk 令 fk=f(xk)、gk=∇f(xk)。选对称矩阵 Bk 和半径 0<Δk≤Δmax。试探步 sk 的模型及预测下降量为
mk(s)=fk+gkTs+21sTBks,predk=mk(0)−mk(sk),∥sk∥≤Δk.预测下降量为正时,定义吻合比率
ρk=predkf(xk)−f(xk+sk).
比率把实际下降量与模型承诺的下降量作比较,半径规则再决定如何处理试探步。取 0<η1<η2<1、0<γdec<1<γinc。若 ρk<η1,拒绝试探步,令 xk+1=xk、Δk+1=γdecΔk。否则接受,令 xk+1=xk+sk;半径保持不变,但若 ρk≥η2 且 ∥sk∥=Δk,可扩至 min{γincΔk,Δmax}。拒绝试探虽不改变迭代点,仍算分析中的一步。若 gk=0,算法停止;以下步长及比率只在 gk=0 时有定义。
假设已知 ∥Bk∥≤β,β≥0,令 Cβ=1+β。对 gk=0,受保障 Cauchy 步定义为
sk=−tkgk,tk=min{1/Cβ, Δk/∥gk∥}.
额外上限在梯度很小时限制步长。沿可行负梯度射线精确最小化模型至少能取得同样下降,但未必满足这个长度上限。以下全局定理明确使用它,不能把它暗中加到所有信赖域方法上。
定理/命题
对对称 B 和 Δ>0,s∗ 在 ∥s∥≤Δ 上最小化 gTs+21sTBs,当且仅当存在 λ≥0 满足
(B+λI)s∗=−g,B+λI⪰0,∥s∗∥≤Δ,λ(Δ−∥s∗∥)=0.
定理 10.1.4
(受保障 Cauchy 步的一阶收敛)
设 f 在 Rn 连续可微、有下界,梯度以 L>0 为 Lipschitz 常数。各对称 Bk 满足 ∥Bk∥≤β,算法使用上述半径规则和受保障 Cauchy 步。除非在驻点停止,否则 ∥gk∥→0。
第一个结果描述模型的全局最小点,包括不定及奇异情况。第二个结果只对指定步长规则证明梯度趋于零,并非任意模型求解器的定理。更强的求解器需另给下降及步长控制假设。此梯度结论不要求迭代点有界、目标凸或最小点存在;若有聚点,梯度的连续性使它成为驻点。
概念视角分析
从牛顿步到最速下降的一条精确步曲线
在困难情况之外,半径为 Δ 的模型极小点位于曲线 s(λ)=−(B+λI)−1g(λ>ℓ)上,其中 ℓ=max{0,−imindi} 与下面的证明相同。其范数随 λ 不增,所以缩小 Δ 会使边界解沿曲线移向更大的 λ。若 B≻0,曲线在 λ=0 处从牛顿步 −B−1g 出发;当 λ→∞ 时,λs(λ)→−g。因此,小信赖域会把精确步转向 Cauchy 步所用的最速下降方向。
证明思路
模型最优性及困难情况
若所列条件成立,对任意可行 s 展开模型差:
m(s)−m(s∗)=21(s−s∗)T(B+λI)(s−s∗)+2λ(∥s∗∥2−∥s∥2)≥0.第一项非负;若 λ>0,互补条件令 s∗ 在边界,第二项也非负;若 λ=0,第二项为零。故即使 B 不定,这些条件仍充分。
证必要性时,对角化 B=Qdiag(di)QT,令 a=QTg 和 ℓ=max{0,−imindi}。对 λ>ℓ,驻点解各分量为 zi=−ai/(di+λ);其范数连续、不递增,且在 λ→∞ 时趋零。若 B⪰0、g 在其值域,而 λ=0 时最小范数解不超过 Δ,它直接满足条件。
否则,若 λ↓ℓ 的范数极限大于 Δ 或为无限,连续性给出 λ>ℓ 使 ∥z∥=Δ。余下情况有 ℓ>0,a 与特征值 −ℓ 的特征空间正交,而极限的最小范数解不超过 Δ。加入该特征空间中的向量,使它到达边界;新点仍解 (B+ℓI)s=−g。这便是奇异的困难情况。构造出的点满足充分条件,故是全局最小点。其他全局最小点有相同值,模型差公式中的非负项必同为零。对 H=B+λI⪰0,二次型为零给出 H(s−s∗)=0,故 Hs=−g;若 λ>0,第二项也迫使 ∥s∥=Δ。因此相同的驻点及互补条件成立。证明没有假设 Hessian 可逆。
收敛定理的证明分两部分:先证明足够小的半径终会被接受,再把接受步的下降转化为梯度趋于零。
Cauchy 下降及足够小的半径
令 t=tk,由矩阵范数界得
mk(0)−mk(−tgk)=t∥gk∥2−21t2gkTBkgk≥21∥gk∥min{Δk,∥gk∥/Cβ}.因为 tβ≤β/Cβ<1。步长也满足 ∥sk∥≤∥gk∥/Cβ。Lipschitz 梯度估计与 ∥Bk∥≤β 给出,令 C=(L+β)/2>0,
∣f(xk+sk)−mk(sk)∣≤C∥sk∥2≤CΔk2.固定 ε>0。若 ∥gk∥≥ε 且 Δk≤min{ε/Cβ,(1−η1)ε/(2C)},Cauchy 界推出 ∣1−ρk∣≤1−η1,因此该步被接受。故梯度至少为 ε 时,拒绝的步不能把半径缩至低于上述阈值的 γdec 倍。
由接受步下降推出梯度趋零
先假设最终所有 ∥gk∥≥ε。由上段,从那时起半径有共同正下界:接受不会缩小半径;拒绝只在半径高于上述阈值时发生,所以半径至多降到阈值的 γdec 倍。Cauchy 界与 ρk≥η1 因而令每次接受的目标下降量有固定正下界。f 有下界,所以不可能无限次接受;但连续拒绝也不可能无限,因半径终会小到可接受。矛盾证明 kliminf∥gk∥=0。
再证完整极限。固定 a>0。在接受步且 ∥gk∥≥a、Δk≤a/Cβ 时,目标下降至少为 (η1a/2)Δk≥(η1a/2)∥sk∥。若 ∥gk∥≥a 且 Δk>a/Cβ,每次接受至少下降 η1a2/(2Cβ),故只可能有限次,每一步的长度均有限。因此,起点梯度至少为 a 的接受步,其总长度有限;拒绝步位移为零。
选 a>0 使 (1+L/Cβ)a<ε/2。由保障步长及 Lipschitz 条件,若一步起点梯度小于 a,终点梯度仍小于 ε/2。若梯度无限次达到 ε,但下极限为零,选一个梯度至少为 ε 的指标 ℓ,在它之前存在梯度小于 a 的指标;令 j 为 ℓ 前最后一个这样的指标。则 ∥gj+1∥<ε/2,而 j+1,…,ℓ−1 各步起点梯度至少为 a。Lipschitz 连续性迫使这些步的总路程至少为 ε/(2L)。无限多个互不重叠的过程与总长度有限矛盾。因此梯度趋零。长度上限正是在跨入这类过程时使用。
一起解读两个误差估计
证明透视
半径缩小为何恢复吻合
各项假设在不同位置使用。一致界 ∥Bk∥≤β 用了两次:在 Cauchy 不等式中保证 tβ<1,在误差估计中控制模型曲率。梯度的 Lipschitz 连续性提供误差估计的另一半,之后又把梯度范数的变化转化为移动距离。f 有下界只用来保证接受步的下降量之和有限。
关键一步是比较阶数。Cauchy 不等式是模型预测下降量的下界;Lipschitz 估计则是实际值偏离预测的上界。当梯度有正下界而半径很小时,保证的预测量与半径成正比,模型误差却与半径的平方成正比,因此充分小的半径迫使 ρk≥η1。若不知道预测下降不会更快地趋于零,只说模型局部准确并不够。
仅靠这一比较只能得到 kliminf∥gk∥=0。论证最后把下降转化为长度:梯度大的接受步总长度有限,而每一段从梯度小于 a 走到梯度至少为 ε 的过程必须移动至少 ε/(2L)。上限 ∥sk∥≤∥gk∥/Cβ 防止这类过程以一次长跳开始。
定理允许每一步的 Bk 奇异或不定,因为 Cauchy 论证只用到其一致范数界。它也允许连续拒绝许多试探,但在固定的非驻点处不可能永远拒绝:半径反复乘以 γdec 后,前述比较必然迫使接受。上界 Δmax 是方便的既定规则;有限路程论证并不依赖它,因为大半径接受步只有有限多次。
被拒绝的模型与比率的意义
考虑 f(x)=x4/4 在 x=1,故意选模型曲率 B=−4,而非真实 Hessian。半径为一时,精确模型最小步是 s=−1:模型变化 s−2s2 在两端点中较小的值为 −3。预测下降为 3,实际从一到零的下降仅 1/4,所以 ρ=1/12,接受阈值 η1=0.1 会拒绝此步。模型过于乐观;拒绝避免把预测当作实际进展。
若半径缩至 1/2,精确模型步为 s=−1/2。预测下降为一,实际下降是 1/4−(1/2)4/4=15/64,比率 15/64>0.1,所以此试探被接受。这只说明比率规则,不是全局定理的例子:x4/4 在整条实线的梯度并非全局 Lipschitz,而且此处使用精确模型步,而非受保障 Cauchy 步。
信赖域乘子不是罚系数
概念视角结构
只属于模型的乘子
乘子 λ 属于某个固定二次子问题。对边界解,它将 Hessian 移位至非负曲率,同时满足驻点方程及边界长度条件;即使半径不变,它也可随迭代改变。它不是原决策问题约束的乘子,也不可与另一受约束问题所选的罚系数混为一谈。
对一维凸模型 m(s)=gs+bs2/2,b>0,无约束最小点为 −g/b。若其绝对值不超过 Δ,取 λ=0。否则最小点为端点 s∗=−Δsign(g),驻点条件给出 λ=∣g∣/Δ−b>0。此公式显示容许位移缩小时乘子如何增大。在转折点 ∣g∣=bΔ,无约束最小点位于边界,但 λ=0;边界活跃并不保证乘子严格为正。
原目标的驻点仍可能有负曲率。本节的一阶规则明确容许 g=0 时停止,所以可能停在鞍点或最大点。若要寻找二阶驻点,算法需检查负曲率并加入额外下降条件和收敛证明。不定模型例子显示信赖域子问题能利用负曲率,却不会自动把一阶定理变成二阶定理。
例题详解
例题 10.1.5
(不定模型在球内仍有有限最小点)
在 ∣s∣≤2 上取 m(s)=−s2/2,s∗=2 及 s∗=−2 均最小。此时 g=0、B=−1、λ=1,故 B+λ=0 且四个条件均成立。无约束模型却无下界;球约束从根本改变了问题。
取 B=diag(−1,2)、g=(0,1)T、Δ=1。在 λ=1,驻点方程给 s2=−1/3,s1 自由;边界条件给 s1=±8/3。由于 B+I=diag(0,3) 半正定,两点均为模型全局最小点。若硬要求 B+I 的逆,便会漏掉它们。
对 f(x)=x2/2 在 x=2,用精确 Hessian B=1。无约束牛顿步为 −2;半径一时精确模型步为 −1,得到 x+=1。模型和目标相同,预测及实际下降都是 3/2,故 ρ=1。之后较大的半径可容许完整牛顿步。
常见错误
比率为正说明目标值下降了,但上述规则只在 ρk≥η1 时接受。在被拒绝模型的计算中,ρ=1/12 为正,但取 η1=0.1 时试探仍被拒绝。收敛证明利用 ρk≥η1 把预测下降转化为实际下降的固定比例;仅仅为正的比率给不出这样的比例。
当 ∥s∗∥=Δ 且 λ>0 时,最小点解的是 (B+λI)s=−g,而不是 Bs=−g。在以球保障牛顿步的例题中,g=2、B=1、Δ=1;边界步 s∗=−1 对应 λ=1,因为 (1+1)(−1)=−2=−g。牛顿方程则给出不可行的 s=−2。
常见错误
(在困难情形中对移位 Hessian 求逆)
人们很容易计算 s(λ)=−(B+λI)−1g,再调整 λ 直到 ∥s(λ)∥=Δ。对 B=diag(−1,2)、g=(0,1)T、Δ=1,每个允许的 λ>1 都给出 s(λ)=(0,−1/(2+λ))T,其范数小于 1/3,所以任何求逆得到的解都到不了边界。最小点要用奇异移位 λ=1,再加上特征向量分量 s1=±8/3。
模型证书中的半正定条件并非摆设:没有它,其余条件可能认证球内最差的点。
反例模式
只有驻点与互补条件而没有曲率条件
断言:若可行点 s∗ 对某个 λ≥0 满足 (B+λI)s∗=−g 及 λ(Δ−∥s∗∥)=0,则 s∗ 在球上最小化模型。取 m(s)=s−s2/2,即 g=1、B=−1,并取 Δ=1。边界点 s=1 在 λ=0 时满足 (−1+0)⋅1=−1=−g,互补条件也平凡成立。然而 m(1)=1/2、m(−1)=−3/2;由于在 [−1,1] 上 m′(s)=1−s≥0,s=1 其实是最大点。失效的正是被省略的条件:B+0=−1 不是半正定的。在 s=−1 处,驻点条件 (−1+λ)(−1)=−1 给出 λ=2,而 B+2=1≥0,完整的证书正确找出真正的最小点。
本证明使用步长上限;其他分析可用 Cauchy 下降的一定比例,以不同论证得到相同的梯度结论,这里不作推导。
总结
信赖域令二次子问题有限,并容许负曲率下的全局证书。移位半正定 Hessian 与互补半径乘子刻画精确模型最小点。受保障 Cauchy 步提供定量预测下降;半径充分小时模型可靠,再由接受下降及步长控制,在明列假设下证明梯度趋零。
练习
快速检查
(在 ∣s∣≤1/2 上最小化 m(s)=s+s2/2,并求半径乘子。)
解答
无约束最小点 −1 在球外。由于在 [−1/2,1/2] 上 m′(s)=1+s>0,模型在该区间递增,受约束最小点为 s=−1/2。由 (1+λ)(−1/2)=−1 得 λ=1;移位 Hessian 1+λ=2 为正,而 s 在边界上,互补条件成立。
快速检查
(若 g=(1,0)T、B=diag(2,1)、半径为一,以矩阵范数界 β=2 计算受保障 Cauchy 步及其预测下降。)
解答
这里 Cβ=3、t=min{1/3,1/1}=1/3,故 s=(−1/3,0)T。预测下降为 t∥g∥2−21t2gTBg=1/3−21⋅91⋅2=2/9。Cauchy 界保证 21∥g∥min{Δ,∥g∥/Cβ}=1/6,而确实 2/9>1/6。
快速检查
(对 ∣s∣≤1 上的 m(s)=−s2/2,检查 s=0、λ=0 的证书并解释失败原因。)
解答
在 s=0、λ=0 时,驻点条件为 (B+0)⋅0=0=−g,互补条件也成立,但 B+λ=−1 不是半正定的,所以证书不完整。事实上 m(±1)=−1/2<0=m(0):零是最大点,而不是最小点。
快速检查
(若 L=2、β=1、η1=1/2、∥g∥≥1,求证明中足以保证接受的半径阈值。)
在证明的接受阈值中取 ε=1。
解答
这里 Cβ=2、C=(L+β)/2=3/2。取 ε=1,阈值为 min{ε/Cβ,(1−η1)ε/(2C)}=min{1/2,(1/2)/3}=1/6。在所列假设下,任何不大于 1/6 的正半径都给出 ∣1−ρ∣≤1/2,从而 ρ≥1/2。