動機
Hessian 正定時,牛頓(Newton)步最小化局部二次模型,但離中心太遠時模型可能不準確;Hessian 不定時,無約束二次模型甚至可能無下界。信賴域把線搜索的問題倒過來:先限制模型可信的移動距離,再比較預測改善與實際改善。若兩者差距太大,便縮小區域重試。
限制於球內令任何連續二次模型都取得最小值,即使存在負曲率。實用算法未必需要精確解此子問題;也可要求至少取得負梯度方向所提供下降量的一定比例。本節分清精確模型解、廉價的受保障 Cauchy 步,以及推導一階收斂所需的假設。這些結論均不保證非凸目標的全局最小值。
定義
定義 10.1.1
(信賴域模型、預測下降量與吻合比率)
在 xk 令 fk=f(xk)、gk=∇f(xk)。選對稱矩陣 Bk 和半徑 0<Δk≤Δmax。試探步 sk 的模型及預測下降量為
mk(s)=fk+gkTs+21sTBks,predk=mk(0)−mk(sk),∥sk∥≤Δk.預測下降量為正時,定義吻合比率
ρk=predkf(xk)−f(xk+sk).
比率把實際下降量與模型承諾的下降量作比較,半徑規則再決定如何處理試探步。取 0<η1<η2<1、0<γdec<1<γinc。若 ρk<η1,拒絕試探步,令 xk+1=xk、Δk+1=γdecΔk。否則接受,令 xk+1=xk+sk;半徑保持不變,但若 ρk≥η2 且 ∥sk∥=Δk,可擴至 min{γincΔk,Δmax}。拒絕試探雖不改變迭代點,仍算分析中的一步。若 gk=0,算法停止;以下步長及比率只在 gk=0 時有定義。
假設已知 ∥Bk∥≤β,β≥0,令 Cβ=1+β。對 gk=0,受保障 Cauchy 步定義為
sk=−tkgk,tk=min{1/Cβ, Δk/∥gk∥}.
額外上限在梯度很小時限制步長。沿可行負梯度射線精確最小化模型至少能取得同樣下降,但未必滿足這個長度上限。以下全局定理明確使用它,不能把它暗中加到所有信賴域方法上。
定理/命題
對對稱 B 和 Δ>0,s∗ 在 ∥s∥≤Δ 上最小化 gTs+21sTBs,當且僅當存在 λ≥0 滿足
(B+λI)s∗=−g,B+λI⪰0,∥s∗∥≤Δ,λ(Δ−∥s∗∥)=0.
定理 10.1.4
(受保障 Cauchy 步的一階收斂)
設 f 在 Rn 連續可微、有下界,梯度以 L>0 為 Lipschitz 常數。各對稱 Bk 滿足 ∥Bk∥≤β,算法使用上述半徑規則和受保障 Cauchy 步。除非在駐點停止,否則 ∥gk∥→0。
第一個結果描述模型的全局最小點,包括不定及奇異情況。第二個結果只對指定步長規則證明梯度趨零,並非任意模型求解器的定理。更強的求解器需另給下降及步長控制假設。此梯度結論不要求迭代點有界、目標凸或最小點存在;若有聚點,梯度連續性令它成為駐點。
概念視角分析
從牛頓步到最速下降的一條精確步曲線
在困難情況之外,半徑為 Δ 的模型極小點位於曲線 s(λ)=−(B+λI)−1g(λ>ℓ)上,其中 ℓ=max{0,−imindi} 與下面的證明相同。其範數隨 λ 不增,所以縮小 Δ 會使邊界解沿曲線移向較大的 λ。若 B≻0,曲線在 λ=0 處從牛頓步 −B−1g 出發;當 λ→∞ 時,λs(λ)→−g。因此,小信賴域會把精確步轉向 Cauchy 步所用的最速下降方向。
證明思路
模型最優性及困難情況
若所列條件成立,對任意可行 s 展開模型差:
m(s)−m(s∗)=21(s−s∗)T(B+λI)(s−s∗)+2λ(∥s∗∥2−∥s∥2)≥0.第一項非負;若 λ>0,互補條件令 s∗ 在邊界,第二項也非負;若 λ=0,第二項為零。故即使 B 不定,這些條件仍充分。
證必要性時,對角化 B=Qdiag(di)QT,令 a=QTg 和 ℓ=max{0,−imindi}。對 λ>ℓ,駐點解各分量為 zi=−ai/(di+λ);其範數連續、不遞增,且在 λ→∞ 時趨零。若 B⪰0、g 在其值域,而 λ=0 時最小範數解不超過 Δ,它直接滿足條件。
否則,若 λ↓ℓ 的範數極限大於 Δ 或為無限,連續性給出 λ>ℓ 使 ∥z∥=Δ。餘下情況有 ℓ>0,a 與特徵值 −ℓ 的特徵空間正交,而極限的最小範數解不超過 Δ。加入該特徵空間中的向量,使它到達邊界;新點仍解 (B+ℓI)s=−g。這便是奇異的困難情況。構造出的點滿足充分條件,故是全局最小點。其他全局最小點有相同值,模型差公式中的非負項必同為零。對 H=B+λI⪰0,二次型為零給出 H(s−s∗)=0,故 Hs=−g;若 λ>0,第二項也迫使 ∥s∥=Δ。因此相同的駐點及互補條件成立。證明沒有假設 Hessian 可逆。
收斂定理的證明分兩部分:先證明足夠小的半徑終會被接受,再把接受步的下降轉化為梯度趨零。
Cauchy 下降及足夠小的半徑
令 t=tk,由矩陣範數界得
mk(0)−mk(−tgk)=t∥gk∥2−21t2gkTBkgk≥21∥gk∥min{Δk,∥gk∥/Cβ}.因為 tβ≤β/Cβ<1。步長亦滿足 ∥sk∥≤∥gk∥/Cβ。Lipschitz 梯度估計與 ∥Bk∥≤β 給出,令 C=(L+β)/2>0,
∣f(xk+sk)−mk(sk)∣≤C∥sk∥2≤CΔk2.固定 ε>0。若 ∥gk∥≥ε 且 Δk≤min{ε/Cβ,(1−η1)ε/(2C)},Cauchy 界推出 ∣1−ρk∣≤1−η1,因此該步被接受。故梯度至少為 ε 時,拒絕的步不能把半徑縮至低於上述閾值的 γdec 倍。
由接受步下降推出梯度趨零
先假設最終所有 ∥gk∥≥ε。由上段,從那時起半徑有共同正下界:接受不會縮小半徑;拒絕只在半徑高於上述閾值時發生,所以半徑至多降至閾值的 γdec 倍。Cauchy 界與 ρk≥η1 因而令每次接受的目標下降量有固定正下界。f 有下界,所以不可能無限次接受;但連續拒絕亦不可能無限,因半徑終會小到可接受。矛盾證明 kliminf∥gk∥=0。
再證完整極限。固定 a>0。在接受步且 ∥gk∥≥a、Δk≤a/Cβ 時,目標下降至少為 (η1a/2)Δk≥(η1a/2)∥sk∥。若 ∥gk∥≥a 且 Δk>a/Cβ,每次接受至少下降 η1a2/(2Cβ),故只可能有限次,每一步的長度均有限。因此,起點梯度至少為 a 的接受步,其總長度有限;拒絕步位移為零。
選 a>0 使 (1+L/Cβ)a<ε/2。由保障步長及 Lipschitz 條件,若一步起點梯度小於 a,終點梯度仍小於 ε/2。若梯度無限次達到 ε,但下極限為零,選一個梯度至少為 ε 的指標 ℓ,在它之前存在梯度小於 a 的指標;令 j 為 ℓ 前最後一個這樣的指標。則 ∥gj+1∥<ε/2,而 j+1,…,ℓ−1 各步起點梯度至少為 a。Lipschitz 連續性迫使這些步的總路程至少為 ε/(2L)。無限多個互不重疊的過程與總長度有限矛盾。因此梯度趨零。長度上限正是在跨入這類過程時使用。
一起解讀兩個誤差估計
證明透視
半徑縮小為何恢復吻合
各項假設在不同位置使用。一致界 ∥Bk∥≤β 用了兩次:在 Cauchy 不等式中保證 tβ<1,在誤差估計中控制模型曲率。梯度的 Lipschitz 連續性提供誤差估計的另一半,之後又把梯度範數的變化轉化為移動距離。f 有下界只用來令接受步的下降量可加總。
關鍵一步是比較階數。Cauchy 不等式是模型預測下降量的下界;Lipschitz 估計則是實際值偏離預測的上界。當梯度有正下界而半徑小時,保證的預測量與半徑成正比,模型誤差卻與半徑平方成正比,因此充分小的半徑迫使 ρk≥η1。若不知道預測下降不會更快趨零,只說模型局部準確並不足夠。
單靠這個比較只得到 kliminf∥gk∥=0。論證最後把下降轉化為長度:梯度大的接受步總長度有限,而每段由梯度小於 a 走到梯度至少為 ε 的過程必須移動至少 ε/(2L)。上限 ∥sk∥≤∥gk∥/Cβ 防止這類過程以一次長跳開始。
定理容許每一步的 Bk 奇異或不定,因 Cauchy 論證只使用其一致範數界。它亦容許連續拒絕許多試探,但固定非駐點處不可能永遠拒絕:半徑反覆乘 γdec 後,前述比較必迫使接受。上界 Δmax 是方便的既定規則;有限路程論證並不依賴它,因大半徑接受步只有有限多次。
被拒絕的模型與比率的意義
考慮 f(x)=x4/4 在 x=1,故意選模型曲率 B=−4,而非真實 Hessian。半徑為一時,精確模型最小步是 s=−1:模型變化 s−2s2 在兩端點中較小的值為 −3。預測下降為 3,實際從一到零的下降僅 1/4,所以 ρ=1/12,接受閾值 η1=0.1 會拒絕此步。模型過於樂觀;拒絕避免把預測當作實際進展。
若半徑縮至 1/2,精確模型步為 s=−1/2。預測下降為一,實際下降是 1/4−(1/2)4/4=15/64,比率 15/64>0.1,所以此試探被接受。這只說明比率規則,不是全局定理的例子:x4/4 在整條實線的梯度並非全局 Lipschitz,而且此處使用精確模型步,而非受保障 Cauchy 步。
信賴域乘子不是罰係數
概念視角結構
只屬於模型的乘子
乘子 λ 屬於某個固定二次子問題。對邊界解,它將 Hessian 移位至非負曲率,同時滿足駐點方程及邊界長度條件;即使半徑不變,它亦可隨迭代改變。它不是原決策問題約束的乘子,也不可與另一受約束問題所選的罰係數混為一談。
對一維凸模型 m(s)=gs+bs2/2,b>0,無約束最小點為 −g/b。若其絕對值不超過 Δ,取 λ=0。否則最小點為端點 s∗=−Δsign(g),駐點條件給出 λ=∣g∣/Δ−b>0。此公式顯示容許位移縮小時乘子如何增大。在轉折點 ∣g∣=bΔ,無約束最小點位於邊界,但 λ=0;邊界活躍並不保證乘子嚴格為正。
原目標的駐點仍可能有負曲率。本節的一階規則明確容許 g=0 時停止,所以可能停在鞍點或最大點。若要尋找二階駐點,算法需檢查負曲率並加入額外下降條件和收斂證明。不定模型例子顯示信賴域子問題能利用負曲率,卻不會自動把一階定理變成二階定理。
例題詳解
例題 10.1.5
(不定模型在球內仍有有限最小點)
在 ∣s∣≤2 上取 m(s)=−s2/2,s∗=2 及 s∗=−2 均最小。此時 g=0、B=−1、λ=1,故 B+λ=0 且四個條件均成立。無約束模型卻無下界;球約束從根本改變了問題。
取 B=diag(−1,2)、g=(0,1)T、Δ=1。在 λ=1,駐點方程給 s2=−1/3,s1 自由;邊界條件給 s1=±8/3。由於 B+I=diag(0,3) 半正定,兩點均為模型全局最小點。若硬要求 B+I 的逆,便會漏掉它們。
對 f(x)=x2/2 在 x=2,用精確 Hessian B=1。無約束牛頓步為 −2;半徑一時精確模型步為 −1,得到 x+=1。模型和目標相同,預測及實際下降都是 3/2,故 ρ=1。之後較大的半徑可容許完整牛頓步。
常見錯誤
比率為正表示目標值下降了,但上述規則只在 ρk≥η1 時接受。在被拒絕模型的計算中,ρ=1/12 為正,但取 η1=0.1 時試探仍被拒絕。收斂證明利用 ρk≥η1 把預測下降轉化為實際下降的固定比例;僅僅為正的比率並無這樣的比例。
當 ∥s∗∥=Δ 且 λ>0 時,最小點解的是 (B+λI)s=−g,而不是 Bs=−g。在以球保障牛頓步的例題中,g=2、B=1、Δ=1;邊界步 s∗=−1 對應 λ=1,因為 (1+1)(−1)=−2=−g。牛頓方程則給出不可行的 s=−2。
常見錯誤
(在困難情況中對移位 Hessian 求逆)
人們很容易計算 s(λ)=−(B+λI)−1g,再調整 λ 直至 ∥s(λ)∥=Δ。對 B=diag(−1,2)、g=(0,1)T、Δ=1,每個容許的 λ>1 都給出 s(λ)=(0,−1/(2+λ))T,其範數小於 1/3,所以沒有任何逆矩陣解能到達邊界。最小點要用奇異移位 λ=1,再加上特徵向量分量 s1=±8/3。
模型證書中的半正定條件並非裝飾:沒有它,其餘條件可能證明球內最差的點。
反例模式
只有駐點與互補條件而沒有曲率條件
斷言:若可行點 s∗ 對某個 λ≥0 滿足 (B+λI)s∗=−g 及 λ(Δ−∥s∗∥)=0,則 s∗ 在球上最小化模型。取 m(s)=s−s2/2,即 g=1、B=−1,並取 Δ=1。邊界點 s=1 在 λ=0 時滿足 (−1+0)⋅1=−1=−g,互補條件亦平凡成立。然而 m(1)=1/2、m(−1)=−3/2;由於在 [−1,1] 上 m′(s)=1−s≥0,s=1 其實是最大點。失效的正是被省略的條件:B+0=−1 不是半正定。在 s=−1,駐點條件 (−1+λ)(−1)=−1 給出 λ=2,而 B+2=1≥0,完整證書正確找出真正的最小點。
本證明使用步長上限;其他分析可用 Cauchy 下降的一定比例,以不同論證得到相同梯度結論,這裏不作推導。
總結
信賴域令二次子問題有限,並容許負曲率下的全局證書。移位半正定 Hessian 與互補半徑乘子刻畫精確模型最小點。受保障 Cauchy 步提供定量預測下降;半徑充分小時模型可靠,再由接受下降及步長控制,在明列假設下證明梯度趨零。
練習
快速檢查
(在 ∣s∣≤1/2 上最小化 m(s)=s+s2/2,並求半徑乘子。)
解答
無約束最小點 −1 在球外。由於在 [−1/2,1/2] 上 m′(s)=1+s>0,模型在該區間遞增,受約束最小點為 s=−1/2。由 (1+λ)(−1/2)=−1 得 λ=1;移位 Hessian 1+λ=2 為正,而 s 在邊界上,互補條件成立。
快速檢查
(若 g=(1,0)T、B=diag(2,1)、半徑為一,以矩陣範數界 β=2 計算受保障 Cauchy 步及其預測下降。)
解答
此處 Cβ=3、t=min{1/3,1/1}=1/3,故 s=(−1/3,0)T。預測下降為 t∥g∥2−21t2gTBg=1/3−21⋅91⋅2=2/9。Cauchy 界保證 21∥g∥min{Δ,∥g∥/Cβ}=1/6,而確實 2/9>1/6。
快速檢查
(對 ∣s∣≤1 上的 m(s)=−s2/2,檢查 s=0、λ=0 的證書並解釋失敗原因。)
解答
在 s=0、λ=0 時,駐點條件為 (B+0)⋅0=0=−g,互補條件亦成立,但 B+λ=−1 不是半正定,所以證書不完整。事實上 m(±1)=−1/2<0=m(0):零是最大點,而非最小點。
快速檢查
(若 L=2、β=1、η1=1/2、∥g∥≥1,求證明中足以保證接受的半徑閾值。)
在證明的接受閾值中取 ε=1。
解答
此處 Cβ=2、C=(L+β)/2=3/2。取 ε=1,閾值為 min{ε/Cβ,(1−η1)ε/(2C)}=min{1/2,(1/2)/3}=1/6。在所列假設下,任何不大於 1/6 的正半徑都給出 ∣1−ρ∣≤1/2,故 ρ≥1/2。