優化算法小結

對比梯度下降，牛頓法，高斯牛頓

梯度下降

實質是使用了雅克比矩陣(一階導數矩陣)

優點：簡單，

缺點：1、取得的是極小值，是以隻有在凸函數上才可能找到全局最小。

2、與初始值設定有關，若初始值選取不當，需要疊代很多次

3、與步長有關，步長設定不當可能會形成震蕩

4、收斂較慢

牛頓法

實質是在梯度下降的基礎上進一步考慮了二階項，即Hessian矩陣(二階導數矩陣)。

通俗的說，牛頓法疊代優化時既利用了梯度，又利用了梯度變化的速度（二階導數）的資訊。

缺點：高次元下計算Hessian矩陣需要消耗很大的計算量，很多時候無法計算。

注：在牛頓法中，Hessian矩陣可逆且正定。

高斯牛頓法

高斯牛頓法在牛頓法基礎上解決Hessian矩陣難計算的問題。思想是用雅克比矩陣的乘積近似代替Hessian矩陣。即J(x)TJ(x)

缺點：1、這樣近似的矩陣一般不滿足Hessian矩陣正定且可逆，會導緻穩定性很差，算法不收斂。

2、隻可在小範圍内近似，若步長選取較大，近似将不再準确，導緻算法不收斂。

LM算法

在高斯牛頓法基礎上進一步優化，使用J(x)TJ(x)+uI(I是機關陣)來近似Hessian矩陣。其中u是一個非負可變量。如果 u 取值較大時，uI 占主要地位，此時的LM算法更接近一階梯度下降法，說明此時距離最終解還比較遠，用一階近似更合适。反之，如果 u 取值較小時，H 占主要地位，說明此時距離最終解距離較近，用二階近似模型比較合适，可以避免梯度下降的“震蕩”，容易快速收斂到極值點。是以參數 u 不僅影響到疊代的方向還影響到疊代步長的大小。

LM采用的搜尋方法是信賴域（Trust Region）方法，和梯度下降、牛頓法、高斯牛頓法采用的線性搜尋（Line Search）方法不同。

為什麼要用信賴域呢？這是因為高斯牛頓法中采用近似二階泰勒函數隻在展開點附近有較好的近似效果，如果步長太大近似就不準确，是以我們應該給步長加個信賴區域，在信賴區域裡，我們認為近似是有效的，出了這個區域，近似會出問題。

LM算法比高斯牛頓法更加魯棒，但收斂速度變慢。