非線性優(yōu)化算法總結(jié)

文章目錄

• 非線性優(yōu)化算法總結(jié)
• 一、非線性最小二乘問題
• 二、最速梯度下降法和牛頓法
• 三、高斯牛頓法
• 四、LM（ Levenberg-Marquadt）法

---

一、非線性最小二乘問題

最小二乘法形式如下式：

這里Target（θ）函數(shù)為目標(biāo)函數(shù)，在機(jī)器學(xué)習(xí)中就是損失函數(shù)，

這個(gè)函數(shù)為預(yù)測(cè)值，在機(jī)器學(xué)習(xí)中就是模型輸出值，yi是真實(shí)值或理論值。
那么 非線性最小二乘 就很容易理解了，目標(biāo)參數(shù)函數(shù)和參數(shù)的關(guān)系是非線性。這里要優(yōu)化的參數(shù)為θ。

對(duì)于矩陣形式，這里我們簡(jiǎn)單一點(diǎn)：直接把簡(jiǎn)單的非線性最小二乘問題定義為：

這里要優(yōu)化的參數(shù)就是X。其中自變量x∈Rn,f(x)是任意的非線性函數(shù)，并設(shè)它的維度為m,即f(x)∈Rm.如果 f 是個(gè)數(shù)學(xué)形式上很簡(jiǎn)單的函數(shù)，那問題也許可以用解析形式來求。令目標(biāo)函數(shù)的導(dǎo)數(shù)為零，然后求解 x 的最優(yōu)值，就和一個(gè)求二元函數(shù)的極值一樣：

解此方程，就得到了導(dǎo)數(shù)為零處的極值。它們可能是極大、極小或鞍點(diǎn)處的值，只要挨個(gè)兒比較它們的函數(shù)值大小即可。但是導(dǎo)數(shù)不一定可以直接求解x,這個(gè)導(dǎo)函數(shù)可能是一個(gè)復(fù)雜的非線性方程。這種情況下一般采用迭代來求解，從一個(gè)初始值出發(fā)，不斷地更新當(dāng)前的優(yōu)化變量，使目標(biāo)函數(shù)下降。具體步驟可以表示為 :

這讓求解導(dǎo)函數(shù)為零的問題，變成了一個(gè)不斷尋找梯度并下降的過程。直到某個(gè)時(shí)刻增量非常小，無法再使函數(shù)下降。此時(shí)算法收斂，目標(biāo)達(dá)到了一個(gè)極小，我們完成了尋找極小值的過程。

二、最速梯度下降法和牛頓法

首先，我們將目標(biāo)函數(shù)在X附近進(jìn)行泰勒展開：

這里如果看不懂的話就復(fù)習(xí)一下高數(shù)中的泰勒展開式和簡(jiǎn)單矩陣求導(dǎo)。這里的J(x)是f(x)關(guān)于x的導(dǎo)數(shù)（雅可比矩陣），H(x)是二階導(dǎo)數(shù)(海森矩陣)。我們可以選擇保留泰勒公式的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)，如果保留一階導(dǎo)數(shù)，則增量的解就是：

它的直觀意義非常簡(jiǎn)單，只要我們找到梯度然后沿著反向梯度方向前進(jìn)即可。當(dāng)然，我們還需要該方向上取一個(gè)步長 λ，求得最快的下降方式。這種方法被稱為最速梯度下降法或是一階梯度法。

另一方面，如果保留二階梯度信息，那么增量方程為：

對(duì)Δx求導(dǎo)數(shù)并令它等于0，則

就得到了增量的解：

這種方法稱為牛頓法或二階梯度法，它的迭代公式可以表示為：

這兩種方法只要把函數(shù)在迭代點(diǎn)附近進(jìn)行泰勒展開，并針對(duì)更新量作最小化即可。由于泰勒展開之后函數(shù)變成了多項(xiàng)式，所以求解增量時(shí)只需解線性方程即可，避免了直接求導(dǎo)函數(shù)為零這樣的非線性方程的困難。這兩種方法也存在它們自身的問題。最速梯度下降法過于貪心，容易走出鋸齒路線，反而增加了迭代次數(shù)。而牛頓法則需要計(jì)算目標(biāo)函數(shù)的 H 矩陣，這在問題規(guī)模較大時(shí)非常困難，我們通常傾向于避免 H 的計(jì)算。

三、高斯牛頓法

Gauss Newton 是最優(yōu)化算法里面最簡(jiǎn)單的方法之一。它的思想是將 f(x) 進(jìn)行一階的
泰勒展開（請(qǐng)注意不是對(duì)下面的目標(biāo)函數(shù) 進(jìn)行展開）
而是如下展開：

這里 J(x) 為 f(x) 關(guān)于 x 的導(dǎo)數(shù)，實(shí)際上是一個(gè) m × n 的矩陣，也是一個(gè)雅可比矩陣。根據(jù)前面的框架，當(dāng)前的目標(biāo)是為了尋找下降矢量 ?x，使得 ∥f (x + ?x)∥2 達(dá)到最小。為了求 ?x，我們構(gòu)建 一個(gè)線性的最小二乘問題：

根據(jù)極值條件，將上述目標(biāo)函數(shù)對(duì) ?x 求導(dǎo)，并令導(dǎo)數(shù)為零。由于這里考慮的是 ?x 的導(dǎo)數(shù)（而不是 x），我們最后將得到一個(gè)線性的方程。為此，先展開目標(biāo)函數(shù)的平方項(xiàng)：

求上式關(guān)于 ?x 的導(dǎo)數(shù)，并令其為零：

