簡述dfp演算法的演算法步驟

1. 梯度下降法與牛頓法

梯度下降和牛頓法的推導均與泰勒公式有關，所以先介紹泰勒展開公式：
基本形式：

上面這個迭代形式將應用到下面的梯度下降和牛頓法中。

梯度下降法應用一階泰勒展開，假設 L (θ)代表損失函數，目標：最小化損失函數，θ是需要更新的模型參數。下面公式中alpha是步長(學習率)，可以直接賦值一個小的數，也可以通過line search。

牛頓法應用二階泰勒展開，目標：最小化損失函數

g定義為雅克比矩陣，矩陣中各元素對應一階偏導數
Hessian矩陣中各元素對應二階偏導數。Hessian矩陣的逆同比於梯度下降法的學習率參數alpha，Hessian的逆在迭代中不斷減小，起到逐漸縮小步長的效果。

1.梯度下降法： 通過梯度方向和步長，直接求解目標函數最小值時的參數。
越接近最優值時，步長應該不斷減小，否則會在最優值附近來回震盪。
2.牛頓法：
優點：通過求解目標函數的一階導數為0時的參數，進而求出目標函數最小值時的參數。收斂速度很快。海森矩陣的逆在迭代過程中不斷減小，可以起到逐步減小步長的效果。
缺點：海森矩陣的逆計算復雜，代價比較大，因此有了擬牛頓法。

解決牛頓法計算比較復雜的問題，使用正定矩陣近似Hessian矩陣的逆，簡化了運算的復雜度。
常用的擬牛頓演算法：DFP演算法和BFGS演算法

2. 非線性規劃的深入解析

例1（投資決策問題）某企業有n個項目可供選擇投資，並且至少要對其中一個項目投資。已知該企業擁有總資金A元，投資於第i個項目需花資金ai元，並預計可收益bi元。試選擇最佳投資方案。
解:設投資決策變數為

則投資總額為∑aixi，投資總收益為∑bixi。因為該公司至少要對一個項目投資，並且總的投資金額不能超過總資金 ，故有限制條件

另外，由於 xi只取值0或1，所以還有

最佳投資方案應是投資額最小而總收益最大的方案，所以這個最佳投資決策問題歸結為總資金以及決策變數（取0或1）的限制條件下，極大化總收益和總投資之比。因此，其數學模型為：
上面例題是在一組等式或不等式的約束下，求一個函數的最大值（或最小值）問題，其中目標函數或約束條件中至少有一個非線性函數，這類問題稱之為非線性規劃問題，簡記為（NP）。可概括為一般形式

