從零開始學習「張氏相機標定法」（四）優化演算法前傳

前一篇說到LM優化演算法。在介紹LM優化演算法前，得先說說它是怎麼一步步發展來的。因此，優化演算法部分的介紹順序是：梯度下降、牛頓法、高斯牛頓法、LM法。

一般待優化的目標函數都是由誤差的平方和組成，也就是我們常見的最小二乘問題：

這裡的 f 一般是非線性函數。我們在微積分課程里學過，如果想要求目標函數的極值（可能是極大值、極小值或者鞍點處的值），可以通過令目標函數的導數（如果可導）為零，求解析解得到。但是實際應用中函數 f 一般是非常複雜的非線性函數，沒有解析解。所以一般最常用的優化方法就是迭代求解。

如何迭代呢？

迭代求解

以迭代求解極小值為例（如果求極大值，在前面加個負號轉化為求極小值問題）。通用的方法就是先給定一個初值 θ0，對應目標函數值為 f(θ0)，這個初值可以是經驗估計的或者隨機指定（隨機的話收斂會慢一些），然後我們改變（增大或減少） θ0 的值，得到一個新的值 θ1，如果 f(θ1)<f(θ0)，那麼說明我們迭代的方向是朝著目標函數值減小的方向，離我們期待的極小值更近了一步，繼續朝著這個方向改變 θ1的值，否則朝著相反的方向改變 θ1的值。如此循環迭代多次，直到達到終止條件結束迭代過程。這個終止條件可以是：相鄰幾次迭代的目標函數值差別在某個閾值範圍內，也可以是達到了最大迭代次數等。我們認為迭代終止時的目標函數值就是極小值。

因此迭代的一般過程如下：

1、對於目標函數 f(x)，給定自變數某個初始值x0。這個初值可以是經驗估計的或者隨機指定。

2、根據採用的具體方法（梯度下降、牛頓、高斯牛頓、LM等）確定一個增量△xk

3、計算目標函數添加了增量後的值如下

4、如果達到迭代終止條件（達到最大迭代次數或函數值/自變數變化非常小），則迭代結束，可以認為此時對應的目標函數值就是最小值。

5、如果沒有達到迭代終止條件，按如下方式更新自變數，並返回第2步。

因此，不同的優化演算法的不同主要體現在增量的更新方式上。如果採用不合適的更新方式，其實很容易陷入局部最小值。這裡給出一個關於局部最小值和全局最小值的直觀的理解。如下圖所示：

通常我們希望迭代得到的是全局最小值（只有一個）而不是局部最小值（可能有多個）。下圖表示的是不同初始值對迭代結果的影響。如果我們初值設的是紅色的θ0，最後找到的極小值位於 θ∞，在這個例子中它是全局最小值。但是如果我們初值設的是藍色的 θ0，最後我們找到的極小值位於 θ∞，顯然只是局部最小值，不是全局最小值。

實際上按照上述迭代方法，很多時候我們找到的所謂「全局最小值」其實只是局部最小值，這並不是我們期望的。有沒有保證局部最小值一定是全局最小值的情況呢？

答案是有，當然這就需要對目標函數有一定的限制。如果我們的目標函數是凸函數，那麼可以保證最終找到的極小值就是最小值。很多人可能忘記了什麼是凸函數，下面簡單介紹一下。

凸函數的概念

凸函數（convex function）在優化演算法中是一個非常重要的概念，其定義如下：

如果上面定義沒有看懂也沒關係，我們可以發現，凸函數其實就是一個「碗」狀曲線，碗口向上。下圖列舉了幾種凸函數和非凸函數的例子。如果一個函數是凸函數，那麼它只有一個極小值點，也就是最小值點，從下圖中也可以看出來。下圖從左到右從上到下分別展示了：只有一個極小值的凸函數、只有一個極小值的非凸函數、有多個極值的非凸函數、加了噪音的非凸函數。

如何判斷一個函數是否是凸函數？

對於一元二次可微函數，如果它的二階導數是正的，那麼該函數就是嚴格凸函數。對於多元二次可微函數，當它的Hessian矩陣（不懂沒關係，後面會講）是正定的時候，就是嚴格凸函數。好了，凸函數就介紹這麼些，對凸函數做個總結吧。

1、如果一個函數是凸函數，那麼它有且只有一個極值點，且這個極值點是最值點。

2、幾個非負凸函數的和仍然是凸函數。

3、如果一個函數不是凸函數，那麼它可能只有一個極值點，也可能有多個極值點（局部極值點和全局極值點）

