动机
正定 Hessian 的二次函数有唯一最小点,但维数大时直接解线性方程可能昂贵。共轭梯度法构造不会撤销先前方向进展的新方向;递推只需矩阵与向量相乘及少量存储,特别适合大型稀疏矩阵。其优美的有限步定理是假设精确运算的结论,不能误认为浮点实现总会在指定步数内精确停止。
非线性目标的 Hessian 随位置改变,固定二次模型不再准确。拟牛顿(quasi-Newton)法收集梯度改变以近似曲率。本节从割线及正定性要求推导 BFGS 公式,再分开有条件的全局收敛论证和局部超线性判据。单有更新公式并不保证任意线搜索、初始值和非线性问题都收敛。
定义
定义 7.1.1
(共轭梯度递推与 Krylov 空间)
设 A A A 对称正定(SPD),f ( x ) = 1 2 x T A x − b T x f(x)=\tfrac12x^TAx-b^Tx f ( x ) = 2 1 x T A x − b T x 。令 g k = A x k − b g_k=Ax_k-b g k = A x k − b ,使用递推
p 0 = − g 0 , α k = g k T g k p k T A p k , x k + 1 = x k + α k p k , g k + 1 = g k + α k A p k , p_0=-g_0,\quad
\alpha_k=\frac{g_k^Tg_k}{p_k^TAp_k},\quad
x_{k+1}=x_k+\alpha_kp_k,\quad
g_{k+1}=g_k+\alpha_kAp_k, p 0 = − g 0 , α k = p k T A p k g k T g k , x k + 1 = x k + α k p k , g k + 1 = g k + α k A p k , 若 g k + 1 ≠ 0 g_{k+1}\ne0 g k + 1 = 0 ,再令
β k + 1 = g k + 1 T g k + 1 g k T g k , p k + 1 = − g k + 1 + β k + 1 p k . \beta_{k+1}=\frac{g_{k+1}^Tg_{k+1}}{g_k^Tg_k},
\qquad p_{k+1}=-g_{k+1}+\beta_{k+1}p_k. β k + 1 = g k T g k g k + 1 T g k + 1 , p k + 1 = − g k + 1 + β k + 1 p k . 若初始或后续梯度为零便停止:目前点是唯一最小点。否则正定性保证所有分母为正。线性系统 A x = b Ax=b A x = b 的残差是 r k = b − A x k = − g k r_k=b-Ax_k=-g_k r k = b − A x k = − g k 。由 g 0 g_0 g 0 产生的 Krylov 空间为 K j = span { g 0 , A g 0 , … , A j − 1 g 0 } K_j=\operatorname{span}\{g_0,Ag_0,\ldots,A^{j-1}g_0\} K j = span { g 0 , A g 0 , … , A j − 1 g 0 } 。
对非线性函数,定义 s k = x k + 1 − x k s_k=x_{k+1}-x_k s k = x k + 1 − x k 、y k = ∇ f ( x k + 1 ) − ∇ f ( x k ) y_k=\nabla f(x_{k+1})-\nabla f(x_k) y k = ∇ f ( x k + 1 ) − ∇ f ( x k ) 。若 Hessian 近似 B k + 1 B_{k+1} B k + 1 满足 B k + 1 s k = y k B_{k+1}s_k=y_k B k + 1 s k = y k ,便满足割线方程;其逆 H k + 1 H_{k+1} H k + 1 满足 H k + 1 y k = s k H_{k+1}y_k=s_k H k + 1 y k = s k 。一对向量只决定矩阵在一个方向上的作用,所以更新规则须另外说明如何选择其余信息。
定理/命题
对正定 A A A ,上述递推要么提早在唯一最小点停止,要么产生互相正交的非零梯度及互相 A A A -共轭的方向。至多 n n n 步便到达 A − 1 b A^{-1}b A − 1 b 。停止前,x k x_k x k 在 x 0 + K k x_0+K_k x 0 + K k 上最小化 f f f 。
若 B B B 对称正定且 s T y > 0 s^Ty>0 s T y > 0 ,则
B + = B − B s s T B s T B s + y y T s T y B_+=B-\frac{Bss^TB}{s^TBs}+\frac{yy^T}{s^Ty} B + = B − s T B s B s s T B + s T y y y T 仍对称正定且满足 B + s = y B_+s=y B + s = y 。其逆为
H + = ( I − ρ s y T ) H ( I − ρ y s T ) + ρ s s T , H = B − 1 , ρ = ( s T y ) − 1 . H_+=(I-\rho sy^T)H(I-\rho ys^T)+\rho ss^T,
\quad H=B^{-1},\quad \rho=(s^Ty)^{-1}. H + = ( I − ρ s y T ) H ( I − ρ y s T ) + ρ s s T , H = B − 1 , ρ = ( s T y ) − 1 .
曲率条件是存在正定割线解的必要条件:若 B + B_+ B + 正定且 B + s = y B_+s=y B + s = y ,则 s T y = s T B + s > 0 s^Ty=s^TB_+s>0 s T y = s T B + s > 0 。它不只是避免分母为零。
证明思路
共轭梯度递推的推导
归纳假设当前梯度与之前的方向及梯度正交,而之前方向互相 A A A -共轭。由 p k = − g k + β k p k − 1 p_k=-g_k+\beta_kp_{k-1} p k = − g k + β k p k − 1 和正交性,g k T p k = − ∥ g k ∥ 2 g_k^Tp_k=-\|g_k\|^2 g k T p k = − ∥ g k ∥ 2 。故上面的 α k \alpha_k α k 是 f ( x k + α p k ) f(x_k+\alpha p_k) f ( x k + α p k ) 的精确最小步长,并有 g k + 1 T p k = 0 g_{k+1}^Tp_k=0 g k + 1 T p k = 0 。对 i < k i<k i < k ,共轭性给 g k + 1 T p i = g k T p i + α k p k T A p i = 0 g_{k+1}^Tp_i=g_k^Tp_i+\alpha_kp_k^TAp_i=0 g k + 1 T p i = g k T p i + α k p k T A p i = 0 。先前梯度在先前方向的张成空间中,故新梯度也与它们正交。
选择 p k + 1 p_{k+1} p k + 1 的系数使 p k + 1 T A p k = 0 p_{k+1}^TAp_k=0 p k + 1 T A p k = 0 。利用 A p k = ( g k + 1 − g k ) / α k Ap_k=(g_{k+1}-g_k)/\alpha_k A p k = ( g k + 1 − g k ) / α k 、梯度正交性,以及 α k p k T A p k = ∥ g k ∥ 2 \alpha_kp_k^TAp_k=\|g_k\|^2 α k p k T A p k = ∥ g k ∥ 2 ,得到 β k + 1 = ∥ g k + 1 ∥ 2 / ∥ g k ∥ 2 \beta_{k+1}=\|g_{k+1}\|^2/\|g_k\|^2 β k + 1 = ∥ g k + 1 ∥ 2 /∥ g k ∥ 2 。若 i < k i<k i < k ,A p i = ( g i + 1 − g i ) / α i Ap_i=(g_{i+1}-g_i)/\alpha_i A p i = ( g i + 1 − g i ) / α i 属于先前梯度的张成空间,所以 g k + 1 T A p i = 0 g_{k+1}^TAp_i=0 g k + 1 T A p i = 0 ;再用归纳共轭性得 p k + 1 T A p i = 0 p_{k+1}^TAp_i=0 p k + 1 T A p i = 0 。归纳完成。
非零共轭方向线性无关:对其线性关系取任一方向的 A A A -内积,即可分离其系数。维数限制使非零方向最多 n n n 个,故算法至多 n n n 步终止。递推亦令 p j ∈ K j + 1 p_j\in K_{j+1} p j ∈ K j + 1 ;停止前首 k k k 个独立方向张成 K k K_k K k 。新梯度与此空间正交,所以正定二次函数的一阶条件证明 x k x_k x k 在 x 0 + K k x_0+K_k x 0 + K k 上唯一最小。
证明透视
归纳法维持了什么 归纳同时维持两个不变性:新梯度与先前所有方向正交,而各方向两两 A A A -共轭。两者互相支撑。精确线搜索给出 g k + 1 ⊥ p k g_{k+1}\perp p_k g k + 1 ⊥ p k ,共轭性再通过 g k + 1 T p i = g k T p i + α k p k T A p i g_{k+1}^Tp_i=g_k^Tp_i+\alpha_kp_k^TAp_i g k + 1 T p i = g k T p i + α k p k T A p i 把正交性传到所有较早的 p i p_i p i 。反过来,梯度正交正是短递推足够的原因:由于 A p i = ( g i + 1 − g i ) / α i Ap_i=(g_{i+1}-g_i)/\alpha_i A p i = ( g i + 1 − g i ) / α i ,新方向自动与每个 i < k i\lt k i < k 的 p i p_i p i 共轭,只需选择一个系数 β k + 1 \beta_{k+1} β k + 1 。正定性用于保证分母为正,最后再用两次:共轭方向线性无关,从而步数不超过 n n n ;一阶条件则成为在 x 0 + K k x_0+K_k x 0 + K k 上的最小化。不精确线搜索和舍入误差会破坏这些不变性,所以定理只就精确运算陈述。
BFGS 为何采用秩二形式
证明
(先去掉在 s s s 上的旧作用,再加入割线项)
由 B B B 减去 B s s T B / ( s T B s ) Bss^TB/(s^TBs) B s s T B / ( s T B s ) ,先消去它在 s s s 上的作用;再加 y y T / ( s T y ) yy^T/(s^Ty) y y T / ( s T y ) ,把 s s s 映到 y y y 。结果对称且满足割线方程。对任意 v v v ,
v T B + v = v T B v − ( v T B s ) 2 s T B s + ( v T y ) 2 s T y . v^TB_+v=v^TBv-\frac{(v^TBs)^2}{s^TBs}+\frac{(v^Ty)^2}{s^Ty}. v T B + v = v T B v − s T B s ( v T B s ) 2 + s T y ( v T y ) 2 . B B B -内积下的 Cauchy–Schwarz 不等式令前两项之和非负,且仅当 v v v 为 s s s 的倍数时取零。非零倍数由 s T y > 0 s^Ty>0 s T y > 0 令最后一项为正,故 B + B_+ B + 正定。直接相乘 B + H + B_+H_+ B + H + ,代入 H B = I HB=I H B = I 和 ρ s T y = 1 \rho s^Ty=1 ρ s T y = 1 ,可验证上面的逆公式。此推导选出一种对称秩二更新;割线方程本身不能唯一决定整个矩阵。
证明透视
曲率条件在哪里支撑正定性 对称性和割线方程纯粹是代数:减去的项把 s s s 映到 B s Bs B s ,加上的项把 s s s 映到 y y y 。真正的工作在正定性。v T B + v v^TB_+v v T B + v 的前两项构成 B B B -内积下的 Cauchy–Schwarz 差额,这需要 B B B 是 SPD,而且只在经过 s s s 的直线上为零。曲率条件使第三项处处非负,在那条直线上更起决定作用:对 v = t s v=ts v = t s ,整个二次型等于 t 2 s T y t^2s^Ty t 2 s T y 。因此正的差额处理了 s s s 以外的所有方向,而 s T y > 0 s^Ty\gt0 s T y > 0 处理 s s s 本身;下面的反例展示了它不成立时会发生什么。
若 p p p 是下降方向,s = α p s=\alpha p s = α p 且 α > 0 \alpha>0 α > 0 ,弱 Wolfe 条件给出
s T y = α [ ∇ f ( x + α p ) T p − ∇ f ( x ) T p ] ≥ α ( c 2 − 1 ) ∇ f ( x ) T p > 0. s^Ty=\alpha[\nabla f(x+\alpha p)^Tp-\nabla f(x)^Tp]
\ge\alpha(c_2-1)\nabla f(x)^Tp>0. s T y = α [ ∇ f ( x + α p ) T p − ∇ f ( x ) T p ] ≥ α ( c 2 − 1 ) ∇ f ( x ) T p > 0.
即使目标非凸,弱 Wolfe 也保证曲率条件。只满足 Armijo 的步长一般不提供这保证。
有条件的全局保证
假设 f f f 有下界、梯度为 L L L -Lipschitz,沿 p k = − H k g k p_k=-H_kg_k p k = − H k g k 的每一步都满足弱 Wolfe 条件,而逆近似有一致谱界 m I ⪯ H k ⪯ M I mI\preceq H_k\preceq MI m I ⪯ H k ⪯ M I ,其中 0 < m ≤ M 0\lt m\le M 0 < m ≤ M 固定。则 ∥ g k ∥ → 0 \|g_k\|\to0 ∥ g k ∥ → 0 。若 f f f 还是 μ \mu μ -强凸,最小点为 x ∗ x_* x ∗ ,则 x k → x ∗ x_k\to x_* x k → x ∗ 。
在非驻点,g k T p k = − g k T H k g k ≤ − m ∥ g k ∥ 2 < 0 g_k^Tp_k=-g_k^TH_kg_k\le-m\|g_k\|^2\lt0 g k T p k = − g k T H k g k ≤ − m ∥ g k ∥ 2 < 0 ,所以 p k p_k p k 是下降方向;再由 ∥ H k g k ∥ ≤ M ∥ g k ∥ \|H_kg_k\|\le M\|g_k\| ∥ H k g k ∥ ≤ M ∥ g k ∥ 得
cos θ k = g k T H k g k ∥ g k ∥ ∥ H k g k ∥ ≥ m M . \cos\theta_k=\frac{g_k^TH_kg_k}{\|g_k\|\|H_kg_k\|}\ge\frac mM. cos θ k = ∥ g k ∥∥ H k g k ∥ g k T H k g k ≥ M m . Wolfe 角度定理因此给出 ∥ g k ∥ → 0 \|g_k\|\to0 ∥ g k ∥ → 0 。在强凸性下梯度强单调,特别有 ∥ g k ∥ ≥ μ ∥ x k − x ∗ ∥ \|g_k\|\ge\mu\|x_k-x_*\| ∥ g k ∥ ≥ μ ∥ x k − x ∗ ∥ ,所以 x k → x ∗ x_k\to x_* x k → x ∗ 。
一致谱界是明确的额外假设;单靠 BFGS 更新及正定性没有证明它。因此这个论证不能当作无条件的 BFGS 全局收敛定理引用。
局部超线性判据
假设 x k → x ∗ x_k\to x_* x k → x ∗ 、∇ f ( x ∗ ) = 0 \nabla f(x_*)=0 ∇ f ( x ∗ ) = 0 ,Hessian 在 x ∗ x_* x ∗ 连续,而最终使用完整步 x k + 1 = x k − B k − 1 ∇ f ( x k ) x_{k+1}=x_k-B_k^{-1}\nabla f(x_k) x k + 1 = x k − B k − 1 ∇ f ( x k ) ,且 ∥ B k − 1 ∥ \|B_k^{-1}\| ∥ B k − 1 ∥ 一致有界。令 e k = x k − x ∗ e_k=x_k-x_* e k = x k − x ∗ 。若
∥ ( B k − ∇ 2 f ( x ∗ ) ) e k ∥ ∥ e k ∥ ⟶ 0 , \frac{\|(B_k-\nabla^2f(x_*))e_k\|}{\|e_k\|}\longrightarrow0, ∥ e k ∥ ∥ ( B k − ∇ 2 f ( x ∗ )) e k ∥ ⟶ 0 , 则收敛超线性,即 ∥ e k + 1 ∥ / ∥ e k ∥ → 0 \|e_{k+1}\|/\|e_k\|\to0 ∥ e k + 1 ∥/∥ e k ∥ → 0 。
由于 ∇ f ( x ∗ ) = 0 \nabla f(x_*)=0 ∇ f ( x ∗ ) = 0 且 Hessian 在 x ∗ x_* x ∗ 连续,∇ f ( x k ) = ∇ 2 f ( x ∗ ) e k + o ( ∥ e k ∥ ) \nabla f(x_k)=\nabla^2f(x_*)e_k+o(\|e_k\|) ∇ f ( x k ) = ∇ 2 f ( x ∗ ) e k + o ( ∥ e k ∥ ) 。因此 e k + 1 = e k − B k − 1 ∇ f ( x k ) = B k − 1 [ ( B k − ∇ 2 f ( x ∗ ) ) e k + o ( ∥ e k ∥ ) ] e_{k+1}=e_k-B_k^{-1}\nabla f(x_k)=B_k^{-1}[(B_k-\nabla^2f(x_*))e_k+o(\|e_k\|)] e k + 1 = e k − B k − 1 ∇ f ( x k ) = B k − 1 [( B k − ∇ 2 f ( x ∗ )) e k + o ( ∥ e k ∥ )] 。判据及 ∥ B k − 1 ∥ \|B_k^{-1}\| ∥ B k − 1 ∥ 的一致上界使右端成为 o ( ∥ e k ∥ ) o(\|e_k\|) o ( ∥ e k ∥ ) 。
这只是充分判据,并未证明任意 BFGS 序列都满足它。更强的 BFGS 超线性定理需要额外假设及独立证明。
Krylov 最小化及误差界
Krylov 解释除了有限步终止,也可与任意多项式作定量比较。因 x k − x 0 ∈ K k x_k-x_0\in K_k x k − x 0 ∈ K k ,误差 e k = x k − x ∗ e_k=x_k-x_* e k = x k − x ∗ 可写成 P k ( A ) e 0 P_k(A)e_0 P k ( A ) e 0 ,其中 P k P_k P k 次数至多 k k k 且 P k ( 0 ) = 1 P_k(0)=1 P k ( 0 ) = 1 。反过来,每个此类多项式都给出 x 0 + K k x_0+K_k x 0 + K k 中一点。CG 在该仿射空间最小化二次目标差,而
f ( x ) − f ( x ∗ ) = 1 2 ∥ x − x ∗ ∥ A 2 , ∥ v ∥ A 2 = v T A v . f(x)-f(x_*)=\tfrac12\|x-x_*\|_A^2,
\qquad \|v\|_A^2=v^TAv. f ( x ) − f ( x ∗ ) = 2 1 ∥ x − x ∗ ∥ A 2 , ∥ v ∥ A 2 = v T A v .
对角化 A A A 可得:对每个可用多项式 P P P ,∥ e k ∥ A ≤ max λ ∈ spec ( A ) ∣ P ( λ ) ∣ ∥ e 0 ∥ A \|e_k\|_A\le\max\limits_{\lambda\in\operatorname{spec}(A)}|P(\lambda)|\,\|e_0\|_A ∥ e k ∥ A ≤ λ ∈ spec ( A ) max ∣ P ( λ ) ∣ ∥ e 0 ∥ A 。取 m = λ min m=\lambda_{\min} m = λ m i n 、M = λ max M=\lambda_{\max} M = λ m a x 、κ = M / m \kappa=M/m κ = M / m ,并选 P ( λ ) = ( 1 − 2 λ / ( m + M ) ) k P(\lambda)=(1-2\lambda/(m+M))^k P ( λ ) = ( 1 − 2 λ / ( m + M ) ) k 。在整个 [ m , M ] [m,M] [ m , M ] ,因子的绝对值至多 ( κ − 1 ) / ( κ + 1 ) (\kappa-1)/(\kappa+1) ( κ − 1 ) / ( κ + 1 ) ,所以
∥ e k ∥ A ≤ ( κ − 1 κ + 1 ) k ∥ e 0 ∥ A . \|e_k\|_A\le\left(\frac{\kappa-1}{\kappa+1}\right)^k\|e_0\|_A. ∥ e k ∥ A ≤ ( κ + 1 κ − 1 ) k ∥ e 0 ∥ A .
此界来自与固定步长梯度法比较,未必是最锐利的 CG 界;更精细的多项式可改善它。即使尚未精确终止,它仍说明条件数的影响。当 m = M m=M m = M ,所有特征值相同,CG 一步终止,与零因子一致。
检查及保障曲率
反例模式
没有正曲率时更新会离开正定锥 一个诱人的说法是:正定矩阵的 BFGS 更新总是正定。取 f ( x ) = − x 2 f(x)=-x^2 f ( x ) = − x 2 、x = 1 x=1 x = 1 、s = 1 s=1 s = 1 ,则 y = f ′ ( 2 ) − f ′ ( 1 ) = − 2 y=f'(2)-f'(1)=-2 y = f ′ ( 2 ) − f ′ ( 1 ) = − 2 ,故 s T y = − 2 s^Ty=-2 s T y = − 2 。以正定标量 B = 1 B=1 B = 1 代入公式,得 B + = 1 − 1 + ( − 2 ) 2 / ( − 2 ) = − 2 B_+=1-1+(-2)^2/(-2)=-2 B + = 1 − 1 + ( − 2 ) 2 / ( − 2 ) = − 2 ,是负数。这一对向量不可能有正定割线矩阵,因为它会迫使 s T y = s T B + s > 0 s^Ty=s^TB_+s>0 s T y = s T B + s > 0 。补救的条件正是 s T y > 0 s^Ty>0 s T y > 0 ,而弱 Wolfe 步能提供它。实现时可以在曲率不足时跳过或修改更新,但具体保障方式会改变算法,引用收敛结论前必须写清楚。
首个 BFGS 矩阵也重要:正定性保持证明从正定 B 0 B_0 B 0 出发,不定初始矩阵不符合假设。反过来,即使每一步均保持正定,也只保证非零梯度时方向下降;特征值仍可能趋向零或无限。上面的有条件全局结果明确假设一致谱界,正是为了控制方向角度。
梯度正交是精确运算的不变性
CG 归纳不只是提供系数公式。在第 k k k 步,g k g_k g k 与所有已搜索方向正交;因此其张成空间内没有方向令当前目标产生非零一阶变化。由 Hessian 正定,这个一阶结论证明仿射 Krylov 空间上的最小点,而不只是驻点。一旦新残差为零,即有 A x k = b Ax_k=b A x k = b ,不需要再做递推。
对 A = a I A=aI A = a I (a > 0 a>0 a > 0 )可直接检查:第一个方向是 − g 0 -g_0 − g 0 ,精确步长为 1 / a 1/a 1/ a ,因此 g 1 = g 0 + ( 1 / a ) A ( − g 0 ) = 0 g_1=g_0+(1/a)A(-g_0)=0 g 1 = g 0 + ( 1/ a ) A ( − g 0 ) = 0 。一般正定矩阵在不同特征方向有不同曲率,一个标量步长通常不能同时消去所有分量;递推因应剩余分量建立新方向。重复特征值可以使相关 Krylov 空间维数小于环境维数,令精确终止提早发生。
浮点运算中,递推计算的残差和真实残差 b − A x k b-Ax_k b − A x k 可能逐渐偏离,舍入亦会扰乱有限步证明所用的正交性。偶尔重新计算真实残差可评估实际线性系统误差,但重算或重启规则属于实现选择,此数学证明没有指定。对正定 A A A ,小残差给出 ∥ x k − x ∗ ∥ ≤ ∥ r k ∥ / λ min ( A ) \|x_k-x_*\|\le\|r_k\|/\lambda_{\min}(A) ∥ x k − x ∗ ∥ ≤ ∥ r k ∥/ λ m i n ( A ) ,所以解读残差亦依赖最小特征值的尺度。
二次误差多项式的常数项是一,因为 Krylov 空间中的修正不能通过零次项任意改变初始误差。若具有该常数项的多项式在 A A A 每个不同特征值都为零,则其矩阵作用会消去误差的所有特征分量。这是不同特征值较少时可提早终止的另一解释;它仍是假设精确运算,不能消除浮点残差检查的需要。
例题详解
取 A = diag ( 1 , 2 ) A=\operatorname{diag}(1,2) A = diag ( 1 , 2 ) 、b = ( 1 , 2 ) T b=(1,2)^T b = ( 1 , 2 ) T 、x 0 = 0 x_0=0 x 0 = 0 。则 g 0 = ( − 1 , − 2 ) T g_0=(-1,-2)^T g 0 = ( − 1 , − 2 ) T 、p 0 = ( 1 , 2 ) T p_0=(1,2)^T p 0 = ( 1 , 2 ) T 、α 0 = 5 / 9 \alpha_0=5/9 α 0 = 5/9 ,故 x 1 = ( 5 / 9 , 10 / 9 ) T x_1=(5/9,10/9)^T x 1 = ( 5/9 , 10/9 ) T 、g 1 = ( − 4 / 9 , 2 / 9 ) T g_1=(-4/9,2/9)^T g 1 = ( − 4/9 , 2/9 ) T 。系数 β 1 = 4 / 81 \beta_1=4/81 β 1 = 4/81 ,所以 p 1 = ( 40 / 81 , − 10 / 81 ) T p_1=(40/81,-10/81)^T p 1 = ( 40/81 , − 10/81 ) T 。下一步长为 9 / 10 9/10 9/10 ,x 2 = ( 1 , 1 ) T = A − 1 b x_2=(1,1)^T=A^{-1}b x 2 = ( 1 , 1 ) T = A − 1 b ;直接计算 p 0 T A p 1 = 0 p_0^TAp_1=0 p 0 T A p 1 = 0 。
标量 B = 3 B=3 B = 3 、s = 2 s=2 s = 2 、y = 4 y=4 y = 4 的曲率乘积为八。更新得 B + = 3 − 3 + 16 / 8 = 2 B_+=3-3+16/8=2 B + = 3 − 3 + 16/8 = 2 ,且 B + s = 4 = y B_+s=4=y B + s = 4 = y ,其逆为 1 / 2 1/2 1/2 。一维时割线方程已决定整个矩阵;高维时则不是。
f ( x ) = − x 2 f(x)=-x^2 f ( x ) = − x 2 在 x = 1 x=1 x = 1 的 Hessian 为 − 2 -2 − 2 ,牛顿方向 p = − 1 p=-1 p = − 1 ,梯度为 − 2 -2 − 2 ,所以 g p = 2 > 0 gp=2>0 g p = 2 > 0 ,方向上升。若逆近似正定,− H g -Hg − H g 才保证下降。此例无下界,不满足全局定理假设;它只用来展示方向可能失败。
常见错误
以下三种错误经常出现。
各方向满足 p i T A p j = 0 p_i^TAp_j=0 p i T A p j = 0 ,而不是 p i T p j = 0 p_i^Tp_j=0 p i T p j = 0 。在第一个例题中,p 0 = ( 1 , 2 ) T p_0=(1,2)^T p 0 = ( 1 , 2 ) T 与 p 1 = ( 40 / 81 , − 10 / 81 ) T p_1=(40/81,-10/81)^T p 1 = ( 40/81 , − 10/81 ) T 有 p 0 T p 1 = 20 / 81 ≠ 0 p_0^Tp_1=20/81\ne0 p 0 T p 1 = 20/81 = 0 ,但 p 0 T A p 1 = 0 p_0^TAp_1=0 p 0 T A p 1 = 0 。互相正交的是梯度。
n n n 步定理针对精确运算下的正定二次函数。舍入会破坏精确正交;非线性共轭梯度变体不会自动继承有限步证明。梯度为零时公式也应停止,除以零范数并不是另一次迭代。
只有在 s T y > 0 s^Ty>0 s T y > 0 时才保持正定,割线方程本身不足够。全局结果假设了一致谱界,超线性判据也只是充分条件;两者都不是对所有 BFGS 实现的无条件保证。
总结
CG 递推不必存储整组基底,便能强制精确线搜索及共轭性;对正定二次函数,在精确运算下至多维数步到解。BFGS 结合对称割线更新与正曲率。Wolfe 步长给正曲率,额外一致谱界给全局驻定保证;独立的局部近似条件给超线性收敛。
练习
快速检查
(对 A = diag ( 1 , 2 ) A=\operatorname{diag}(1,2) A = diag ( 1 , 2 ) 、b = ( 1 , 2 ) T b=(1,2)^T b = ( 1 , 2 ) T 验证第一个 CG 步及 g 1 T g 0 = 0 g_1^Tg_0=0 g 1 T g 0 = 0 。)
利用 α 0 = ∥ g 0 ∥ 2 / ( p 0 T A p 0 ) \alpha_0=\|g_0\|^2/(p_0^TAp_0) α 0 = ∥ g 0 ∥ 2 / ( p 0 T A p 0 ) 。
解答 · 答案 g 0 = ( − 1 , − 2 ) T g_0=(-1,-2)^T g 0 = ( − 1 , − 2 ) T 、p 0 = ( 1 , 2 ) T p_0=(1,2)^T p 0 = ( 1 , 2 ) T 、p 0 T A p 0 = 9 p_0^TAp_0=9 p 0 T A p 0 = 9 ,故 α 0 = 5 / 9 \alpha_0=5/9 α 0 = 5/9 。因此 g 1 = ( − 4 / 9 , 2 / 9 ) T g_1=(-4/9,2/9)^T g 1 = ( − 4/9 , 2/9 ) T ,内积 g 1 T g 0 = 4 / 9 − 4 / 9 = 0 g_1^Tg_0=4/9-4/9=0 g 1 T g 0 = 4/9 − 4/9 = 0 。
快速检查
(验证 Hessian BFGS 公式有 B + s = y B_+s=y B + s = y ,并解释 s T y > 0 s^Ty>0 s T y > 0 为何是正定解的必要条件。)
解答 · 答案 前两项作用于 s s s 后抵消,最后一项 y y T s / ( s T y ) = y yy^Ts/(s^Ty)=y y y T s / ( s T y ) = y 。若正定 B + B_+ B + 满足割线方程,则非零 s s s 有 s T y = s T B + s > 0 s^Ty=s^TB_+s>0 s T y = s T B + s > 0 。
快速检查
(若正定 H H H 的特征值在 [ 2 , 5 ] [2,5] [ 2 , 5 ] ,对非零 g g g 求 p = − H g p=-Hg p = − H g 的角度因子下界。)
估计 g T H g g^THg g T H g 的下界及 ∥ H g ∥ \|Hg\| ∥ H g ∥ 的上界。
解答 · 答案 g T H g ≥ 2 ∥ g ∥ 2 g^THg\ge2\|g\|^2 g T H g ≥ 2∥ g ∥ 2 ,∥ H g ∥ ≤ 5 ∥ g ∥ \|Hg\|\le5\|g\| ∥ H g ∥ ≤ 5∥ g ∥ ,故角度因子至少为 2 / 5 2/5 2/5 。这是简单充分界,未必最锐利。
快速检查
(在局部超线性判据中,若每次 B k = ∇ 2 f ( x ∗ ) B_k=\nabla^2f(x_*) B k = ∇ 2 f ( x ∗ ) 且逆矩阵有界,在所列收敛及完整步假设下可得什么结论?)
解答 判据分子恒为零,故其他假设蕴含 ∥ e k + 1 ∥ / ∥ e k ∥ → 0 \|e_{k+1}\|/\|e_k\|\to0 ∥ e k + 1 ∥/∥ e k ∥ → 0 ,即超线性收敛。这并没有证明任意初始点都会收敛。