一步所提供的資訊
擬 Newton 方法利用相鄰迭代點的數據建立 Hessian 近似。令 、,割線方程 要求新矩陣沿著步長重現觀察到的梯度變化。這只限制一個方向,並不能決定整個矩陣;觀察值亦可能顯示負曲率或受誤差影響。若逆矩陣近似 正定,則對非零梯度, 必為下降方向,因為 。保持這個性質,與證明整個算法收斂,是兩件不同的事。
若 對稱正定(SPD),而 ,BFGS 更新為
它滿足 ,並保持正定。若 ,則不存在滿足原割線方程的正定矩陣:在方程左乘 就會得到矛盾 。阻尼是改變割線方程的目標,並非令此矛盾消失。
曲率保護
選定 ,假設 ,記 及 。定義
在 (1) 中以 代替 。第一種情況下觀察數據已達到門檻,故保持不變;第二種情況下 ,所以 。此時 混合實際梯度變化和舊模型的預測 。門檻是相對於模型曲率 ,並不是梯度誤差的絕對界。
定理 7.2.1
(阻尼 BFGS 保持正定)
設 為 SPD、、 且 。按 (2) 構造 ,並令
則 、,而且 為 SPD。在實際啟用阻尼時,第一個不等式取等號。
證明
(先計算 ,再檢驗二次型)
不修改時,。否則代入得
的前兩項互相抵消,最後一項給出 。對任意非零 ,
內積的 Cauchy–Schwarz 不等式說明前兩項之和非負,取等號當且僅當 是 的倍數。對非零倍數,因 ,最後一項嚴格為正。故 正定。這並未證明它接近真實 Hessian,也未證明迭代點收斂。
證明透視
保護步驟究竟證明了甚麼
證明有兩個互相獨立的部分。第一部分是關於 的代數:由於 是 的仿射函數, 的公式正是方程 的解,而分情況定義保證 ,所以 確實是 與 的混合。門檻令 不只為正,而且不小於模型曲率 的固定比例。第二部分是未阻尼 BFGS 的正定性論證,只是把 換成 ;保護步驟只在 Cauchy–Schwarz 取等號的情況出現:此時 是 的倍數, 令最後一項嚴格為正。兩部分都沒有涉及 ,所以定理對 Hessian 的近似程度或收斂均無任何斷言。
例題 7.2.2
(需要阻尼的一對數據)
取 、、 及 。此時 、,所以 ,,。直接代入得到
可驗證 。首個對角元素為正,行列式為 ,也確認此二維矩陣正定。原數據的曲率雖然為正,卻低於選定的相對門檻;正曲率本身不一定使阻尼閒置。
反例模式
原割線方程可能無解
對 ,取 、,則 。沒有正的純量 滿足 。取 、,(2) 給出 、。這是正定模型,但它使用修改後的割線數據,並不代表 的實際負曲率。
有限記憶的逆矩陣運算
儲存密集的 矩陣可能很昂貴。改為選擇易於與向量相乘的 SPD 初始矩陣 ,並按時間次序保留 對 ,每對都滿足 。令 ,概念上的逆矩陣更新為
不必實際構造 ,可用以下雙迴圈遞推計算 :
- 設 。按 計算並儲存 ,再以 取代 。
- 設 。按 計算 ,再以 取代 。
- 輸出 ;可用 作搜索方向。
把 (3) 的分解形式逐層展開,便可證明這個遞推。
命題 7.2.3
(雙迴圈遞推套用逆矩陣更新)
設保留的每一對都滿足 。在精確運算下,雙迴圈遞推輸出 ,其中 由 (3) 定義,過程中不需構造任何 矩陣。
證明
(為甚麼兩個迴圈的次序不同)
令 ,則 (3) 為 。將最新更新作用於 時,先把 作用於 ,所得向量再輸入較早的逆矩陣更新。重複此步得到反向迴圈,因為 。回程時,,恰好是正向迴圈。因此在精確算術下,結果等於 。若 ,兩個迴圈都是空的,結果為 。
(3) 每次更新均保持正定:對非零 ,二次型為 。若它為零,則 且 ;但後者使 ,矛盾。因此非零 對應的方向嚴格下降。數據對及暫存向量需要 空間;計算量為 加上套用 的成本。常見選擇是單位矩陣的正倍數。下次迭代可以丟棄最舊的一對,並以指定的新基底和剩餘數據重新定義概念矩陣;這通常不同於保留全部歷史更新的完整 BFGS。
例題 7.2.4
(一對數據的雙迴圈)
取 、、、。則 、,反向迴圈給 。令 ,得到 ,正向迴圈輸出 。直接由 (3) 得 ,其與 的乘積相同。因此 。
例題 7.2.5
(兩對數據重現對角牛頓步)
取 ,以及兩對 、,它們正是 的梯度變化;再令 。則 、。反向迴圈從最新的一對開始: 給出 ,接著 給出 。因此 。正向迴圈給出 及 ,再得 及 。這等於 ,正是 的精確牛頓(Newton)步;事實上 (3) 給出 及 。由於反向迴圈後 ,初始矩陣 對這個結果毫無影響。
常見錯誤
(阻尼後仍儲存原始數據對)
阻尼更新滿足的是 ,而不是 。若有限記憶的歷史儲存 而非 ,便不能重現阻尼後的矩陣;而且 的原始數據對會令 為負或無定義,(3) 的正定性論證便不再適用。在上面負曲率的例子中,應儲存的是 ,而不是 。
即使曲率為正,有限精度和極小分母仍促使實作採用明確的數值保護;以上是精確算術,沒有指定數值容許誤差。下降方向本身不能保證全局收斂:線搜索條件、目標函數假設和方向品質的控制都須另行處理。
習題與解答
快速檢查
(設 、、、。求 。)
比較 與 。
解答 · 答案
,,故 、。
快速檢查
(在一維取 、、、。計算 、、。)
這裏 。
解答 · 答案
、,所以 。因此 ,一維割線方程給出 ,與原目標 不同。
快速檢查
(設 、、、。求輸出。)
只有一對數據,所以每個迴圈只有一步。
解答 · 答案
、,所以 。接著 、,最終向量為 ;等價地,更新後的逆矩陣為 。
快速檢查
(為甚麼每個 正定,仍不能單憑此推出 ?)
考慮 與 的夾角。
解答 · 答案
對非零 ,正定性只給 ;它並不給出遠離 的方向夾角界,也不控制步長。下降法的收斂論證需要額外性質,單靠正定性不足。