局部模型為何需要保障?
牛頓(Newton)法在目前位置最小化一個二次模型。設 二次連續可微,記 、。若 正定,則
的唯一極小點為 。在非退化極小點附近,這方向十分有效;離得遠時,對小位移準確的模型卻未必能預測完整步長的結果。線搜尋保留方向,利用真正的函數值檢查步長。
下文的「全局收斂」指在所列假設下,由任意起點出發,梯度趨於零;這並不表示找到全局最小值。「局部二次收斂」則描述足夠接近合適極小點時的更快速收斂。第一項結論本身不保證迭代點收斂至某個駐點。
下降方向與 Armijo 條件
定義 1.8.1
(回溯線搜尋)
選定 、。給定 和滿足 的方向 ,先取 。只要
尚未成立,就把 換成 。接受第一個通過測試的步長,並令 。式 (1) 稱為 Armijo 充分下降條件。
因右邊嚴格小於 ,接受的步驟必定降低函數值。條件要求取得線性項預測下降量的 倍,而非整個二次模型的預測量。若 且 對稱正定,則 滿足 ,確為下降方向。若 ,應停止;此時嚴格下降條件不適用。
定理 1.8.2
(回溯必定終止)
若 的梯度在 上為 -Lipschitz,,且 ,則回溯必定終止。事實上,只要
就滿足 (1)。
證明
(沿射線的二次上界)
沿線段積分梯度,再利用 Lipschitz 不等式,得到
當步長不大於上述界時,後兩項之和至多為 。由於 ,測試的步長最終必小於這個正數。這只是充分界,並非聲稱所有較長步驟都會失敗。
全局駐點保證
定理 1.8.3
(一致正定牛頓矩陣下的梯度收斂)
設 的梯度為 -Lipschitz,並在初始水平集 上有下界。假設存在常數 ,使所有 滿足
在每個非駐點使用牛頓方向與固定 的 Armijo 回溯,則迭代或於有限步到達駐點,或滿足 。
這些 Hessian 界是強假設,不能單憑極小點存在便斷定成立。它們令方向在整個水平集內受到一致控制。單說每一步均使 下降並不夠:每次下降可能太小,總下降量有限時梯度仍可能很大。
證明
(一致下降量與可求和級數)
每次接受的步驟都下降,故迭代點留在 。由特徵值界可得
因此上一個定理的充分步長界至少為 。若 ,第一個步長已被接受;否則,第一個被接受的步長大於 ,除非它本來就是 1。所以所有接受步長均滿足 。Armijo 條件給出
從 加至 後,左邊相消,且至多為 。故 ,其非負項必趨於零。
證明透視
每個假設換來哪一個不等式
論證把每步的下降轉化為一致的下降,而每個假設都花在一個環節上。上界 使牛頓方向夠陡,;下界 使它不太長,。兩者連同 Lipschitz 常數,在可接受步長之下放了一個與 無關的下限 ;以固定因子 回溯,至多越過這個下限一個因子,於是得到 。Armijo 條件再把下限變成與 成正比的下降量。單調下降還用了一次:保證每個迭代點都留在 Hessian 界成立的 內。收結的一步是相消求和:有下界使總下降量有限,所以 可求和。去掉 ,下限可能崩潰;去掉有下界,總和未必有限。
證明用到精確求解線性方程。若以近似方向代替,仍須另證相應的下降及長度界;不定 Hessian 和信賴域方法也需要各自的保障,不能直接套用此定理。
何時恢復完整牛頓步?
定理 1.8.4
(嚴格極小點附近的完整步與二次收斂)
設 為駐點, 正定,Hessian 在其鄰域內為 Lipschitz,並取 。則對每個充分接近 的 ,回溯在每一步都接受 ,而迭代二次收斂至 。
證明
(三次餘項最終被壓倒)
當 充分接近 時,Hessian 仍一致正定。令 ,由二階展開,
由 至少是 的正倍數,當 夠小,三次餘項小於 ,完整步便通過 (1)。要求 是為餘項留出空間;它是充分條件,並非對每個函數都必要。
為分析速度,記 。由梯度的積分式及 ,
逆矩陣在局部有界,加上 Hessian 的 Lipschitz 條件,得到 。因此起點足夠接近時,迭代留在該鄰域,使用完整步並二次收斂。全局梯度收斂結論本身不保證迭代進入此鄰域。
證明透視
為甚麼完整步會被接受,之後誤差又會平方
證明分成兩個互不依賴的部分。接受性:由於 ,二次項恰好抵消線性項的一半,,所以實際下降量是線性預測下降量的一半,只差一個由 Lipschitz Hessian 控制的三次餘項。在 附近的正定性使 與 同階,而 留出的餘量 在 足夠小時吸收這個餘項。收斂階:誤差恆等式把 寫成 乘以大小為 的 Hessian 之差作用在 上。論證以歸納收尾:一旦 ,下一個迭代點更近,兩部分便可再次應用。全局定理的假設一個也沒有用到。
常見錯誤
(選取 卻期望完整步)
限制 並非裝飾。對 ,完整牛頓步恰好落在極小點,,而 。取 的 Armijo 條件要求 ,這不成立,所以精確的一步被拒絕。接著 被接受,因為 ,迭代變成 :在二次函數上也只有線性收斂。
必須縮短的步長
例題 1.8.5
(指數目標函數)
取 、、、。由 、,唯一極小點為 。牛頓方向為
完整步到達 ,函數值大幅上升。取 時,,,雖低於 ,卻大於 Armijo 右邊約 ,故僅有下降並不足夠。取 ,則 、,右邊約為 ,所以接受。此函數的梯度在整個 上並非 Lipschitz,因此不能直接引用以上所述的全局定理處理此例。
常見錯誤
(接受任何下降)
上例取 時, 確實由約 降至 。接受這類步驟,無法得到以 表示的下降量下界,而這正是駐點證明所需;Armijo 拒絕它,因為它達不到所預測線性下降量的四分之一。
例題 1.8.6
(靠近極小點時完整步接手)
從已接受的點 起改用完整步。此時牛頓更新為 。在 ,完整步給出 ,低於 Armijo 右邊約 ,所以接受 ,其後的完整步亦全被接受。迭代約為
比值 約為 、、 及 :每步誤差都被平方,常數趨於 。全局階段只需縮短一次步長,之後便由局部定理描述。
例題 1.8.7
(強凸目標函數的一致步長下限)
令 。在整個 上 ,故 、,且 為 -Lipschitz; 有下界 。取 、,證明給出 及 ,因此保證下降至少為 。從 起:、、。完整步給出 、,低於 Armijo 右邊 ,所以接受 。實際下降 遠大於保證的 :定理的常數保證收斂,而非速度。
反例模式
下降方向的論證不能省掉正定性
令 ,在 有 、。牛頓方程給出 ,因此 ,這是上升方向。當正的 充分小時,,而 Armijo 右邊也高於 。下降方向下的終止證明不適用。取 時,回溯迴圈其實永不停止:,而 在 取得的最小值約為 ,所以對每個 都為正。算法必須偵測或修正這類方向。
練習與解答
快速檢查
(設 、、,求牛頓方向並測試 。)
比較 與 。
解答 · 答案
、,所以 。新函數值是 0,而 Armijo 右邊為 ,故接受完整步。
快速檢查
(若對稱矩陣 的特徵值均在 ,其中 ,證明 。)
使用 。
解答 · 答案
正交對角化 ; 的特徵值均在 ,故 。
快速檢查
(為何 下降且有下界,仍不足以推出 ?)
想想函數值收斂對每次下降量說明了甚麼。
解答 · 答案
函數值收斂只能推出相鄰兩步的下降量趨零;若沒有把下降量和 聯繫起來的下界,無法斷言梯度趨零。例如 、,函數值下降且有下界,但梯度恆為 1。此例只說明邏輯缺口,並非滿足定理的牛頓序列。
快速檢查
(設 、。完整牛頓迭代如何?)
計算 。
解答 · 答案
,故 、,但 沒有有限極限, 亦沒有駐點。沿序列的 Hessian 沒有一致正下界;梯度收斂不自動代表迭代點收斂。