最速下降法matlab程式_非線性優化方法小結-(最小二乘，梯度下降，高斯牛頓, LM)...

前言

主要摘取高博士 視覺SLAM14講裡内容，結合知乎裡一些優秀回答總結而成。

非線性最小二層

我們先考慮一個最小二乘問題：

，

是一個任意的非線性函數。如果

是個數學形式上很簡單的函數，那問題也許可以用解析形式來求。令目标函數導數為0，求解

的最優值，就和求一個二進制函數的極值一樣：

解此方程，就得到了導數為0的極值。它們可能是極大，極小或者鞍點值，隻要挨個比較它們的函數值即可。但是，這個方程是否容易解取決于

導函數的形式。

有可能是一個非常複雜的非線性方程。通常對于不友善求解的最小二層問題，我們可以用

疊代

的方式，從一個初始值出發，不斷更新目前的優化變量，使目标函數下降。具體的步驟可列寫如下：

疊代求解非線性最小二層問題

這讓求解導函數為零的問題，變成了一個不斷尋找梯度并下降的過程。直到某個時刻的增量非常小，無法再使函數下降。此時算法收斂，目标達到了一個極小，我們完成了尋找極小值的過程。在這個過程中，我們隻要找到疊代點的梯度方向即可，而無需尋找全局導數為0的情況。

接下來的問題是，增量

如何确定？ 實際上研究者們已經花費了大量精力探尋增量的求解方式(每年夠一大堆博士畢業的)。

我們将介紹兩類方法，他們用不同的手段來尋找這個增量。

一階和二階梯度法

求解增量最直覺的方式是将目标函數在

附近進行泰勒展開:

其中

是

關于

的導數(雅克比矩陣)，而

則是二階導數(海森(Hessian))矩陣。我們可以選擇保留泰勒展開的一階或二階項，對應的求解方法則為一階梯度或者二階梯度法。如果保留一階梯度，那麼增量方向為：

他的直覺意義很明顯，隻要按照反響梯度的方向前進即可。當然，我們還需要該方向上取一個步長

，求得最快的下降方式，這種方法被稱作

最速下降法。

(當然，由下圖可以看出，如果不是梯度的反方向，隻要是在梯度反方向附近(±90°範圍内)，都可以達到函數值下降的效果，怎麼選就有學問了，這就超出本文範圍了，不再展開。)

用等高線描述的二維梯度下降法

另一方面，如果保留二階梯度資訊，那麼增量方程為:

求右側等式關于

的導數并令他為零，就得到了增量的解：

牛頓法求根的逼近過程

該方法稱之為牛頓法。我們看到，一階和二階梯度法都非常直覺，隻要把函數在疊代點進行泰勒展開，并針對更新量作最小化即可。由于泰勒展開之後變成了多項式，是以求解增量時隻需解線性方程即可，避免了直接求導函數為零這樣的非線性方程的困難。不過，這兩種方法也存在它們自身的問題。最速下降法過于貪心，容易走出鋸齒路線，反而增加了疊代次數。而牛頓法則需要計算目标函數的H 矩陣，這在問題規模較大時非常困難，我們通常傾向于避免H 的計算。是以，接下來我們詳細地介紹兩類更加實用的方法：高斯牛頓法和列文伯格——馬誇爾特方法。

總結

• 一階梯度法，也叫最速下降法：

  

• 二階梯度法：也叫牛頓法：

  

高斯牛頓法(GN)

GN(Gauss-Newton)是優化算法力最簡單的方法之一。它的思想是将

進行一階的泰勒展開(注意不是目标函數

):

其中

為

在

的導數，是一個雅克比矩陣。根據前面的架構，目前的目标是為了尋找下降矢量

，使得

達到最小。為了求

，我們需要求解一個線性最小二乘問題：

這個方程與之間的有什麼不一樣呢？ 根據極值條件，我們将上述目标函數對

求導，并令其導數為零。由于這裡考慮的是

的導數而不是

,我們最後将得到一個線性方程。為此，先展開目标函數的平方項：

注意，我們要求解的變量是

，是以這是一個

線性方程組,

我們稱為增量方程，也叫高斯牛頓方程，也叫正規方程。我們把左邊系數定義為

，右邊定義為

,則上式變為：

這裡把左側記做

是有意義的，對比牛頓法。 GN用

作為牛頓法中的二階Hession. 進而省略H的過程。

求解增量方程式整個優化問題的核心所在。

