最佳化 | 數值最佳化（2）——線搜尋：步長選取條件的收斂性
文章須知
文章作者：學弱猹
稽核編輯：阿春
微信編輯：玖蓁
本文轉載自公眾號 學弱猹的精品小屋
（ID：cha-diary）
原文連結：數值最佳化（2）——線搜尋：步長選取條件的收斂性
作者：學弱猹
編者按
在上篇文章，我們簡單的介紹了數值最佳化中線搜尋方法的思想和步長條件。那麼這一節，我們更多的開始關注這些步長條件的理論性質，學最佳化最忌知其然，不知其所以然，所以我們需要我們幫助我們理解為什麼給定的步長條件可以匯出的一些好的，有助於最佳化的收斂性。
上一節筆記傳送門：數值最佳化（1）——引入，線搜尋：步長選取條件
大家好！
在上一節，我們簡單的介紹了數值最佳化中線搜尋方法的思想和步長條件。那麼這一節，我們更多的開始關注這些步長條件的
理論性質
，學最佳化
最忌知其然，不知其所以然
，所以我們需要我們幫助我們理解為什麼給定的步長條件可以匯出的一些好的，有助於最佳化的收斂性。
那麼我們開始吧。
目錄
線搜尋的全域性收斂性
理論好用的B-N條件
聯絡步長與搜尋方向的Zoutendijk條件
全域性收斂性的證明
Case：最速下降法的區域性收斂性
線搜尋的全域性收斂性
我們在上一節有簡單說明各種步長選取條件和它們的來源思想。事實上，上一節的幾個反例也說明了，如果我們不能夠很好的選取步長，那麼最後的收斂結果就不會是
駐點所在的位置
，這不是我們希望看到的。也是因為這個，我們需要保證我們的步長具有
全域性收斂性
。換句話說，我們希望我們的最佳化方法，
在給定步長條件下，能夠收斂到駐點
，這就夠了。要說明這件事並不容易，我們會接觸到大量的性質和定理。
理論好用的B-N條件
在說明這一件事之前，我們先要關心的是
步長的存在性
。存在即合理，不存在就啥也不是。
還有一個條件在哪裡呢？還記得我們如何
圖解Wolfe條件
的嗎？我們再把這張圖放出來
好的，我們現在已經證明了步長的存在性，是不是可以證明全域性收斂性了呢？不好意思，
依然不行
。這是因為我們的條件雖然已經足夠讓我們進行實操，但是我們的這兩個條件
在理論上不是很好用
。為了彌補這個缺陷我們又提出了一個
理論上好用
的步長選取條件。
我們說它“理論上好用”，意思是說我們會希望透過它來證明我們想得到的
全域性收斂性
。也就是說，我們只是把它當作一個工具，而實戰中我們還是使用A-G或者Wolfe條件。有的人會問，實戰和理論使用的不是一套工具，不會出問題嗎？答案確實是不會。這就是我們接下來要說明的事情。
這個證明是比較複雜的，這是因為我們要考慮到步長選取的任何一個情況，因此我們要假設存在一個滿足條件的步長和一個不滿足條件的步長，而
不能夠對步長本身施加任何的假設
。而且要注意的問題是，對於初始步長的情況，初識步長的“前一步步長”是否是可接受的，實際上是未知的，因此
不能夠直接套用之後那一部分的證明
。但是你也能看出來，這個式子就說明了，如果我們的導函式性質足夠好（因為LIpschitz連續是一個很強的條件），是足夠推出B-N條件的。為了使得B-N條件的普適性得以使用，我們確實花了不少功夫。
接下來我們來看看Wolfe條件的情況。
聯絡步長與搜尋方向的Zoutendijk條件
全域性收斂性的證明
有了這個Zoutendijk條件之後，其實我們下一步要考慮的就是如何利用Zoutendijk條件告訴我們的資訊，來推出全域性收斂性。
為了讓大家信服，我們最後再把證明寫一遍。
而且我們已經做了那麼多的準備工作，如果不能夠證明全域性收斂性，也不可能直接把演算法放出來，對吧？
接下來，我們考慮一下Zoutendijk條件。注意到我們的求和式子蘊含兩個元素：
夾角和梯度模長
。那麼換句話說，如果有一個有下界，另外一個就必須趨於0（否則級數不可能有限）。因為這個我們可以來考慮一下夾角的性質。注意到
第一個式子其實就是我們的Rayleigh商，可以參考
https：//
zhuanlan。zhihu。com/p/52
476330
中的Proposition 1，它的最小值對應的就是矩陣
的最小特徵值，也是最小奇異值（因為矩陣對稱正定）。而第二個式子事實上與矩陣範數的定義有關，也就是說
而我們的模長都是2-範數，對應到矩陣上就是最大奇異值。綜合來看，我們可以得到
這是因為矩陣的條件數就是。到此我們的就說明了夾角是存在下界的，也就是說無論我們的迭代進行到哪一步，我們的方向都
不會與負梯度方向垂直
。
Case：最速下降法的區域性收斂性
我們用這個問題來結束我們這一節。
首先當然要關心的是
全域性收斂性和區域性收斂性到底有什麼區別
？全域性收斂性關注的是收斂性，也就是說，
給定任何的初始點，演算法都能收斂到一個駐點
。但是區域性收斂性更多的關注的是
收斂速度
。也就是說初始點不能任意選取。而在這裡我們就要給出最速下降法的一個區域性收斂性質。
也就是說，我們這裡的海塞矩陣的正定性
只在一個小區域上滿足
，並且這個正定性的要求還很高。因此梯度下降法是非常依賴一個函式的海塞矩陣的性質的。
我們證明一下這個結論。既然左邊的式子相當於是一個函式差，題目中又有比較明顯的海塞矩陣的提示，那麼我們自然考慮Taylor展開，也就是說有
小結
在這一節，我們層層推進，一切以證明收斂為目標，匯出了一系列的結論。這一節也算是為最佳化的理論性正名了。事實上，看完這一節，你就會明白，為什麼搜尋方向不可以標準化，為什麼梯度下降不僅僅是隨便選一個大/小的步長那麼簡單。當然，如果你只是關心線搜尋方法的真正的實現，那麼這一節並沒有什麼作用（下一節就會很有作用）。但是反過來說，
授之以魚，不如授之以漁
。如果你不知道這個工具怎麼用，那麼你就很難說會在工具出問題的時候，發現它真正的缺陷。