凸函數講完了，我們繼續說說迭代求解最小值法。從最簡單易懂的梯度下降法說起。

梯度下降（Gradient Descent）法

先來假設一個場景：一個人去探險被困在一座山上的某個位置，他必須趕在太陽下山之前回到山底的營地，否則會有危險。但是他對這座山不熟悉，而且視野有限無法看清哪裡是山底，時間不多了，因此他必須採取比較激進的最快下山路線。由於可視距離有限，比如說10米。那麼他需要以當前位置（坐標x0）為中心，以10米為半徑尋找周圍最陡峭的路（假設沒有障礙），盯著這條10米長的路終點（坐標x1）走，當走到坐標為x1位置時，需要重新觀察以當前位置為中心，以可視距離10米為半徑區域重新尋找最陡峭的路，盯著這條路的終點（坐標x2）走，如此往複，那麼最終他能夠走到山底嗎？

上述過程就是梯度下降法的實例。梯度下降法是求解無約束優化問題最簡單和最古老的方法之一，雖然現在已經不具有實用性，但是許多有效演算法都是以它為基礎進行改進和修正而得到的。

梯度下降法，其本質是一階優化演算法，有時候也稱為最速下降法（Steepest Descent）。與其對應的是梯度上升法(Gradient ascent)，用來求函數的極大值，兩種方法原理一樣，只是計算的過程中正負號不同而已。本文後續都是以梯度下降法為例進行介紹。

在微積分里，對函數求導數（如果是多元函數則求偏導）得到的就是梯度。具體來說，對於函數 f(x,y)， 在點 (x0,y0)，沿著梯度向量的方向就是(?f/?x0, ?f/?y0)，它的方向是 f(x,y) 增加最快的方向。或者說，沿著梯度向量的方向，更加容易找到函數的極大值。反過來說，沿著梯度向量相反的方向，也就是 -(?f/?x0, ?f/?y0) 的方向，梯度減少最快，也就是更加容易找到函數的極小值。

以一元函數為例，假設目標函數為F(x)，梯度的符號為?，那麼在梯度下降中，自變數x每次按照如下方式迭代更新：

其中 λ 稱為步長或者學習率。按照上述方式迭代更新自變數，直到滿足迭代終止條件，此時認為自變數更新到函數最小值點。下圖是梯度下降法的示意圖。

梯度下降法看起來很好，但是在具體使用過程中，會存在不少問題。

問題1：初始值選取

如下圖所示，是二維函數優化的一個例子，不同顏色表示不同高度。我們初始值在藍色的加號位置，最小值位於綠色的加號位置。圖中展示了從不同的初始值開始迭代所需要的迭代次數，可以看到不同初始值會產生非常大的差異。(a) 圖只經過5次迭代就收斂了， (b) 圖經過了22次迭代才 收斂。

那麼 (b)圖裡究竟為什麼會多出那麼多次的迭代呢？將局部細節放大後如下圖所示，這部分「鋸齒」狀的震蕩式下降是因為它經歷了一個高度逐漸下降的「山谷」，而每次下降方向都與上一次垂直。換句話說，這種下降方式太「短視」，只關注了一個極小範圍內的變化，而忽略了長遠的趨勢（牛頓法就是根據這點進行的改進，具體見後介紹），並不是一種「平滑」的下降。

既然初始值影響這麼大，那麼一般採用隨機多次選取初始值進行多次迭代，然後將多次迭代結果進行比較，找出其中最小的那個作為最小值。這樣會導致計算量急劇變大，最終確定的值也不能保證最小，並且因為隨機選取，會導致每次最小值都不同，結果不穩定。

問題2：步長選取

步長，就是每一步走多遠，這個參數如果設置的太大，那麼很容易就在最小值附近徘徊；相反，如果設置的太小，則會導致收斂速度過慢。所以步長的選取也是一個非常關鍵的因素。

總結一下梯度下降法：

1、實際使用中使用梯度下降法找到的通常是局部極小值，而不是全局最小值。

2、具體找到的是哪個極小值和初始點位置有很大關係。

3、如果函數是凸函數，那麼梯度下降法可以保證收斂到全局最優解（最小值）

4、梯度下降法收斂速度通常比較慢

5、梯度下降法中搜索步長 λ 很關鍵，步長太長會導致找不到極值點甚至震蕩發散，步長太小收斂非常慢。

因此，前面的例子中，迷路的探險者可能花費了大量時間找到的卻是一個假的山腳（山腰的某個低洼處，局部最小值）。

本文首發於公眾號：計算機視覺life。原文鏈接：從零開始學習「張氏相機標定法」（四）優化演算法前傳