精確線搜索只在當前直線上選最好的位置,並非一次找出未來所有步驟的最佳路徑。在狹長的二次函數等高線上,新的負梯度可能再次橫越谷底。我們可以定量分析這現象,而不必假設算法有限步終止。
方法與幾何
設 為實對稱正定的 矩陣,定義
定義 3.2.1
(二次函數上的精確最速下降法)
目標值差為 。若 ,便停止:此時 。否則,精確最速下降法取
分母是正數。沿直線對目標函數求導,可見 是所有實步長中唯一的最小化步長,而且為正。又因 ,所以 。連續梯度在歐氏內積下正交,但這本身既不保證它們 -共軛,也不保證新梯度為零。
精確下降界
定理 3.2.2
(正定二次函數的精確線搜索收斂率)
假設 的特徵值均在 內,其中 ,並設 。每個尚未終止的精確最速下降步都滿足
在精確算術下,重複 步所得的界為初始差乘以 。若 ,一步便到達最小點。
證明
(由譜界推導下降因子)
暫略迭代下標,設 。把精確步長代入二次式,得到
除以初始目標值差,得到比值
要控制分母,將 在 的一組標準正交特徵向量基底展開。令 為各係數的平方除以 ,則 。每個 均滿足
因為 。令 、,取加權平均可得 。由 ,有 ,因此
代入比值,並用 ,便得所述因子。反覆應用單步不等式;若已終止,其後保留最小點。當 時,對稱性給出 ,精確步長是 。
證明透視
譜區間在哪裏起作用
證明分為兩個獨立部分。第一部分是精確恆等式:一步下降量 只用到步長沿直線最小化以及 ,不涉及任何特徵值界。譜只在第二部分出現,即界 。其關鍵一步是 上的逐點不等式 :它對權重 是線性的,所以取平均後仍成立;再用初等不等式 ,把和的界轉為積的界。兩個不等式同時取等號,當且僅當權重只落在兩個極端特徵值上且各為 ,所以這個界是精確的。正定性貫穿全程,因為要除以 ,須有 。
這個界衡量的是目標值差,不是歐氏誤差或殘差範數。它使用極端特徵值;實際下降可以快得多。 大會令最壞情況的因子接近一,但不代表每個起點都收斂緩慢。
精確算出最壞情況路徑
例題 3.2.3
(正交梯度與反覆的鋸齒路徑)
取 、、。此時 、、,故
初始目標值為 ,下一個為 ,比值 正好等於 、 時的 。下一步的步長也為 ,而 。因此路徑以縮小的尺度重複:精確線搜索不會在兩步內解出這個二維問題。雖然 ,卻有 ,兩個搜索方向並非 -共軛。
例題 3.2.4
(最壞情況何時恰好出現)
證明顯示了在 時比值何時等於 。 取等號,迫使每個帶正權重的特徵值都是 或 。記其權重為 ; 取等號要求 ,即
因此 :梯度沿 的一個特徵向量與沿 的一個特徵向量的分量平方相等,其他方向沒有分量。對 ,這就是 ;上面的 與 都是這種形式,所以那條路徑的每一步都達到上界。
例題 3.2.5
(勝過上界的起點)
仍取 、,並取 。則 、、、,故
驗算:下降量為 。比值為 ,遠低於 ,因為梯度分量的平方 與 相差甚遠。
反例模式
條件數大不代表必然收斂緩慢
沿用同一個 ,但取 ,梯度是特徵向量。使目標函數最小的步長為 ,故 。條件數描述最壞情況的保證,並不是每個初始誤差實際觀察到的速度。本定理亦不能用於負定 Hessian:例如 在 沿負梯度的直線限制無下界,所以精確線上最小點不存在。
下面的互動圖以精確分數執行精確最速下降法,並把每步的比值 與 比較:在 上從 出發恰好達到 ,從其他起點出發則更好。
常見錯誤
常見錯誤
(精確線搜索不會在 n 步內終止)
連續梯度互相正交,容易令人以為像共軛方向那樣在 步後終止。第一個例題否定了這點:在二維問題上,路徑以 的比例無限重複,因為 。
常見錯誤
(收斂率針對目標值差,而非誤差)
定理收縮的是 ,其中 。由於 ,歐氏誤差只滿足 ;若對 只寫 ,便漏掉因子 。
練習與解答
快速檢查
(若 是 的特徵向量,特徵值為 ,求 和 。)
解答 · 答案
,,一步便到達二次函數的唯一最小點。
快速檢查
(若 、,初始目標值差為 ,求三步後的上界。)
解答 · 答案
,所以目標值差至多 ;實際值可以更小,甚至已為零。
快速檢查
(設 、、。它們是否歐氏正交?是否 -共軛?)
解答 · 答案
,但 ,所以不是 -共軛。