動機
選擇下降方向只表示充分短的移動會改善目標值;它沒有告訴我們應走多遠、實際搜索會否找到步長,或反覆移動有甚麼結論。線搜索把局部資訊轉成算法: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,比一般二次界更強。