從一步學習曲率
Newton 方向解方程 ,其中 。當 Hessian 昂貴時,擬 Newton 法改為保存其逆的對稱近似 ,取 。只要 正定且 ,這就是下降方向。我們希望利用已計算的梯度改進 。
設 、。若目標是 Hessian 為 的二次函數,則 ,真正的逆滿足 。更新要求新近似重現這次觀察到的作用,對非二次函數亦如此。
定義 7.4.1
(割線方程與 DFP 更新)
設 、。若矩陣 滿足 ,稱它滿足割線方程。若 ,稱向量對 滿足曲率條件。對對稱正定矩陣 及這樣的向量對,Davidon–Fletcher–Powell(DFP)更新為
割線方程不能決定整個矩陣:一個方向的觀察無法揭示全部曲率。曲率條件確保 非零,兩個分母皆為正;它是對實際使用的向量對的條件,並非單由 正定得出。
定理 7.4.2
(割線方程與正定性)
若 對稱正定且 ,則 (1) 所得 對稱正定,並滿足 。
證明
(代入與加權 Cauchy–Schwarz 不等式)
(1) 的三項都是對稱矩陣,所以 對稱。把 (1) 乘以 ,得
對任意非零 ,
由於 正定, 是內積,Cauchy–Schwarz 不等式給出 ,且等號恰在 與 平行時成立。因此方括號非負;若 不是 的倍數,方括號嚴格為正,而最後一項非負,所以 。若 且 ,方括號為零,最後一項等於 。兩種情況涵蓋所有非零 ,故 正定。
證明透視
減去一項後為何仍正定
證明把非零向量分成兩種情況,每個假設各司其職。 的正定性用於方括號:它使 成為內積,於是在通過 的直線以外,Cauchy–Schwarz 不等式嚴格成立。在這條直線上,減去的一項抵銷了 的全部貢獻,這正是它的用途: 必須忘記舊的作用 。那裏只剩下新加的一項,曲率條件就用在這一項上。取 可見這條件亦是必要的,因為 ;若 ,方向 本身就證明 不正定。論證之所以閉合,是因為兩種情況窮盡一切,而不是因為某一項佔優。
此更新移除舊矩陣在 方向的作用 ,換成 。它不一定保留每個先前的割線方程;以上證明也沒有保證迭代收斂或整個矩陣的準確度。
常見錯誤
(把逆矩陣更新用於 Hessian 近似)
公式 (1) 更新的是逆 Hessian 的近似 ,並強制 。若把同一公式用於 Hessian 本身的近似 ,強制的是 ,這是錯誤的割線方程;Hessian 近似必須滿足 。在 (1) 中互換 與 的角色,得到 ,這是另一個更新( 的 BFGS 公式),而不是以 寫出的 DFP 更新。
完整計算一步
例題 7.4.3
(二維二次函數)
令 、、。則 ,。精確線搜索最小化 ,其導數 在 為零。因此
由 ,公式 (1) 給出
直接相乘可驗證 。其行列式為 ,第一個對角元素為正,與定理一致。它尚不是真正的逆 :割線方程只約束矩陣在 上的作用。
從 繼續,可以看到第二次觀察帶來甚麼。
例題 7.4.4
(同一二次函數的第二步)
在 處梯度為 ,而
沿 , 的導數為 ,所以精確線搜索到達 ,即最小點。新向量對為 、,且 、、。於是
每個元素都以公分母 核對。在這個例子中,兩次精確線搜索步到達最小點,而 正是真正的逆 Hessian,所以它亦滿足第一個割線方程 。這只是對此二次函數的計算;本頁沒有證明一般的有限步終止定理。
曲率從何而來
若 在整條步長線段上二次連續可微,微積分基本定理給出
因此,非零步長沿線若有一致正曲率下界,便有 。另一條途徑是弱 Wolfe 曲率條件。
命題 7.4.5
(弱 Wolfe 條件給出可用的向量對)
設 、、,且 。若 ,則
證明
(兩個方向導數相減)
由 及 ,
其中不等式就是曲率條件,最後的等式用到 。三個因子都為正。
這計算假設符合條件的步長存在且被接受,並未證明線搜索必定終止。
例題 7.4.6
(一維情況:更新忘記舊值)
在一維中,(1) 化為 ,與所用的正數 無關。取 ,則 ;設 、、,試探步長 。於是 、。取 ,曲率條件成立,因為 。此時 、、,大於命題的下界 。因此 ,即 在 上平均斜率 的倒數。它不是 :割線向量對記錄的是沿步長的平均曲率,而不是新點的曲率。
反例模式
割線向量對的符號可能不合要求
取 、、;這一步令 由 降至 。由 得 、,所以 。一維割線方程迫使 ,因此沒有正定更新可滿足它。單靠下降並不提供曲率:實際方法必須處理這類向量對,例如跳過或修改更新;這些做法需要另行分析。
練習與解答
快速檢查
(若 、、,由 (1) 求 。)
把數值代入 (1) 的三項。
解答 · 答案
,與割線方程要求的 相同。
快速檢查
(若 ,對稱正定的 能否滿足 ?)
把割線方程左乘 。
解答 · 答案
只有退化情況 可以。若 ,則 ,矛盾;若 ,割線方程迫使 ,不提供曲率資訊。
快速檢查
(若 、、,可得 甚麼下界?)
運用關於弱 Wolfe 條件的命題。
解答 · 答案
;實際接受的步長可能得到更大的值。
快速檢查
(二維中若 , 是否必等於產生此向量對的二次函數的真正逆 Hessian?)
比較第一個例題中的兩個矩陣。
解答 · 答案
不必。在第一個例題中, 與 都把 映到 ,但兩者不同。要決定矩陣,需要額外觀察與假設。