opt summary

1 優化問題分類

優化問題一般可分為兩大類：無限制優化問題和限制優化問題，限制優化問題又可分為含等式限制優化問題和含不等式限制優化問題。

• 無限制優化問題
• 含等式限制的優化問題
• 含不等式限制的優化問題

2 求解政策

針對以上三種情形，各有不同的處理政策：

• 無限制的優化問題：可直接對其求導，并使其為0，這樣便能得到最終的最優解；
• 含等式限制的優化問題：主要通過拉格朗日乘數法将含等式限制的優化問題轉換成為無限制優化問題求解；
• 含有不等式限制的優化問題：主要通過KKT條件(Karush-Kuhn-Tucker Condition)将其轉化成無限制優化問題求解。

3 求解算法

3.1 無限制優化算法

ref:http://www.cnblogs.com/maybe2030/p/4751804.html

3.1.1 梯度下降法

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

　　牛頓法的缺點：

　　（1）靠近極小值時收斂速度減慢，如下圖所示；

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

　　（3）可能會“之字形”地下降。

　　從上圖可以看出，梯度下降法在接近最優解的區域收斂速度明顯變慢，利用梯度下降法求解需要很多次的疊代。

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

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

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

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

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

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

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

　　2）随機梯度下降（StochasticGradient Descent，SGD）

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

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

　　（3）随機梯度下降是通過每個樣本來疊代更新一次，如果樣本量很大的情況（例如幾十萬），那麼可能隻用其中幾萬條或者幾千條的樣本，就已經将theta疊代到最優解了，對比上面的批量梯度下降，疊代一次需要用到十幾萬訓練樣本，一次疊代不可能最優，如果疊代10次的話就需要周遊訓練樣本10次。但是，SGD伴随的一個問題是噪音較BGD要多，使得SGD并不是每次疊代都向着整體最優化方向。

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

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

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

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

3.1.2 牛頓法和拟牛頓法

　1）牛頓法（Newton’s method）

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

　　具體步驟：

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

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

　　已經證明，如果f  ‘ 是連續的，并且待求的零點x是孤立的，那麼在零點x周圍存在一個區域，隻要初始值x0位于這個鄰近區域内，那麼牛頓法必定收斂。 并且，如果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算法。

3.1.3 共轭梯度法

共轭梯度法是介于最速下降法與牛頓法之間的一個方法，它僅需利用一階導數資訊，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點，共轭梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優化最有效的算法之一。 在各種優化算法中，共轭梯度法是非常重要的一種。其優點是所需存儲量小，具有步收斂性，穩定性高，而且不需要任何外來參數。

　　具體的實作步驟請參加wiki百科共轭梯度法。

　　下圖為共轭梯度法和梯度下降法搜尋最優解的路徑對比示意圖：

注：綠色為梯度下降法，紅色代表共轭梯度法

　　MATLAB代碼：

[plain]

view plain copy print ?

1. function [x] = conjgrad(A,b,x)  
2.     r=b-A*x;  
3.     p=r;  
4.     rsold=r’*r;  
5.     for i=1:length(b)  
6.         Ap=A*p;  
7.         alpha=rsold/(p’*Ap);  
8.         x=x+alpha*p;  
9.         r=r-alpha*Ap;  
10.         rsnew=r’*r;  
11.         if sqrt(rsnew)<1e-10  
12.               break;  
13.         end  
14.         p=r+(rsnew/rsold)*p;  
15.         rsold=rsnew;  
16.     end  
17. end  

function [x] = conjgrad(A,b,x) 

    r=b-A*x; 

    p=r; 

    rsold=r'*r;
           