（NP)
其中x=[x1 ... xn]稱為模型（NP）的決策變數，f稱為目標函數，gi和hj 稱為約束函數。另外，gi(x)=0稱為等式約束，hj(x)<=0稱為不等式約束。 對於一個實際問題，在把它歸結成非線性規劃問題時，一般要注意如下幾點：
（i）確定供選方案：首先要收集同問題有關的資料和數據，在全面熟悉問題的基礎上，確認什麼是問題的可供選擇的方案，並用一組變數來表示它們。
（ii）提出追求目標：經過資料分析，根據實際需要和可能，提出要追求極小化或極大化的目標。並且，運用各種科學和技術原理，把它表示成數學關系式。
（iii）給出價值標准：在提出要追求的目標之後，要確立所考慮目標的「好」或「壞」的價值標准，並用某種數量形式來描述它。
（iv）尋求限制條件：由於所追求的目標一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變數之間的一些不等式或等式來表示。 對實際規劃問題作定量分析，必須建立數學模型。建立數學模型首先要選定適當的目標變數和決策變數，並建立起目標變數與決策變數之間的函數關系，稱之為目標函數。然後將各種限制條件加以抽象，得出決策變數應滿足的一些等式或不等式，稱之為約束條件。非線性規劃問題的一般數學模型可表述為求未知量x1，x2，…，xn，使滿足約束條件：
gi(x1，…，xn）≥0i=1，…，m
hj(x1，…，xn)=0j=1，…，p
並使目標函數f(x1，…，xn）達到最小值（或最大值）。其中f，諸gi和諸hj都是定義在n維向量空間Rn的某子集D（定義域）上的實值函數，且至少有一個是非線性函數。
上述模型可簡記為：
min f(x)
s.t. gi(x）≥0i=1，…，m
hj(x)=0 j=1，…，p
其中x=(x1，…，xn）屬於定義域D，符號min表示「求最小值」，符號s.t.表示「受約束於」。
定義域D 中滿足約束條件的點稱為問題的可行解。全體可行解所成的集合稱為問題的可行集。對於一個可行解x*，如果存在x*的一個鄰域，使目標函數在x*處的值f(x*）優於 （指不大於或不小於）該鄰域中任何其他可行解處的函數值，則稱x*為問題的局部最優解（簡稱局部解）。如果f(x*）優於一切可行解處的目標函數值，則稱x*為問題的整體最優解（簡稱整體解）。實用非線性規劃問題要求整體解，而現有解法大多隻是求出局部解。 指尋求一元函數在某區間上的最優值點的方法。這類方法不僅有實用價值，而且大量多維最優化方法都依賴於一系列的一維最優化。常用的一維最優化方法有黃金分割法、切線法和插值法。
①黃金分割法又稱0.618法。它適用於單峰函數。其基本思想是：在初始尋查區間中設計一列點，通過逐次比較其函數值，逐步縮小尋查區間，以得出近似最優值點。
②切線法又稱牛頓法。它也是針對單峰函數的。其基本思想是：在一個猜測點附近將目標函數的導函數線性化，用此線性函數的零點作為新的猜測點，逐步迭代去逼近最優點。
③插值法又稱多項式逼近法。其基本思想是用多項式（通常用二次或三次多項式）去擬合目標函數。
此外，還有斐波那契法、割線法、有理插值法、分批搜索法等。 指尋求 n元實函數f在整個n維向量空間Rn上的最優值點的方法。這類方法的意義在於：雖然實用規劃問題大多是有約束的，但許多約束最優化方法可將有約束問題轉化為若干無約束問題來求解。
無約束最優化方法大多是逐次一維搜索的迭代演算法。這類迭代演算法可分為兩類。一類需要用目標函數的導函數，稱為解析法。另一類不涉及導數，只用到函數值，稱為直接法。這些迭代演算法的基本思想是：在一個近似點處選定一個有利搜索方向，沿這個方向進行一維尋查，得出新的近似點。然後對新點施行同樣手續，如此反復迭代，直到滿足預定的精度要求為止。根據搜索方向的取法不同，可以有各種演算法。屬於解析型的演算法有：①梯度法：又稱最速下降法。這是早期的解析法，收斂速度較慢。②牛頓法：收斂速度快，但不穩定，計算也較困難。③共軛梯度法：收斂較快，效果較好。④變尺度法：這是一類效率較高的方法。其中達維登-弗萊徹-鮑威爾變尺度法，簡稱 DFP法，是最常用的方法。屬於直接型的演算法有交替方向法（又稱坐標輪換法）、模式搜索法、旋轉方向法、鮑威爾共軛方向法和單純形加速法等。 這是一類特殊的非線性規劃。在前述非線性規劃數學模型中，若f是凸函數，諸gi都是凹函數，諸hj都是一次函數，則稱之為凸規劃。所謂f是凸函數，是指f有如下性質：它的定義域是凸集，且對於定義域中任意兩點x和y及任一小於1的正數α，下式都成立：
f(（1-α）x +αy）α≤（1-α）f(x)+αf(y)
將上述不等式中的不等號反向即得凹函數的定義。所謂凸集，是指具有如下性質的集合：連結集合中任意兩點的直線段上的點全部屬於該集合。
對於一般的非線性規劃問題，局部解不一定是整體解。但凸規劃的局部解必為整體解，而且凸規劃的可行集和最優解集都是凸集。 幾何規劃一類特殊的非線性規劃。它的目標函數和約束函數都是正定多項式（或稱正項式）。幾何規劃本身一般不是凸規劃，但經適當變數替換，即可變為凸規劃。幾何規劃的局部最優解必為整體最優解。求解幾何規劃的方法有兩類。一類是通過對偶規劃去求解；另一類是直接求解原規劃，這類演算法大多建立在根據幾何不等式將多項式轉化為單項式的思想上。

3. 幾種常用最優化方法

學習和工作中遇到的大多問題都可以建模成一種最優化模型進行求解，比如我們現在學習的機器學習演算法，大部分的機器學習演算法的本質都是建立優化模型，通過最優化方法對目標函數（或損失函數）進行優化，從而訓練出最好的模型。常見的優化方法(optimization)有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。

1. 梯度下降法（Gradient Descent）

梯度下降法是最早最簡單，也是最為常用的最優化方法。梯度下降法實現簡單，當目標函數是凸函數時，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優解，梯度下降法的速度也未必是最快的。 梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以也被稱為是」最速下降法「。最速下降法越接近目標值，步長越小，前進越慢。

梯度下降 法的缺點：

（1）靠近極小值時收斂速度減慢;

（2）直線搜索時可能會產生一些問題；

（3）可能會「之字形」地下降。

在機器學習中，基於基本的梯度下降法發展了兩種梯度下降方法，分別為隨機梯度下降法和批量梯度下降法。

比如對一個線性回歸（Linear Logistics）模型，假設下面的h(x)是要擬合的函數，J( )為損失函數， 是參數，要迭代求解的值，求解出來了那最終要擬合的函數h( )就出來了。其中m是訓練集的樣本個數，n是特徵的個數。

1）批量梯度下降法（Batch Gradient Descent，BGD）

（1）將J( )對 求偏導，得到每個theta對應的的梯度：

(2）由於是要最小化風險函數，所以按每個參數 的梯度負方向，來更新每個 ：

        （3）從上面公式可以注意到，它得到的是一個全局最優解，但是每迭代一步，都要用到訓練集所有的數據，如果m很大，那麼可想而知這種方法的迭代速度會相當的慢。所以，這就引入了另外一種方法——隨機梯度下降。

對於批量梯度下降法，樣本個數m，x為n維向量，一次迭代需要把m個樣本全部帶入計算，迭代一次計算量為m*n2。

2）隨機梯度下降（Stochastic Gradient Descent，SGD）

        （1）上面的風險函數可以寫成如下這種形式，損失函數對應的是訓練集中每個樣本的粒度，而上面批量梯度下降對應的是所有的訓練樣本：

（2）每個樣本的損失函數，對 求偏導得到對應梯度，來更新 ：

（3）隨機梯度下降是通過每個樣本來迭代更新一次，如果樣本量很大的情況（例如幾十萬），那麼可能只用其中幾萬條或者幾千條的樣本，就已經將

迭代到最優解了，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓練樣本，一次迭代不可能最優，如果迭代10次的話就需要遍歷訓練樣本10次。但是，SGD伴隨的一個問題是噪音較BGD要多，使得SGD並不是每次迭代都向著整體最優化方向。

隨機梯度下降每次迭代只使用一個樣本，迭代一次計算量為n2，當樣本個數m很大的時候，隨機梯度下降迭代一次的速度要遠高於批量梯度下降方法。 兩者的關系可以這樣理解：隨機梯度下降方法以損失很小的一部分精確度和增加一定數量的迭代次數為代價，換取了總體的優化效率的提升。增加的迭代次數遠遠小於樣本的數量。

對批量梯度下降法和隨機梯度下降法的總結：

批量梯度下降---最小化所有訓練樣本的損失函數，使得最終求解的是全局的最優解，即求解的參數是使得風險函數最小，但是對於大規模樣本問題效率低下。

隨機梯度下降---最小化每條樣本的損失函數，雖然不是每次迭代得到的損失函數都向著全局最優方向， 但是大的整體的方向是向全局最優解的，最終的結果往往是在全局最優解附近，適用於大規模訓練樣本情況。

2. 牛頓法和擬牛頓法（Newton's method & Quasi-Newton Methods）

1）牛頓法（Newton's method）

牛頓法是一種在實數域和復數域上近似求解方程的方法。方法使用函數 f  ( x )的泰勒級數的前面幾項來尋找方程 f  ( x ) = 0的根。牛頓法最大的特點就在於它的收斂速度很快。

具體步驟：

首先，選擇一個接近函數 f  ( x )零點的x0，計算相應的 f  ( x 0)和切線斜率 f  '  ( x 0)（這里 f '  表示函數 f   的導數）。然後我們計算穿過點( x 0, f   ( x 0))並且斜率為 f  '( x 0)的直線和 x  軸的交點的 x 坐標，也就是求如下方程的解：

我們將新求得的點的 x  坐標命名為 x 1，通常 x 1會比 x 0更接近方程 f   ( x ) = 0的解。因此我們現在可以利用 x 1開始下一輪迭代。迭代公式可化簡為如下所示：

已經證明，如果 f   '是連續的，並且待求的零點 x 是孤立的，那麼在零點 x 周圍存在一個區域，只要初始值 x 0位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果 f   ' ( x )不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。下圖為一個牛頓法執行過程的例子。

由於牛頓法是基於當前位置的切線來確定下一次的位置，所以牛頓法又被很形象地稱為是"切線法"。

關於牛頓法和梯度下降法的效率對比：

從本質上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之後，坡度是否會變得更大。所以，可以說牛頓法比梯度下降法看得更遠一點，能更快地走到最底部。（牛頓法目光更加長遠，所以少走彎路；相對而言，梯度下降法只考慮了局部的最優，沒有全局思想。）

根據wiki上的解釋，從幾何上說，牛頓法就是用一個二次曲面去擬合你當前所處位置的局部曲面，而梯度下降法是用一個平面去擬合當前的局部曲面，通常情況下，二次曲面的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合真實的最優下降路徑。

註：紅色的牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。

牛頓法的優缺點總結：

優點：二階收斂，收斂速度快；

缺點：牛頓法是一種迭代演算法，每一步都需要求解目標函數的Hessian矩陣的逆矩陣，計算比較復雜。

2）擬牛頓法（Quasi-Newton Methods）

擬牛頓法是求解非線性優化問題最有效的方法之一，於20世紀50年代由美國Argonne國家實驗室的物理學家W.C.Davidon所提出來。Davidon設計的這種演算法在當時看來是非線性優化領域最具創造性的發明之一。不久R. Fletcher和M. J. D. Powell證實了這種新的演算法遠比其他方法快速和可靠，使得非線性優化這門學科在一夜之間突飛猛進。

擬牛頓法的本質思想是改善牛頓法每次需要求解復雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的復雜度。 擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。如今，優化軟體中包含了大量的擬牛頓演算法用來解決無約束，約束，和大規模的優化問題。

具體步驟：

擬牛頓法的基本思想如下。首先構造目標函數在當前迭代xk的二次模型：

這里Bk是一個對稱正定矩陣，於是我們取這個二次模型的最優解作為搜索方向，並且得到新的迭代點：

其中我們要求步長ak 滿足Wolfe條件。這樣的迭代與牛頓法類似，區別就在於用近似的Hesse矩陣Bk 代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣Bk的更新。現在假設得到一個新的迭代xk+1，並得到一個新的二次模型：

我們盡可能地利用上一步的信息來選取Bk。具體地，我們要求

從而得到

這個公式被稱為割線方程。常用的擬牛頓法有DFP演算法和BFGS演算法。

原文鏈接： [Math] 常見的幾種最優化方法 - Poll的筆記 - 博客園