我們要求解的變量是 ?x，這是一個(gè)線性方程組，我們稱它為增量方程或高斯牛頓方程 (Gauss Newton equations) 或者正規(guī)方程 (Normal equations)。我們把左邊的系數(shù)定義為 H，右邊定義為 g，那么上式變?yōu)?#xff1a;


對(duì)比牛頓法可見，高斯牛頓法用 J矩陣的轉(zhuǎn)置乘以J矩陣作為牛頓法中二階 H 矩陣的近似，從而省略了計(jì)算 H 的過程。求解增量方程是整個(gè)優(yōu)化問題的核心所在。原則上，它要求近似的矩陣H是可逆的（而且是正定的），而實(shí)際計(jì)算中得到的JTJ卻是半正定的。也就是使用高斯牛頓法會(huì)出現(xiàn)JTJ為奇異或者病態(tài)情況，此時(shí)增量的穩(wěn)定性較差，導(dǎo)致算法不收斂。即使H非奇異也非病態(tài)，如果求得的Δx非常大,也會(huì)導(dǎo)致我們采用的局部近似不夠正確，這樣以來可能不能保證收斂，哪怕是還有可能讓目標(biāo)函數(shù)更大。即使高斯牛頓法具有它的缺點(diǎn)，但是很多非線性優(yōu)化可以看作是高斯牛頓法的一個(gè)變種，這些算法結(jié)合了高斯牛頓法的優(yōu)點(diǎn)并修正其缺點(diǎn)。例如LM算法，盡管它的收斂速度可能比高斯牛頓法更慢，但是該方法健壯性更強(qiáng)，也被稱為阻尼牛頓法。

四、LM（ Levenberg-Marquadt）法

由于 高斯牛頓方法中采用的近似二階泰勒展開只能在展開點(diǎn)附近有較好的近似效果，所以我們很自然地想到應(yīng)該給 ?x 添加一個(gè)信賴區(qū)域（Trust Region），不能讓它太大而使得近似不準(zhǔn)確。非線性優(yōu)化種有一系列這類方法，這類方法也被稱之為信賴區(qū)域方法 (Trust Region Method)。在信賴區(qū)域里邊，我們認(rèn)為近似是有效的；出了這個(gè)區(qū)域，近似可能會(huì)出問題。一個(gè)比較好的方法是根據(jù)我們的近似模型跟實(shí)際函數(shù)之間的差異來確定這個(gè)范圍：如果差異小，我們就讓范圍盡可能大；如果差異大，我們就縮小這個(gè)近似范圍。因此，考慮使用：

來判斷泰勒近似是否夠好。ρ 的分子是實(shí)際函數(shù)下降的值，分母是近似模型下降的值。如果 ρ 接近于 1，則近似是好的。如果 ρ 太小，說明實(shí)際減小的值遠(yuǎn)少于近似減小的值，則認(rèn)為近似比較差，需要縮小近似范圍。反之，如果 ρ 比較大，則說明實(shí)際下降的比預(yù)計(jì)的更大，我們可以放大近似范圍。LM算法表示如下：

上面算法中，μ表示信賴區(qū)域的半徑，那么信賴區(qū)域就是一個(gè)球形區(qū)域，該約束認(rèn)為只有在球內(nèi)才是有效的，帶上矩陣D后就是一個(gè)橢球區(qū)域。在 LM 算法中，我們需要解下面的式子那樣的一個(gè)子問題來獲得梯度。

這個(gè)子問題是帶不等式約束的優(yōu)化問題采用拉格朗日乘子法將上述問題轉(zhuǎn)化為一個(gè)無約束問題：

這里 λ 為 拉格朗日 乘子。仔細(xì)看上面的式子，我們根據(jù)加號(hào)把它分為左右兩部分，回想前面的高斯牛頓算法，你會(huì)發(fā)現(xiàn)加號(hào)左邊是一個(gè)高斯牛頓算法中的最小二乘問題，這一部分對(duì)Δx求梯度，得到增量方程：

加號(hào)右邊對(duì)Δx求梯度，得到：

我們把這兩部分合并：得到增量的線性方程：

可以看到，增量方程相比于 高斯牛頓，多了一項(xiàng)。如果考慮它的簡(jiǎn)化形式，即 D = I，那么相當(dāng)于求解：

當(dāng)參數(shù) λ 比較小時(shí)，H 占主要地位，這說明二次近似模型在該范圍內(nèi)是比較好的，LM 方法更接近于 高斯牛頓法。另一方面，當(dāng) λ 比較大時(shí)，λI 占據(jù)主要地位，LM更接近于最速梯度下降法這說明附近的二次近似不夠好。LM 的求解方式，可在一定程度上避免線性方程組的系數(shù)矩陣的非奇異和病態(tài)問題，提供更穩(wěn)定更準(zhǔn)確的增量 ?x。
總而言之，非線性優(yōu)化問題的框架，分為 Line Search 和 Trust Region 兩類。Line Search 先固定搜索方向，然后在該方向?qū)ふ也介L，以最速下降法和 高斯牛頓法為代表。而 Trust Region 則先固定搜索區(qū)域，再考慮找該區(qū)域內(nèi)的最優(yōu)點(diǎn)。此類方法以 LM 為代表。實(shí)際問題中，我們通常選擇 高斯牛頓或 LM 之一作為梯度下降策略。

參考書籍《視覺SLAM十四講 從理論到實(shí)踐》

---

如果您認(rèn)可我的文章，希望能夠關(guān)注我的微信公眾號(hào)，我會(huì)不定期更新工作中學(xué)到的東西和一些技術(shù)比較前沿的東西。

總結(jié)

以上是生活随笔為你收集整理的非线性优化算法总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。