for i=1:length(b)
    Ap=A*p;
    alpha=rsold/(p'*Ap);
    x=x+alpha*p;
    r=r-alpha*Ap;
    rsnew=r'*r;
    if sqrt(rsnew)<1e-10
          break;
    end
    p=r+(rsnew/rsold)*p;
    rsold=rsnew;
end
           

end

3.2 限制優化算法

3.2.1 含等式限制優化算法——拉格朗日乘數法

ref: http://www.cnblogs.com/zhangchaoyang/articles/2726873.html#3592012

3.2.2 含不等式限制優化算法——KKT條件

4 智能優化算法 

ref: http://blog.csdn.net/hp910315/article/details/51221657

4.1、遺傳算法 

遺傳算法（GeneticAlgorithm）是一類借鑒生物界的進化規律（适者生存，優勝劣汰遺傳機制）演化而來的随機化搜尋方法。

4.2、模拟退火算法 

是用來求解最優化問題的算法。比如著名的TSP問題，函數最大值最小值問題等等。

4.3、粒子群優化算法 

和模拟退火算法相似，它也是從随機解出發，通過疊代尋找最優解，它也是通過适應度來評價解的品質，但它比遺傳算法規則更為簡單，它沒有遺傳算法的“交叉”(Crossover) 和“變異”(Mutation) 操作，它通過追随目前搜尋到的最優值來尋找全局最優。

4.4、蟻群算法 

蟻群算法(antcolony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優化路徑的機率型算法。

4.5、免疫算法 

免疫算法是一種具有生成+檢測 (generate andtest)的疊代過程的搜尋算法。從理論上分析，疊代過程中，在保留上一代最佳個體的前提下，遺傳算法是全局收斂的。

4.6、克隆選擇算法 

根據克隆選擇原理設計的免疫算法。解決問題時，一般把問題定義為抗原，而問題的解就是抗體集合。在特定的形态空間中，随機産生的抗體試圖與抗原發生比對，即嘗試解決問題。比對度高的抗體有可能産生更好的解，被賦予更大的克隆機率參與下一次比對。

4.7、和聲搜尋算法 

和聲搜尋（HarmonySearch, HS）算法是一種新穎的智能優化算法。類似于遺傳算法對生物進化的模仿、模拟退火算法對實體退火的模拟以及粒子群優化算法對鳥群的模仿等，和聲算法模拟了音樂演奏的原理。

4.8、禁忌搜尋算法 

禁忌（TabuSearch）算法是一種亞啟發式(meta-heuristic)随機搜尋算法，它從一個初始可行解出發，選擇一系列的特定搜尋方向（移動）作為試探，選擇實作讓特定的目标函數值變化最多的移動。為了避免陷入局部最優解，TS搜尋中采用了一種靈活的“記憶”技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜尋方向，這就是Tabu表的建立。

4.9、差分進化算法 

它是由Storn等人于1995年提出的，和其它演化算法一樣，DE是一種模拟生物進化的随機模型，通過反複疊代，使得那些适應環境的個體被儲存了下來。但相比于進化算法，DE保留了基于種群的全局搜尋政策，采用實數編碼、基于差分的簡單變異操作和一對一的競争生存政策，降低了遺傳操作的複雜性。同時，DE特有的記憶能力使其可以動态跟蹤目前的搜尋情況，以調整其搜尋政策，具有較強的全局收斂能力和魯棒性，且不需要借助問題的特征資訊，适于求解一些利用正常的數學規劃方法所無法求解的複雜環境中的優化問題。

4.10、BP神經網絡算法 

BP神經網絡是一種基于有監督的學習，使用非線性可導函數作為傳遞函數的前饋神經網絡。

5 算法比較

5.1 無限制優化算法

Ø  坐标輪換法具有不需要導數資訊的優點，計算過程比較簡單，程式實作也比較容易，但存在算法收斂速度較慢、計算效率低等缺點。坐标輪換法主要用來解決優化問題設計變量數目小于10的小規模無限制優化問題;另外，坐标輪換法還可解決目标函數的等值線為圓或平行于坐标軸的優化問題。

Ø  與其他無限制優化算法相比，最速下降法具有方法簡單等優點，計算效率在最初幾步疊代時較高，且對初始點不敏感，因而常與其他方法一起使用，但最速下降法需要目标函數的一階導數資訊。

Ø  求解無限制優化問題的牛頓法對給定的初始點比較敏。如果初始點選擇的比較好，則其解決優化問題的收斂過程會很快;如果選擇不當，則可能會出現收斂失敗的情況。另外，牛頓法存在計算過程複雜、計算量特别大等缺點，是以主要适合于設計變量數目小的優化問題及目标函數階次較低的優化問題。

Ø  共轭梯度法具有收斂速度快等優點，其收斂速度遠快于最速下降法。共轭梯度法計算簡單，所需要的存儲空間少，适合于優化變量數目較多的中等規模優化問題。

Ø  在無限制優化方法中，Powell法是計算效率比較高的優化算法之一，它不需要目标函數的導數，是求解中小型規模優化問題的有效方法。

Ø  變尺度法也是計算效率比較高的優化算法之一，可用來解決高階目标函數的優化問題，但存在程式實作比較複雜、存儲空間比較大等缺點。

Ø  單純形法具有不需目标函數導數資訊、程式實作簡單、計算效率比較高等優點。

5.2 限制優化算法

Ø  Monte Carlo法具有方法簡單、不需要導數資訊等優點，但存在求解高維優化問題時計算量大等不足;

Ø  随機方向搜尋法具有優化求解過程收斂快，但存在局部尋優的不足，因而在使用時需采用選擇多個不同初始點的政策;

Ø  複合形法具有程式實作簡單等優點，但在解決設計變量和限制條件多的優化問題時優化效率比較低;

Ø  可行方向法是解決限制優化問題的有效方法之一，适合求解中等規模化問題，但存在程式實作複雜等不足;

Ø  廣義簡約梯度法具有算法收斂快、計算精度高等優點，但也存在程式實作複雜等不足;

Ø  罰函數優化方法包括内點法、外點法、混合法等，具有方法實作簡單等優點，但存在優化過程不穩定、收斂速度較慢等缺點，适宜于解決中小規模優化問題;

Ø  序列線性規劃法收斂較慢，隻适用于非線性程度不是很強的優化問題;

Ø  序列二次規劃法是收斂速度較快、優化比較有效的方法之一，比較适合于中等規模優化問題;

5.3 智能算法

遺傳算法：優點是能很好的處理限制，能很好的跳出局部最優，最終得到全局最優解，全局搜尋能力強；缺點是收斂較慢，局部搜尋能力較弱，運作時間長，且容易受參數的影響。

遺傳算法适合求解離散問題，具備數學理論支援，但是存在着漢明懸崖等問題。

模拟退火：優點是局部搜尋能力強，運作時間較短；缺點是全局搜尋能力差，容易受參數的影響。

爬山算法：顯然爬山算法較簡單，效率高，但是處理多限制大規模問題時力不從心，往往不能得到較好的解。

粒子群算法适合求解實數問題，算法簡單，計算友善，求解速度快，但是存在着陷入局部最優等問題。

蟻群算法适合在圖上搜尋路徑問題，計算開銷會大。

要将三種算法進行混合，就要針對特定問題，然後融合其中的優勢，比如将遺傳算法中的變異算子加入粒子群中就可以形成基于變異的粒子群算法。

6 參考資料及文檔

優化方法：http://wenku.baidu.com/view/435728f032d4b14e852458fb770bf78a64293a53

矩陣計算：http://wenku.baidu.com/view/4da1a2eda0c7aa00b52acfc789eb172dec639950

更多課件參考：http://www.cnblogs.com/zhangchaoyang/articles/2600491.html

斯坦福大學Ng課件：http://cs229.stanford.edu/section/cs229-cvxopt.pdf

大牛部落格：http://www.cnblogs.com/maybe2030/category/709560.html

五大經典算法系列：http://www.cnblogs.com/steven_oyj/category/246990.html