动机
选择下降方向只表示充分短的移动会改善目标值;它没有告诉我们应走多远、实际搜索会否找到步长,或反复移动有什么结论。线搜索把局部信息转成算法:Armijo 测试实际下降量,Wolfe 再加入斜率条件,防止步长过短。这些测试本身并非全局最优证书;收敛结果还需要光滑性、目标下界及方向的假设。
牛顿(Newton)法用曲率选择方向,在非退化最小点附近可以收敛得快得多。但远离该点时 Hessian 可能奇异或不定,牛顿方向不一定下降。先证一般搜索的保证,再在更强的独立假设下证明局部牛顿收敛率。
定义
设 f:Rn→R 连续可微。在 xk 令 gk=∇f(xk),选 gkTpk<0 的方向,并令 xk+1=xk+αkpk。
定义 6.1.1
(Armijo、弱 Wolfe 与强 Wolfe 条件)
设 0<c1<c2<1,pk 是下降方向。若正步长 αk 满足
f(xk+αkpk)≤f(xk)+c1αkgkTpk,∇f(xk+αkpk)Tpk≥c2gkTpk,则称它满足弱 Wolfe 条件。单独第一式是 Armijo 充分下降条件,第二式是曲率条件。强 Wolfe 条件保留 Armijo,并把第二式换成 ∣∇f(xk+αkpk)Tpk∣≤c2∣gkTpk∣。Armijo 回溯法从 αˉ>0 出发,反复把试探步长乘以 β∈(0,1),直到 Armijo 成立。
强 Wolfe 蕴含弱 Wolfe,限制更严。回溯法不保证 Wolfe 曲率条件;它用另一种机制防止步长过小,见下文第一个证明。
对 gk=0 及下降方向 pk,角度因子为 cosθk=−gkTpk/(∥gk∥∥pk∥)>0。
它度量方向与负梯度的对齐程度。缩放 pk 会改变数值步长,却不改变角度;pk=−gk 时因子等于一。
定理/命题
定理 6.1.3
(Armijo 回溯的梯度收敛界)
设 f 的梯度以 L 为 Lipschitz 常数,且 f≥finf。使用 pk=−gk 和固定 αˉ>0、β∈(0,1)、c1∈(0,1) 的 Armijo 回溯。每次非驻点搜索均终止,接受步长有共同正下界,且
0≤k<Tmin∥gk∥2≤c1αminTf(x0)−finf.因此除非算法在驻点停止,否则梯度范数趋于零。
Wolfe 条件只有在合格步长存在时才有用;下一个引理对任何下降方向解决这个问题。
设 f 连续可微,p 是 x 处的下降方向,且 α↦f(x+αp) 在 (0,∞) 上有下界。则对每组 0<c1<c2<1,都存在满足弱 Wolfe 条件的步长 α>0。
有了这样的步长,便可把它们强制的下降量相加。
设 f 有下界且梯度为 L-Lipschitz。若每个 pk 是下降方向,每步满足弱 Wolfe,则
k=0∑∞cos2θk∥gk∥2<∞.若另外有共同正下界 cosθk≥γ>0,则 ∥gk∥→0。
在非退化最小点附近,曲率给出强得多的局部结论。
设 f 在 x∗ 附近二次连续可微,∇f(x∗)=0,H∗:=∇2f(x∗) 正定,而 Hessian H(x)=∇2f(x) 在 x∗ 的某个凸邻域上以常数 M 满足 Lipschitz 条件。则存在 ρ>0 及 K>0,使得对每个满足 ∥x0−x∗∥<ρ 的 x0,完整牛顿迭代 xk+1=xk−H(xk)−1∇f(xk) 都有定义、收敛到 x∗,并满足
∥xk+1−x∗∥≤2KM∥xk−x∗∥2.
对梯度下降法,强凸性把 Armijo 结果从驻定提升为目标值的收敛率。
在 Armijo 回溯定理的假设下,再设 f 为 μ-强凸且有最小点 x∗。则
f(xk+1)−f(x∗)≤(1−2μc1αmin)[f(xk)−f(x∗)],其中系数属于 [0,1),且 xk→x∗。
驻点可以是极大点或鞍点。这些定理没有断言迭代点收敛,也没有断言达到全局最小值。角度假设对上述梯度结论重要,因下降方向可以逐渐接近与梯度垂直。
证明思路
回溯及一致步长下界
下降引理给 f(x−αg)≤f(x)−α(1−Lα/2)∥g∥2。所以 α≤2(1−c1)/L 时 Armijo 成立,回溯必定到达。若初始步长不被接受,接受值大于阈值的 β 倍;若初始值获接受,步长等于 αˉ。因此共同下界可取
αmin=min{αˉ, 2β(1−c1)/L}>0.Armijo 下降量令 c1αmink=0∑T−1∥gk∥2≤f(x0)−f(xT)≤f(x0)−finf。除以 T 得最小梯度界。相同的平方和有限亦证明各梯度范数趋零。这是有明确复杂度的驻定保证,并未声称迭代点接近唯一点。
Wolfe 步长的存在与后果
证明
(对 Armijo 差距使用 Rolle 定理)
对固定下降方向,令 ϕ(α)=f(x+αp)、ψ(α)=ϕ(α)−ϕ(0)−c1αϕ′(0)。因 ψ(0)=0、ψ′(0)<0,充分小的正步长有 ψ<0。若沿射线的 f 有下界,−c1αϕ′(0) 趋向正无限,使 ψ 最终为正。在第一个正零点之前 Armijo 成立;在零与该首个零点之间使用 Rolle 定理,得到一个内点使 ψ′=0。该处 ϕ′=c1ϕ′(0)>c2ϕ′(0),因初始斜率为负,故弱 Wolfe 成立。这证明存在,但不保证单纯 Armijo 回溯会找到它。
对已接受的步长,弱 Wolfe 及 Lipschitz 条件给出
(1−c2)(−gkTpk)≤[∇f(xk+αkpk)−gk]Tpk≤Lαk∥pk∥2.将步长下界代入 Armijo 得
f(xk)−f(xk+1)≥Lc1(1−c2)∥pk∥2(gkTpk)2=Lc1(1−c2)cos2θk∥gk∥2.从 k=0 到 T−1 求和,cos2θk∥gk∥2 的部分和不超过 L[f(x0)−inff]/(c1(1−c2)),这就证明了 Wolfe 角度定理。若 cosθk≥γ>0,则 γ2∑∥gk∥2<∞,故 ∥gk∥→0;没有此下界时,只能控制加权级数。
证明透视
每个 Wolfe 条件各做一件事
论证把步长转换为下降量,两条 Wolfe 不等式各提供一半。曲率条件先用上:配合 Lipschitz 梯度,它表示除非步长至少为 (1−c2)∣gkTpk∣/(L∥pk∥2),否则斜率不能改变 (1−c2)∣gkTpk∣,因此接受的步长不能任意短。Armijo 随后用上:它把任何接受的步长转为至少 c1αk∣gkTpk∣ 的下降量。关键一步是把两个界相乘,得到 (gkTpk)2/∥pk∥2;这个量在 pk 缩放时不变,所以结论以角度而不是步长表述。f 的下界使下降量的伸缩和有限,论证由此闭合。若允许 c2=1,因子 1−c2 为零,步长下界便失去内容;若 f 无下界,总和可以发散,本节稍后的反例正说明这一点。
牛顿法的局部二次收敛
在牛顿定理的假设下进行。连续性给出以 x∗ 为中心的球,使其上 H(x) 可逆且 ∥H(x)−1∥≤K;本节末的曲率论证给出明确的选择 K=2/m。对完整牛顿步 x+=x−H(x)−1∇f(x),令 e=x−x∗,则 x+−x∗=H(x)−1[H(x)e−∇f(x)]。由于 ∇f(x)=∫01H(x∗+te)edt,且 ∥H(x)−H(x∗+te)∥≤M(1−t)∥e∥,
H(x)e−∇f(x)=∫01[H(x)−H(x∗+te)]edt,∥x+−x∗∥≤2KM∥e∥2.选取不大于该球半径、且满足 KMρ/2<1 的 ρ。则 ∥e∥<ρ 给出 ∥x+−x∗∥≤(KMρ/2)∥e∥<∥e∥,下一个迭代点仍在球内。归纳即得收敛及每步的二次估计。
证明透视
平方从哪里来
整个证明建立在一个改写之上:利用 ∇f(x∗)=0,把新误差写成 H(x)−1[H(x)e−∇f(x)],即逆 Hessian 作用在线性化的偏差上。∇f(x) 的积分形式把这个偏差化为 Hessian 差的平均,而 Lipschitz 界 M(1−t)∥e∥ 积分后得到 M∥e∥/2;一个 ∥e∥ 来自偏差,另一个来自它所作用的向量。H∗ 的正定性只通过连续性起作用,在一个球内给出可逆性及 ∥H(x)−1∥≤K。选取 KMρ/2<1 使误差收缩,保证每个迭代点都留在球内,归纳法才能完成。
H∗ 正定也令 x∗ 为严格局部最小点。此结果只涵盖充分接近 x∗ 的完整步长,不是任意起点、奇异 Hessian 或任意阻尼步长的全局定理。
概念视角算法
同一个牛顿步的两种描述
步长 p=−H(x)−1g 是二次模型 m(p)=f(x)+gTp+21pTH(x)p 的驻点,因为 ∇m(p)=g+H(x)p。它同时是对方程 ∇f=0 做牛顿求根的一步,即把 ∇f(x+p) 线性化为 g+H(x)p。上面的局部证明只用到第二种描述:它从不比较函数值,因此在 H(x∗) 仅仅可逆的鞍点或最大点附近同样成立。模型描述补上了求根观点所缺的一点:当 H(x) 正定时,p 极小化 m,并且在 g=0 时是下降方向。
完整牛顿步终会被接受
在相同局部假设下,H(x) 保持一致正定。令 p=−H(x)−1g;Taylor 展开得到 f(x+p)=f(x)+gTp+21pTH(x)p+O(∥p∥3)。因 gTp=−pTH(x)p,正的二次量在充分接近解时支配三次余项,所以 0<c1<1/2 的 Armijo 测试接受 α=1。因此若某阻尼算法已进入该邻域,便可恢复完整牛顿法的二次收敛;如何进入邻域是另外的问题。
强凸下的收敛率
前面的 Armijo 定理没有假设凸性,只证明驻定。强凸性给出更强的目标值结论。
在强凸命题的假设下,于 x 处使用强凸不等式并代入 x∗,得
f(x∗)≥f(x)+gT(x∗−x)+2μ∥x∗−x∥2≥f(x)−2μ∥g∥2.第二步把二次式对所有位移最小化。因此 ∥g∥2≥2μ[f(x)−f(x∗)]。Armijo 与一致步长下界给出 f(xk+1)≤f(xk)−c1αmin∥gk∥2,两边减去 f(x∗) 即得命题中的不等式。在这些假设下系数非负:可微的 L-光滑强凸函数有 μ≤L,而 2μc1αmin≤4βc1(1−c1)μ/L<1。反复使用不等式,目标差至少以几何速度下降。强凸性亦给 μ∥xk−x∗∥2/2≤f(xk)−f(x∗),所以迭代点收敛到唯一最小点。
此界依赖常数与搜索参数,并未声称最锐利。
下降方向也可能进展很小
考虑 f(x,y)=21(x2+y2),选取近乎垂直于梯度的方向。在非零 xk,取与 gk 正交的单位向量 uk,令 pk=−εkgk+uk。只要 εk>0,便有 gkTpk=−εk∥gk∥2<0;但当 εk→0,角度余弦可以趋零。因此方向虽符合下降定义,沿梯度方向的进展却可能很小。除非证得一致角度界,定理只能给加权结论。
目标下界也有具体作用。
反例模式
没有下界时梯度不必趋于零
只从 Armijo 回溯定理中删去下界假设。函数 f(x)=x 在 R 上的梯度处处为 1,对任何 L>0 都是 L-Lipschitz。取 pk=−gk=−1,因 c1<1,Armijo 测试 xk−α≤xk−c1α 对每个 α>0 都成立,所以回溯立即接受 αˉ,得 xk=x0−kαˉ。每步使 f 下降 αˉ,但对每个 k 都有 ∥gk∥=1,而且根本没有驻点。总下降量 f(x0)−f(xT)=Tαˉ 无界,所以证明中的求和步骤没有有限量可以除以 T。恢复 f≥finf 后,总下降量不超过 f(x0)−finf,定理便成立。
若有下界的目标存在聚点且梯度连续,梯度收敛则令每个这样的聚点驻定;但聚点存在本身需要紧致性或有界性论证,并非自动成立。
局部牛顿曲率如何控制步长
牛顿证明使用的逆矩阵界可直接由正定性得到。设 H∗ 的最小特征值为 m>0。由连续性,在充分接近 x∗ 时有 ∥H(x)−H∗∥≤m/2。对任意向量 v,
vTH(x)v≥vTH∗v−∥H(x)−H∗∥∥v∥2≥2m∥v∥2.
因此 H(x) 可逆且 ∥H(x)−1∥≤2/m。相同估计亦证明此邻域中非零牛顿步满足 gTp=−pTH(x)p<0,即为下降方向。在邻域之外,H∗ 处的连续性不能给出这个界。算法可把不定 Hessian 换成正定近似以恢复下降,但修改及其对局部收敛率的影响必须另作分析。
对完整步的 Armijo 证明,Hessian 的 Lipschitz 连续性给出 Taylor 余项绝对值上界 M∥p∥3/6。若 H(x)⪰(m/2)I,则 pTH(x)p≥(m/2)∥p∥2。当 c1<1/2、p 够小,正的余额 (1/2−c1)pTH(x)p 便支配三次余项。明确比较两项才证明测试,单说牛顿法局部准确不能指出 c1 的限制。
搜索参数也反映取舍。较小的回溯因子可能把步长缩到远低于可接受阈值,因而削弱 αmin 下界,尽管仍保证终止。较小 c1 对每步下降要求较低,接近一则要求更严;证明适用于区间内任何固定值,并不指出所有计算问题的最佳参数。
以 ∥gk∥ 停止时亦须考虑尺度。把 f 乘以正常数不改变最小点,却会缩放梯度,同一数值容差因此有不同含义。若已知强凸常数 μ,可用 f(x)−f(x∗)≤∥g∥2/(2μ) 把梯度容差转成目标差证书;没有此结构时,小梯度只表示近似驻定。
验证 μ≤L:强凸性给出 (∇f(x)−∇f(y))T(x−y)≥μ∥x−y∥2。Cauchy–Schwarz 及 Lipschitz 连续性则以上界 L∥x−y∥2 控制同一内积。对不同点除以距离平方便得结论。两个假设均有作用,两个常数都不是算法步长。若只在一个局部区域知道这些界,就只能在迭代点确实停留于该区域时使用相应推导,不能直接套用全局定理。
例题详解
f(x)=x2,在 x=1 取 p=−2、c1=1/2、初始步长一及 β=1/2。α=1 时新值为一,Armijo 右端为 −1,故拒绝。α=1/2 时两端均为零,接受并到达最小点;不等式容许相等。
沿用上述 f,x,p,取 c1=0.1、c2=0.9。α=1/2 时新点为零,新方向导数为零。Armijo 成立,且 0≥−3.6,故弱 Wolfe 成立。曲率测试排除任意小步长;此处它要求 α≥0.05。
对 f(x)=21a(x−b)2(a>0),梯度 a(x−b)、Hessian a,所以 p=−(x−b),完整步长一次便到 b。Hessian 的 Lipschitz 常数为零,二次误差界右端亦为零。一般非线性目标并不因此能一步求解。
常见错误
常见错误
(把 Armijo 当作 Wolfe 测试)
Armijo 只控制下降,不控制曲率。对 f(x)=x2,在 x=1 取 p=−2、c1=0.1,极小的步长 α=0.01 通过 Armijo,因为 f(0.98)=0.9604≤0.996;但它不满足 c2=0.9 的曲率条件,该条件要求 α≥0.05。同样,弱 Wolfe 步长未必满足强 Wolfe,后者还限制为正的新斜率。
下降方向只保证充分小的步长使函数下降。对 f(x)=x2,在 x=1 取 p=−2,步长 α=1 落在 −1,没有下降;每个 α>1 更会使 f 增大。反过来,最后得到小梯度也不能证明非凸函数的全局最优:该点可能靠近极大点或鞍点。
牛顿公式要求 Hessian 可逆,不定 Hessian 可以把牛顿方向变成上升方向,下面练习中的 f(x)=−x2 正是如此。局部二次收敛也不保证远处的起点能进入局部邻域。
总结
回溯与下降引理给梯度下降的一致正步长下界。Wolfe 斜率条件给出受方向角度加权的下降估计。牛顿法的局部二次收敛依赖解处正定且可逆的 Hessian 及其 Lipschitz 变化;阻尼及全局收敛需要额外分析。
练习
快速检查
(f(x)=x2,在 x=1 取 p=−2、c1=1/4。求 Armijo 步长范围。)
把 Armijo 不等式两边写成 α 的函数。
解答 · 答案
Armijo 要求 (1−2α)2≤1−α,等价于 α(4α−3)≤0,故正步长范围为 0<α≤3/4。
快速检查
(在 Wolfe 角度定理下,若 cosθk≥1/2,解释为何 ∥gk∥→0。)
把加权级数与 ∑∥gk∥2 比较。
解答 · 答案
定理给出 ∑cos2θk∥gk∥2<∞,角度下界使 41∑∥gk∥2<∞,所以各非负项趋于零。
快速检查
(求 f(x)=−x2 在 x=1 处的牛顿方向,并证明它不是下降方向。)
解答 · 答案
g=−2、H=−2,所以 p=−H−1g=−1。方向内积 gp=2>0,故为上升方向;该步到达驻定的最大点零。
快速检查
(对 f(x)=21x2+41x4 求完整牛顿更新,并证明误差至多为 2∣x∣3。)
解答 · 答案
梯度为 x+x3,Hessian 为 1+3x2,所以 x+=x−(x+x3)/(1+3x2)=2x3/(1+3x2)。最小点为零,∣x+∣≤2∣x∣3,比一般的二次界更强。