方向和距離回答的是不同問題。若 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,所以不能證明強曲率。此充分證書未通過,本身不代表真實強曲率不等式一定不成立。