內層求解法需要交付甚麼
信賴域模型是大問題內的一個小型最優化問題。上一單元已推導其全局最小點的平移 Hessian 證書,但找出該點的工作量可能超過外層迭代的需要。若矩陣只能透過與向量的乘積取得,對角化尤其不合算。因此我們先問一個較適度的問題:能否用有限次矩陣向量乘積,求得一個可行而且有明確模型下降量的步?
負梯度射線給出一個基準,即 Cauchy 點。截斷共軛梯度法(CG)在曲率仍為正時改善這個基準,在球面停止,並把偵測到的非正曲率轉成沿下降方向走向球面的步。「偵測到」這一點很重要:Krylov 子空間未必會遇到整個空間中其他位置的負曲率方向。我們會證明模型下降保證,而不把這個算法誤當成二次模型的全局求解法。
以下略去模型的常數項,寫成
範數是 Euclidean 範數,矩陣範數是其誘導譜範數。除另有說明外,,而算法的所有運算均採用精確算術。若 ,下述一階程序返回零;它不作二階最優性的聲稱。
Cauchy 點及其下降量
記 、。在射線 上,可行性等價於 ,且
若 ,這個函數在可行區間上嚴格遞減,故選右端點。若 ,不受限制的最小值在 取得。因此
Cauchy 點只在一條射線上最小化,並非在整個球上最小化。然而,它的下降量具有全局一階論證所需的尺度。
命題 10.2.1
(Cauchy 下降量)
若 ,令 ,則
證明
(與一個短射線步比較)
把 與可行射線點 比較,其中 。由於 在射線的可行部分上最小化 ,且 、,
因 、,此值為正。
採用 可避免在 時另訂除法慣例。比較點正是上一單元有保障的射線步。Cauchy 點可能較長;自動沿用的是下降量,而非該步的長度上界。
到達邊界而不越界
設 、。恰有一個正數 滿足 。令
這是 的正根;兩根的乘積是 ,所以另一根為負。球的凸性保證到正根為止的線段仍可行。浮點運算時,若 ,等價公式 可避免相減消去誤差;但此處的證明使用精確正根。若以容許誤差判定已碰到邊界,便改變了實作規則,必須另外交代誤差。
明確的截斷 CG 規則
選相對殘差容許值 ,從
開始。這裏 是二次模型的梯度,不是原目標問題的可行性量度。當 時,依以下次序處理。
- 計算 。若 ,返回 。零曲率與負曲率採用同一規則。
- 若 ,計算 。若 ,返回 。等號也視為邊界返回,先於任何殘差檢查。
- 否則令 、。若 ,返回 ;這包括殘差恰為零的情況。
- 若殘差仍非零,令 、,然後繼續。
殘差停止檢查在完成一步後才進行,故算法至少會完成與 Cauchy 點的比較。每次取新方向時,當前點都嚴格位於球內,所以邊界根公式總有 。在非正曲率方向上,這個規則選向前的交點。比較兩個交點可能進一步降低模型值,但下述保證不需要這樣做。
定理 10.2.2
(有限步終止與 Cauchy 下降)
對稱 、、、 下,上述精確算術程序至多經 個方向迭代便返回。其輸出 可行,且滿足 。因此,若 ,則
此聲明不斷言 是球約束模型的全局最小點。
截斷前,CG 恆等式為何仍成立
證明
(以歸納法證明共軛性與正交性)
在正曲率步仍嚴格留在球內時證明所需恆等式。歸納假設已有方向互相 -共軛,當前殘差則與所有較早方向正交。遞推式給出 。因此精確線最小化步使
對 ,由 和 ,同樣有 。新殘差遂與截至當時的全部方向正交。較早殘差都在這些方向的生成空間內,因為 ,且 。因此非零殘差互相正交。
要證明新方向的共軛性,使用 。對 ,剛證得的正交性給出 ,再用前一方向的共軛性便得 。對相鄰方向,
所以 中的兩項相消,完成歸納。這裏沒有使用整個空間上的正定性,只用了已完成步的正方向曲率。
互相共軛且 的方向線性無關:把一個線性關係分別左乘各 ,每個係數都必為零。若已完成 個正曲率內點步,這些方向生成 ,而 與整個空間正交,故必為零。否則,程序早已在容許誤差、邊界或非正曲率檢查時返回。因此不會走到除以零殘差的運算。
概念視角代數
內部 CG 迭代點在 Krylov 子空間上極小化模型
記 。只要每個已完成的步都在內部且 ,對遞推關係作歸納便知 生成 。在這組 共軛基下, 分解成嚴格凸的一維項之和,而 使 恰為其所屬項的極小點。因此 是 在 上的唯一極小點。下面的反例正是 始終不離開一條座標軸的情形。
後續步為何不會抵銷第一步的下降
證明
(從 Cauchy 步開始的單調下降)
每個方向開始時,沿該方向的模型導數為
若 ,它在整條向前射線上嚴格為負。若 ,它在 之前保持非正;邊界截斷所取的 滿足 。每一段返回或完成的線段都降低模型值。首方向是 ,故首步正好到達 Cauchy 點:不是射線最小點,就是邊界。若程序繼續,其後各段把值再降低。這便同時證明 和定理中的下降量下界。
證明透視
終止定理的兩個獨立部分
有限步終止與充分下降由不同機制證明。終止方面,歸納法保持非零殘差兩兩正交,所以 中至多容納 個;微妙之處在於只用到已完成步的曲率 ,從不需要 在整個空間上正定。下降方面,關鍵一步是首方向為 ,所以首段正好停在 Cauchy 點,不論是射線最小點 還是邊界。此後導數 在每段實際走過的線段上都非正: 時在整條向前射線上如此, 時則直到 。這正是邊界規則取向前根的原因。兩部分都不涉及全局最優性:邊界返回的殘差可以很大,零殘差也可能錯過生成子空間以外的負曲率。
逐步算例
例題 10.2.3
(兩個內點步解出正定模型)
取 、、、。此時 、、,且 的範數為 。殘差是 ,而 給出 。其曲率是 ,故 。所以 、,且 。模型值是 ,預測下降量為 。
若同一模型的半徑改成 ,首個不受限制的射線最小點在球外。從零出發的邊界根為 ,得到 ,預測下降量為 。程序不會形成第二個方向。
例題 10.2.4
(一個正曲率步後偵測到負曲率)
令 、、、。首方向是 ,曲率為 ,所以 ,而 在球內。接著 、、。其曲率為 ,觸發非正曲率規則。
此時 、、。邊界根為 ,故返回點是 ,範數為五。模型值從 降至 。這是有用的下降步,卻不是精確全局解: 的第一個座標會要求 ,違反乘子非負的必要條件。
反例模式
零殘差也可能錯過困難情形
設 、、。CG 只探索第二個座標,走到 後便以 返回,且 。但 的範數為一,值為 。平移 Hessian 證書在此以 、 成立。未被探索的第一座標帶有負曲率。要修正「殘差小便證明找到全局模型解」這個錯誤說法,必須加入有效的曲率和邊界證書;否則只能保留截斷 CG 實際已證的充分下降結論。
殘差能證明甚麼
命題 10.2.5
(正定模型的殘差上界)
對正定 ,若已知 ,令 、,則
證明
(在駐點附近展開)
兩個上界都來自 :首先 ;又因 ,在 附近展開得 。
若 可行,它也是球上的最小點。即使 在球外,任何可行 相對於約束最小點的模型差,也不超過上述無約束模型差。
常見錯誤
(把相對殘差檢查當作誤差界)
上述上界依賴正的譜下界;相對條件 本身並不提供該下界。除非已知這樣的下界,截斷 CG 以小殘差返回並不說明它離解有多遠。
例題 10.2.6
(未平移殘差非零的邊界最小點)
取 、、、,於是在 上 。由於在 上 ,最小點是邊界點 ,且 。其未平移殘差為 ,所以在邊界上檢查未平移的駐點方程並不正確。取乘子 ,則 、,而因 ,互補項 為零。因此下面的近似證書把差距的上界定為 :該點正是全局最小點。
若有明確曲率資訊,可得到有用的近似證書。
命題 10.2.7
(近似最優性證書)
設 可行、、,並令 。則對任何全局球最小點 ,
證明
(以平移 Hessian 展開)
把 展成 ,捨去非負二次項,再用 。
若點精確位於可行球面,最後一項為零。只有小的 ,卻沒有半正定檢查或互補項控制,便不構成這個證書。截斷 CG 不會自動計算合適的 ,也不會證明全空間上的半正定性。
與外層收斂證明的連接
上一單元證明有保障射線步的梯度收斂。
常見錯誤
(對未受保障的截斷 CG 引用外層定理)
未作修改的截斷 CG 沿用其 Cauchy 下降下界,卻未必沿用長度上界 。因此,不能只因兩者都叫信賴域方法便引用該定理。
有一個明確的受保障版本:外層第 次迭代在較小的球
上執行上述程序。輸出同時滿足
保持上一單元的外層接受及半徑規則,包括只有滿足原來的 邊界條件才擴大半徑。在同樣的全局 Lipschitz 梯度、目標下界及對稱模型範數一致有界假設下,該單元的證明適用於這兩個不等式:模型誤差估計使用可行性,小半徑接受使用下降量不等式,而有限往返論證使用長度上界。因此,這個受保障版本也有 ,或在駐點停止。此論證明確保留長度限制;它不證明未受限制的截斷 CG 外層方法,也不證明二階駐點定理。
練習
快速檢查
(對 、、,計算 Cauchy 點及截斷 CG 的首次返回。)
先計算 。
解答 · 答案
,所以 、。在 CG 中, 且 ,非正曲率規則遂返回同一邊界點,其模型值為 。
快速檢查
(若 、、,計算正邊界根,並解釋為何不取負根。)
寫出邊界二次方程的 、、。
解答 · 答案
此時 、、,兩根是 。向前根為 ,產生球上的 。負根沿方向往後走,而下降證明控制的是向前線段。
快速檢查
(設 ,某內點近似解有 。給出它到無約束二次模型最小點的距離及目標差上界。)
用 代入殘差上界。
解答 · 答案
給出距離至多 ,目標差至多 。這些是利用已知譜下界的嚴謹上界;單靠殘差大小不能決定它們。
快速檢查
(在純量邊界模型 、、 中,取 、。計算 及近似證書的兩項。只有 是否足以令互補誤差為零?)
把證書與到最小點 的真實差距比較。
解答
、。殘差項為 ,互補項為 。上界雖鬆但有效:實際差是 。非負乘子未必滿足互補性;此處點嚴格在球內,而乘子為正。
快速檢查
(當 、、,求受保障半徑及保證的預測下降量。解釋保障額外提供哪個假設。)
受保障半徑是 。
解答
、。保證下降量是 。除了通常的球可行性與充分下降,保障還提供 ,讓已陳述的外層有限往返證明適用。