動機
正定 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 ,即超線性收斂。這並沒有證明任意初始點都會收斂。