如果能順利求解次方程，那麼GN算法步驟如下：

高斯牛頓法性質讨論

從算法步驟可以看到，增量方程的求解占據着主要地位。原則上，它要求我們所用的近似H矩陣是可逆的，但實際資料中計算得到的

卻隻有半正定性。也就是說，在使用GN時，可能出現

為奇異矩陣的情況，此時增量穩定性較差，導緻算法不收斂。更嚴重的是，計算我們假定H非奇異，如果求出來步長

太大，也會導緻我們采用的局部近似不夠準确。

盡管GN有這些缺點,但是它依然值得我們去學習，因為在非線性優化裡，相當多的算法都可以歸結為GN的變種。這些算法都借助了GN的思想并修正GN的缺點。例如一些線搜尋方法(line search method)，這類改進就加入了标量

，在确定了

進一步找到

使得

達到最小，而不像GN那樣簡單的令

。

Levenberg-Marquadt

LM方法在一定程度上修正了這些問題，一般認為它比GN更為魯棒。盡管它的收斂速度可能比GN慢，被稱之為

阻尼牛頓法.

由于GN中采用近似的二階泰勒展開隻能在展開點附近有較好的近似效果，是以我們很自然的想到應該給

添加一個信賴區域(Trust Region)，不能讓它太大使得近似不準确。非線性優化有一系列這類方法，這類方法也被稱之為

信賴區域方法

(Trust Region Method)。在信賴區域裡面，我們認為近似是有效的，出了這個區域，近似可能會出問題。

那麼如何确認這個信賴區域的範圍？一個比較好的方法是根據我們的近似模型跟實際函數之間的差異來确定。如果差異夠小，我們讓範圍盡可能大。如果差異大，我們就縮小這個近似範圍。是以，可以考慮使用

來判斷泰勒近似是否夠好，

的分子式實際函數下降的值，分母是近似模型下降的值。如果

接近于1，則近似是好的。如果

太小，說明實際減小的值遠少于近似減少的值，這認為近似比較差。反之，如果

比較大，則說明實際下降的比預計的更大，我們可以放大近似範圍。

于是，我們建構一個改良版的非線性優化架構，該架構比GN有更好的效果：

LM算法

這裡近似範圍擴大的倍數和門檻值都是經驗值，可以替換成别的數值。在6.24裡，我們把增量限定于一個半徑為

的球中，認為隻在這個球内才是有效的。帶上

之後，這個球可以看成一個橢球。在Levenberg提出的優化方法中，把

取成機關陣

，相當于直接把

限制在一個球内。随後Margaurdt提出将

取成非負對角陣，實際中通常用

對角線元素的平方根，使得在梯度小的次元上限制範圍更大一些。

不論如何，在LM中，我們都需要解6.24那樣的一個子問題來獲得梯度。這個子問題是帶不等式限制的優化問題，我們用Largrange乘子将它轉化為一個無限制優化問題：

這裡

為Lagrange乘子。類似于GN的做法，把它展開後，我們發現該問題的核心仍是計算增量的線性方程：

可以看到，增量方程相比于GN, 多了一項

。如果考慮它的簡化形式，既

，那麼相當于求解：

我們看到，當參數

比較小時，

占主要地位，這說明二次近似模型在該範圍内是比較好的，LM方法更接近于GN法。另一方面，當

比較大時，

占主要地位，LM更接近于一階梯度下降法，這說明附近二次近似不夠好。LM的求解方法可以一定程度避免線性方程組的系數矩陣非奇異和病态問題，提供更穩定更準确的增量

.

在實際中，還存在許多其他方式來求解函數增量，例如Dog-Leg等。我們在這裡所介紹的，隻是最常見而且最基本的方式，也是視覺SLAM 中用的最多的方式。總而言之，非線性優化問題的架構，分為Line Search 和Trust Region 兩類。Line Search 先固定搜尋方向，然後在該方向尋找步長，以最速下降法和Gauss-Newton 法為代表。而TrustRegion 則先固定搜尋區域，再考慮找該區域内的最優點。此類方法以L-M 為代表。實際問題中，我們通常選擇G-N 或L-M 之一作為梯度下降政策。

參考

1. 高翔， 視覺SLAM十四講
2. METHODS FOR NON-LINEAR LEAST SQUARES PROBLEMS 2004
3. https://zhuanlan.zhihu.com/p/33162840
4. https://zhuanlan.zhihu.com/p/113946848