方向和距离回答的是不同问题。若 gTp<0,沿 p 移动一小段便能降低目标值。然而,几乎没有位移的步骤可能浪费一个有用方向;走得太远,又可能穿过谷底而爬上另一边。强 Wolfe 条件同时要求足够下降和适当小的方向斜率。本节在明确假设下构造能找到这种步长的搜索,也说明为什么不断把步长乘上一个小于一的常数并不足够。
这个构造只用一条射线上的函数值和方向导数,不要求目标函数凸、不要求 Hessian,也不要求射线上存在精确最小点。
把搜索化为单变量问题
固定 x∈Rn 和满足 ∇f(x)Tp<0 的方向 p。定义
ϕ(α)=f(x+αp),ϕ′(α)=∇f(x+αp)Tp,d=−ϕ′(0)>0.
在精确搜索的讨论中,一直假设 ϕ 在 [0,∞) 上连续可微,并有有限下界 F。零点处的导数按右导数理解。通常的连续可微多变量目标函数,在射线上便给出这种正则性。选定常数 0<c1<c2<1,记
A(α)=ϕ(0)−c1dα,ψ(α)=ϕ(α)−A(α).
正步长 α 称为可接受,是指
ϕ(α)≤A(α),∣ϕ′(α)∣≤c2d.
第一式是 Armijo 下降条件。因为 A(α)<ϕ(0),接受步长必定降低目标值。第二式同时限制正、负斜率:即使目标值已大幅下降,过大的正斜率仍不合格。因此“步长太小”或“步长太大”只是非正式说法,真正的判断依据是函数值和斜率。
概念视角分析
减去要求的下降量
残差 ψ 把 Armijo 化为 ψ(α)≤0,而 ψ′(α)=ϕ′(α)+c1d。起初 ψ(0)=0,且 ψ′(0)=−(1−c1)d<0,所以 ψ 在零点右侧立即变负。当 ϕ 有下界时,正的倾斜项 c1dα 最终迫使 ψ 向上。这个残差同时解释存在性和括区证明,却不是外层最优化方法的新目标函数。
存在一整段可接受步长
在上述对 ϕ、c1、c2 的假设下,可接受步长的集合包含一个由正数组成的非空开区间。
由于 ψ(α)≥F−ϕ(0)+c1dα,可选 R>0 使 ψ(R)>0。连续函数 ψ 在 [0,R] 上取到最小值。因为 ψ′(0)<0,这个最小值为负。两个端点都不可能取到此负最小值,故存在内点 0<t<R 使 ψ′(t)=0。于是
ψ(t)<0,ϕ′(t)=−c1d,∣ϕ′(t)∣=c1d<c2d.两个接受不等式在 t 都严格成立。连续性因此给出一个包含 t 的开区间,其中每个步长都为正且可接受。
这比只证明存在一个孤立解更强,但尚未告诉我们应计算哪些试点才能找到该区间。
射线上未必有最小点。例如 ϕ(α)=e−α 的下确界零,只在 α→∞ 时逼近,且 d=1。可是取 c1=0.1、c2=0.5,有限步长 α=1 满足 e−1<0.9=A(1) 和 ∣ϕ′(1)∣=e−1<0.5,所以可接受。不精确线搜索解的是接受条件问题,并非精确最小化问题。
括区本身带有方向
括区是一对相异的非负端点 a,b。端点 a 是保留的合格下降点,b 则界定仍待搜索的区域。它们满足三个不变条件:
- ψ(a)≤0 且 ∣ϕ′(a)∣>c2d:保留端点通过 Armijo,尚未通过强曲率条件。
- ϕ′(a)(b−a)<0:导数所指的下降方向朝向区间内部。
- ψ(b)>0 或 ϕ(b)≥ϕ(a):另一端点未通过 Armijo,或函数值没有比保留值更低。
有些算法把 a 称为“低端点”,这是按它的角色和保留值命名,并不表示其坐标较小。完全可能有 a>b。此时条件 2 要求 ϕ′(a)>0,所以从 a 向 b 移动,在起初会降低目标值。若只把端点按大小排序,却丢掉其角色,便可能破坏算法。
初始化时允许 a=0:此时 ψ(0)=0,而 ∣ϕ′(0)∣=d>c2d。零点本身不是已接受的正步长。进入缩放搜索后,这些不变条件描述的是已取得的信息,并不是说两个端点都满足 Wolfe。
扩张:取得括区或步长
选初始试点 t0>0 和扩张因子 γ>1。从 a=0、t=t0 开始,依照下列顺序重复。
- 计算 ϕ(t)。若 ψ(t)>0 或 ϕ(t)≥ϕ(a),以 a 为保留端点、b=t 为另一端点,进入缩放搜索。
- 否则计算 ϕ′(t)。若 ∣ϕ′(t)∣≤c2d,返回 t。
- 若 ϕ′(t)≥0,以 a=t 为新保留端点,并以原先的保留端点为 b,进入缩放搜索。
- 否则令 a=t、t=γt,继续扩张。
在步骤 1,保留端点的导数为负,且大小超过 c2d:零点如此,而每次继续扩张后仍如此。新另一端点在其右侧,所以全部括区不变条件成立。在步骤 3,新保留端点通过 Armijo,且函数值严格低于原先保留值。因为它未通过曲率测试,其非负导数其实大于 c2d。另一端点在其左侧,且函数值较大,故全部不变条件仍成立,只是方向反转。
如果永远没有返回步长或括区,试点便是 ti=γit0→∞,而每点都通过 Armijo。于是
F≤ϕ(ti)≤ϕ(0)−c1dti⟶−∞,
矛盾。因此扩张经有限次试验便结束。事实上,任何超过 (ϕ(0)−F)/(c1d) 的试点都必定未通过 Armijo。算法不需要知道 F,也能使用这个证明。不过,若固定步长上限,定理便改变了,因为试点可能永远到不了证明所需的范围。
缩放:缩短区间并保留其意义
从满足三个不变条件的端点出发,取中点 t=(a+b)/2,采用以下规则。
- 若 ψ(t)>0 或 ϕ(t)≥ϕ(a),令 b=t,重新取试点。
- 否则,若 ∣ϕ′(t)∣≤c2d,返回 t。
- 否则,若 ϕ′(t)(b−a)≥0,先把 b 设为旧的 a,再令 a=t。若该乘积为负,则保留 b,只令 a=t。继续搜索。
只有函数值测试通过后,才需要计算 t 处的导数。步骤 3 的乘积使用本次试验开始时的端点。保留一份旧 a,便能使赋值次序清楚。每次未成功的试验,都把区间换成其中一半。
先检查步骤 1 如何保留不变条件。原来的 a 不变;新的 b=t 仍在同一方向,而拒绝测试正好给出条件 3。再考虑函数值合格、曲率不合格的情形。此时 ψ(t)≤0、ϕ(t)<ϕ(a),且 ∣ϕ′(t)∣>c2d。如果 ϕ′(t)(b−a)<0,新保留端点可以继续使用旧 b。该端点仍未通过 Armijo,或其值至少等于旧保留值,因而严格高于新值。如果 ϕ′(t)(b−a)>0,把 b 换成旧 a 便反转区间方向,同时另一端点仍有严格较大的值。曲率失败时导数不为零,因此乘积测试不会出现有歧义的零值。两种更新后,三个不变条件都得以保留。
定理 6.2.5
(精确算术下的有限步强 Wolfe 搜索)
设 ϕ∈C1([0,∞)) 有下界,ϕ′(0)<0,且 0<c1<c2<1。以 t0>0、γ>1 作几何扩张,并在需要时使用上述中点缩放规则,则经有限次试验便返回同时满足两个强 Wolfe 不等式的正步长。本叙述中的全部比较和计算均为精确。
扩张的有限性已证。对缩放,反设有无限多次被拒绝的试验。不分端点角色的闭区间彼此套叠,长度因不断折半而趋零。它们有共同极限点 q,两个带角色的端点都趋于 q。由条件 1 及连续性,
∣ϕ′(q)∣≥c2d>0.因为 c2>c1,在 q 的某邻域上,ϕ′ 和 ψ′=ϕ′+c1d 有相同的固定非零符号。具体来说,若 ϕ′(q)≤−c2d,连续性保证附近 ϕ′<−c1d。若 ϕ′(q)≥c2d,则附近 ϕ′>0,故 ψ′>0 亦成立。
最终整个括区都落在此邻域内。条件 2 说从 a 向 b 移动,是逆着这个共同导数符号的方向。因此两函数在此移动中都严格下降,给出
ϕ(b)<ϕ(a),ψ(b)<ψ(a)≤0.条件 3 的两个选项都不成立,矛盾。故缩放必在有限步内终止。最后,返回的中点必为正:区间非退化、两端点非负,而至少一点为正。
证明透视
为什么区间缩小不是整个证明
折半只用来证明一件事:两端点收敛到同一点 q。它本身不使 q 或任何有限次试点可接受;其余一切都来自不变条件。条件 1 与 ϕ′ 的连续性使 ∣ϕ′(q)∣≥c2d,远离零。差距 c2>c1 只在一侧需要:当 ϕ′(q)≤−c2d,它使 q 附近 ψ′=ϕ′+c1d 为负;当 ϕ′(q)≥c2d,正项 c1d 已给出 ψ′>0。关键一步是条件 2:它使从 a 到 b 的移动逆着这个共同符号,于是 b 会在两种意义上同时优于 a。条件 3 正好禁止这种情况,矛盾便排除了无限拒绝序列。若 c1=c2,论证会卡在 ϕ′(q)=−c1d 的极限处,那里 ψ′(q)=0,无法确定符号。
同一证明也容许有保障的插值试点。固定 0<η≤1/2,并要求
min(a,b)+η∣b−a∣≤t≤max(a,b)−η∣b−a∣.
每次未成功的更新后,区间长度至多为 (1−η)∣b−a∣。不变条件证明不变,而套叠区间仍缩至一点。三次或二次插值可以提出 t,但此定理不用插值模型的准确度;保证进展的是内部保障。
导数为 Lipschitz 时的定量界
连续可微已足以保证有限终止,却没有给出导数变化速度的数值界。
另外假设 ϕ′ 在最初的缩放区间上为 Lϕ-Lipschitz,其中 Lϕ>0。该区间内每个满足三个不变条件的括区,宽度都满足
w=∣b−a∣≥Lϕ(c2−c1)d.
若宽度更小且 ϕ′(a)<−c2d,区间内每个导数都小于 −c1d。于是 ϕ 和 ψ 都从 a 向右侧的 b 下降,违反条件 3。若 ϕ′(a)>c2d,区间内每个导数都大于 c1d>0;此时 b<a,两函数从 a 向左侧的 b 移动也都下降,得到相同矛盾。
经过 N 次未成功的中点试验,宽度应为 2−Nw0。因此只要
2−Nw0<Lϕ(c2−c1)d,
便不可能连续出现 N 次未成功试验。这是试验次数的判据,不是预先设定的停止规则。有保障插值时,把 2−N 换成 (1−η)N 即可。较小的保障量或较小的差距 c2−c1 都使此界变弱。
对已接受步长,若从零到该步长的整段上也有导数 Lipschitz 界,则
(1−c2)d≤ϕ′(α)−ϕ′(0)≤Lϕα,α≥Lϕ(1−c2)d.
这个步长下界需要整段上的导数 Lipschitz 常数;只在较后的缩放括区上已知的常数,未必足够。若 ∇f 在相关多变量线段上为 L-Lipschitz,可取 Lϕ=L∥p∥2。参数步长 α 的数值取决于 p 的缩放;目标函数实际感受到的是位移 αp。
逐步算例
设 ϕ(α)=(1−α)2、c1=1/10、c2=1/5,故 d=2。Armijo 的精确正步长范围为 0<α≤9/5,强曲率条件的范围则为 4/5≤α≤6/5,交集就是后者。
取首个试点 3/2。其值 1/4<7/10=A(3/2),但导数 1>2/5,所以扩张转入缩放,带着 a=3/2、b=0。在 t=3/4,函数值 1/16 低于 1/4 且通过 Armijo,但导数 −1/2 未通过曲率。由于 (−1/2)(0−3/2)>0,把 b 换成旧 a=3/2,再令 a=3/4。下一中点是 9/8,其值 1/64<31/40=A(9/8),也有 1/64<1/16=ϕ(3/4),故两个函数值测试都通过。导数 1/4 位于 [−2/5,2/5] 内,故接受。接受步长不是精确最小点 1,也无须是。
取 ϕ(α)=α4−2α2−α。此时 ϕ(0)=0、d=1,而 ϕ′′(α)=12α2−4 在零附近为负。函数虽非凸,在射线上仍有下界。取 c1=1/10、c2=1/2 和首个试点 2。因为 ϕ(2)=6>A(2)=−1/5,以 (a,b)=(0,2) 开始缩放。
中点 1 的值为 −2,导数为 −1。函数值通过两个测试,但曲率不合格,故更新为 (a,b)=(1,2)。下一中点 3/2 的值为 −15/16,高于保留值 −2;无须导数便可拒绝,令 b=3/2。在 5/4,值 −495/256 仍高于 −2,故令 b=5/4。到 9/8,值为 −8415/4096<−2,Armijo 成立,导数为 25/128,绝对值小于 1/2,故接受 9/8。不变条件和终止证明都没有用凸性。
失败情形与计算机能证明的事
反例模式
回溯可能错过所有可接受步长
对 ϕ(α)=(1−α)2,取 c1=1/10、c2=1/2。强曲率要求 1/2≤α≤3/2。从 α=1/10 开始不断折半,只会产生小于 1/2 的步长。这些小步全通过 Armijo,却全不通过强曲率。因此“任何一项强 Wolfe 条件失败便折半”的循环,在精确算术中会永远运行。斜率仍太负时需要扩张;缩短步长并不是对所有失败都适用的反应。
各项假设也有具体作用。没有射线下界时,ϕ(α)=−α 在每个正步长都通过 Armijo,但处处 ∣ϕ′∣=1>c2。没有下降性时,ϕ(α)=α2 在零点没有可接受正步长:Armijo 右侧为零,左侧却为正。人为步长上限甚至能使光滑强凸射线上的搜索失败:对 ϕ(α)=(α−10)2,取 c1=0.01、c2=0.1,强曲率要求 9≤α≤11,而上限 α≤1 排除了全部可接受步长。
精确比较也是实质假设。浮点数中,两端点成为相邻可表示数时,中点可能舍入为端点。区间便不再缩小,精确定理不再适用于该循环。
计算次数用尽、目标值无效、导数计算失败或此种停滞,都应在未验证接受条件时明确报告搜索失败。只看区间宽度容差,并不是强 Wolfe 证书。同样,任意小的参数步长,可能在数值上给出完全不变的点 x+αp=x。
若有严格的计算误差界,可以把它们纳入接受测试。设计算值 ϕα,ϕ0,sα,s0 的绝对误差分别不超过 eα,e0,δα,δ0。真实 Armijo 的一个充分证书是
ϕα−ϕ0−c1αs0+eα+e0+c1αδ0≤0.
真实强曲率的一个充分证书是
∣sα∣+δα≤c2(∣s0∣−δ0),
并以 s0+δ0<0 证明下降性。这些公式来自三角不等式,可能较保守。它们没有证明整个有限精度实现会终止;从经验估算的误差,也不会自动变成严格误差界。
外层方法为什么需要这种搜索
令 s=αp、y=∇f(x+αp)−∇f(x)。任何已接受步长都满足
sTy=α(ϕ′(α)−ϕ′(0))≥α(1−c2)d>0.
这提供了前文 BFGS 正定更新所需的正曲率对。单就此不等式,弱 Wolfe 已足够;强 Wolfe 额外限制可能越过谷底后的正斜率。如果搜索失败而随意返回后备步长,便不能不作检查,就对该步长套用此曲率证明。
在 Wolfe 角度定理的 Lipschitz 梯度及下界假设下,强 Wolfe 提供该定理所用的弱 Wolfe 条件,因此得到同一个加权梯度级数。要推出梯度范数趋零,仍须有统一正的方向角下界,或其他适当的外层方法分析。每次线搜索都在有限步内成功,不代表整个 BFGS 或非线性共轭梯度序列收敛,也不代表非凸驻点是全局最小点。
习题
快速检查
(对 ϕ(α)=(1−α)2,推导任意 0<c1<c2<1 下的完整正接受区间,并说明何时上端点由 Armijo 而非曲率决定。)
解答
Armijo 化为 1−2α+α2≤1−2c1α,即 0<α≤2(1−c1)。强曲率化为 ∣2α−2∣≤2c2,即 1−c2≤α≤1+c2。交集是 [1−c2,min{1+c2,2(1−c1)}]。因 c1<c2<1 推出 1−c2<2(1−c1),此交集非空。当 2c1+c2>1 时,Armijo 给出较小上端点;等号时两限制在同一上端点同时取等。
快速检查
(对 ϕ(α)=e−α,取 c1=0.1、c2=0.5,以 t0=1/4、γ=2 开始扩张。列出直到接受为止的试点。)
解答
初始斜率为 −1。在 1/4 和 1/2,值约为 0.7788 和 0.6065,低于 Armijo 界 0.975 和 0.95,也低于各自原先的保留值。斜率大小仍超过 0.5,所以扩张。到 1,函数值和斜率大小都约为 0.3679,两条件通过。算法接受步长,整个过程没有用括区夹住任何有限精确最小点。
快速检查
(某缩放括区宽度为 w0=4,d=1、c1=0.1、c2=0.5,导数 Lipschitz 常数为 Lϕ=2。定量证明排除了连续多少次未成功的中点试验?这个数字能否在计算前就证明某一特定试点合格?)
解答
不容许的宽度阈值为 (0.5−0.1)/2=0.2。五次未成功试验会留下 4/32=0.125<0.2 的宽度,与保留的不变条件矛盾,故必在首五次中点计算内接受。此界不排除四次失败,因为 4/16=0.25。证明约束的是有效的精确搜索,不能在未检查函数值和导数前就把试点标成合格。
快速检查
(假设二次插值建议每次都严格在括区内,但依次的宽度因子为 1−2−j−2,j=0,1,…。说明为什么严格内点本身不能证明宽度趋零,并比较固定保障的情形。)
解答
记 uj=2−j−2。对有限多个位于 [0,1] 的因子,归纳给出 j∏(1−uj)≥1−j∑uj。此处完整级数和为 1/2,所以每个有限乘积至少为 1/2,递减乘积有正极限。假设的宽度因子因此至少留下原宽度的一半。固定 η>0 则给出 wN≤(1−η)Nw0→0。这指出无保障证明所缺的一个推论,并不是说每种插值搜索都会产生这组因子。
快速检查
(计算所得 Armijo 残差为 −10−6,而 eα=e0=2⋅10−7、c1αδ0=10−7。误差感知测试能否证明 Armijo?若 ∣sα∣=0.50、s0=−1、c2=0.5,两个导数误差都为 0.01,能否证明下降性及强曲率?)
解答
Armijo 残差的总误差界为 5⋅10−7,因此经认证的残差上界为 −5⋅10−7<0,能证明 Armijo。由 −1+0.01<0 可证明下降性。曲率充分条件左侧为 0.51,右侧为 0.5(1−0.01)=0.495,所以不能证明强曲率。此充分证书未通过,本身不代表真实强曲率不等式一定不成立。