從二次函數走向一般目標函數
對稱正定二次函數的共軛梯度法(CG)利用上一個方向,避免抵消已取得的進展。其簡短遞推與有限步終止依賴固定曲率及精確運算。目標函數不是二次函數時,能否保留節省記憶體的遞推?非線性共軛梯度法正是這樣做;但「共軛」只是名稱的由來,不代表新方向必然對某個固定矩陣全部共軛。
定義 7.3.1
(Fletcher–Reeves 非線性共軛梯度法)
設 連續可微,,取 。若 便停止。否則選正步長 ,令 ,再取
的點是駐點,但非凸函數的駐點未必是極小值。由於 時已停止, 的分母非零。實作只須儲存少量向量並計算梯度,不必計算 Hessian。其他 選法定義不同方法,其保證不能自動當作 FR 的保證。
我們希望 。對 在零處微分,得到 ;因此這個值嚴格為負,就保證充分小的正步長使函數下降。單看 前的負號並不足夠:從舊方向繼承的部分可能蓋過它。
精確線搜索與二次函數的計算
假設 是可微線函數的內點精確極小值,則
所以只要 ,下一個 FR 方向便嚴格下降。這裏的正交是對「上一個方向」而言;對非線性目標函數,它不一定同時正交於所有更早方向。精確線極小值可能難以求出,甚至在正射線上不存在,故此觀察本身並不是實際線搜索的保證。
對特殊二次函數 ,其中 對稱正定,梯度變化滿足 ,而精確步長產生了方法名稱所指的共軛性。
定理 7.3.2
(二次函數上精確 Fletcher–Reeves 步的共軛性)
設 , 對稱正定,並以精確線搜索執行 FR,直至梯度為零。則所得方向兩兩 -共軛,而每個梯度 都正交於 。
證明
(對步數歸納)
第一步有 及 ,所以 。假設直至 的方向兩兩 -共軛,而且 正交於所有更早方向。精確搜索給出 ;梯度更新及共軛性則給出 時 。因 時 ,亦有 。於是利用 ,得
因此 FR 選擇使 。若 ,由 及剛證得的正交性,得 : 和 都在 的生成空間中。故 。以 為起點便完成歸納。
標準線性 CG 理論進一步指出此二次問題至多 步終止;一般非線性 不隨之具有成對共軛或有限步終止性質。
完整二維算例
例題 7.3.3
(對角二次函數上的兩個精確 FR 步)
取 ,即 ,並取 ,則 、,精確線搜索給出
由 和 ,得 、。直接計算可見 。第二次精確步長為 ,得到 。這個有限步終止展示的是二次函數定理,而非對一般非線性問題的預測。
步只是上界;從座標軸上的點出發即可看到這一點。
例題 7.3.4
(少於 n 步便終止)
對同一個 ,由 出發。則 、,且 ,所以 、。方法一步後即停止;分母將為 的 從未計算。起始誤差只落在 的一個特徵向量上,因此一個搜索方向已經足夠。
非精確搜索:強 Wolfe 條件的作用
實務上通常接受足夠好的步長,而非精確最小化線函數。
定義 7.3.5
(強 Wolfe 條件)
設 是下降方向,。若步長 滿足
則稱它滿足強 Wolfe 條件。
第一式是 Armijo 充分下降條件。第二式控制新方向導數的絕對值,即使導數已改變符號也適用。條件針對實際接受的步長;只選定 並不證明搜索已找到合格步長。
定理 7.3.6
(Fletcher–Reeves 的一致下降界)
假設 連續可微、,每個接受步長均滿足固定常數 的強 Wolfe 條件。依上式構造 FR 方向,梯度為零時停止。停止前每個方向都滿足
因此每個方向都是下降方向。這個結論本身並不聲稱迭代收斂到極小值。
證明
(對正規化斜率歸納)
在 時定義 ,初值為 。把 FR 遞推式與 取內積,再除以 ,得
令 ,並假設 且 ;於是 是下降方向,強 Wolfe 條件適用於它的步長。強曲率條件給出 ,所以第二項的絕對值不超過 。因此
這組界給出 及 。因 滿足兩者,歸納即完成證明。
證明透視
控制繼承的舊方向
證明只追蹤一個純量,即正規化斜率 ;危險完全來自繼承項 。強 Wolfe 條件就用在這裏,而且只有帶絕對值的形式才有用:普通 Wolfe 曲率條件只從下方限制 ,一個很大的正值仍可把 推到零以上。歸納假設必須攜帶兩件事:界 ,因為曲率估計與 成正比;以及下降性 ,因為 Wolfe 條件只對下降方向有定義。關鍵一步是把 選為 的不動點,使區間的下端自我重現。假設 用在上端: 等價於 ,即 。論證完全沒有用到 Armijo 不等式;該條件影響的是收斂,而非這個符號估計。
要區分逐步下降性與收斂性:後者還涉及步長、光滑性、水平集及其他假設。對非凸目標函數,即使每一步方向下降,算法仍可能趨近不是極小值的駐點。
例題 7.3.7
(同一二次函數上的強 Wolfe 步)
回到 、、,取 、。線函數 滿足 、。試用 ,而非精確的 。Armijo 條件成立,因為 ;強曲率條件亦成立,因為 。於是 、、,且
因此 ,落在 時定理給出的區間 內,但不等於精確搜索的值 。
下降界在非精確步之後仍然成立;假設精確搜索的二次函數定理卻不再成立。
反例模式
非精確步失去有限步終止
一個誘人的說法是:在二維對稱正定二次函數上,只要步長滿足強 Wolfe 條件,FR 仍會在兩步內終止。在上例中 ,所以
兩個方向並不共軛。即使第二步精確,,所得 ,仍未到達最小點。有限步終止需要每一步(不只最後一步)都是精確線搜索,並且需要精確運算。
常見誤解與實作選擇
常見錯誤
(在 Wolfe 步後套用精確搜索的等式)
精確搜索後有 ,因而 。Wolfe 步只限制 ,一般不令其為零,上例的 便是明證。同樣,有限步終止定理需要固定的對稱正定二次函數及精確運算;捨入誤差、非精確搜索和變動的 Hessian 都可能破壞其正交等式。
常見錯誤
(小梯度不能證明極小)
對 , 處梯度為零,但零是嚴格局部極大值。以小梯度停止只表示近似駐點;它本身不能證明局部或全局極小性。
重啟是把 設為 ,不再沿用舊方向。只要 ,它就恢復下降性,但也丟棄已累積的方向資訊。對滿足上述定理假設的 FR 方法,證明下降性不需要重啟;實際重啟規則及數值停止容差則需另行選擇。應計算結果的目標函數與梯度;若需要最優性證書,還要利用凸性或合適的二階論證。
練習
練習 7.3.8
(在第一個例題中,直接驗證 和 。為甚麼後者使用 而非普通內積?)
基礎
解答(3)
- 1
檢查與上一個方向正交
。
- 2
檢查共軛性
,因此 。
- 3
說明 的作用
二次函數的曲率由雙線性形式 衡量;歐氏正交是另一個條件。此處 。
練習 7.3.9
(設 FR 方向滿足 ,接受的步長以 滿足強 Wolfe 條件。若 ,求 的界。)
核心
解答(3)
- 1
寫出正規化遞推式
,其中 。
- 2
限制繼承項
關鍵一步
。
依據: 強曲率條件給出 。
- 3
得出結論
,嚴格為負。這個局部計算不要求題中比值一定由此前 FR 迭代產生。
練習 7.3.10
(設 、、。 是否下降方向?重啟有甚麼作用?)
基礎
解答(2)
- 1
計算所提方向
,與 的內積是 ,所以是上升方向。
- 2
重啟
重啟得到 ,內積為 ,是下降方向。
練習 7.3.11
(在內點精確線極小值處,對任意有限純量 (不只 FR)證明 。為甚麼這不足以證明收斂?)
核心證明
解答(3)
- 1
在線上使用一階條件
。
依據: 線函數可微,且 是內點極小值。
- 2
把遞推式與 取內積
。
- 3
結論的限度
∎方向下降本身既不給出總進展的界,也不判定極限駐點的性質。