最優化理論與演算法牛頓法

Ⅰ 什麼是最優化

最優化是應用數學的一個分支，主要指在一定條件限制下，選取某種研究方案使目標達到最優的一種方法。最優化問題在當今的軍事、工程、管理等領域有著極其廣泛的應用。

常見方法：

1. 梯度下降法（Gradient Descent）

梯度下降法是最早最簡單，也是最為常用的最優化方法。

梯度下降法實現簡單，當目標函數是凸函數時，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優解，梯度下降法的速度也未必是最快的。

梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以也被稱為是」最速下降法「。最速下降法越接近目標值，步長越小，前進越慢。

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

（1）牛頓法：

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

（2）擬牛頓法：

擬牛頓法是求解非線性優化問題最有效的方法之一，其本質思想是改善牛頓法每次需要求解復雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的復雜度。擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。

通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。如今，優化軟體中包含了大量的擬牛頓演算法用來解決無約束，約束，和大規模的優化問題。

3. 共軛梯度法（Conjugate Gradient）

共軛梯度法是介於最速下降法與牛頓法之間的一個方法，它僅需利用一階導數信息，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣並求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優化最有效的演算法之一。

在各種優化演算法中，共軛梯度法是非常重要的一種。其優點是所需存儲量小，具有步收斂性，穩定性高，而且不需要任何外來參數。

4. 啟發式優化方法

啟發式方法指人在解決問題時所採取的一種根據經驗規則進行發現的方法。其特點是在解決問題時,利用過去的經驗，選擇已經行之有效的方法，而不是系統地、以確定的步驟去尋求答案。

啟發式優化方法種類繁多，包括經典的模擬退火方法、遺傳演算法、蟻群演算法以及粒子群演算法等等。

5. 拉格朗日乘數法

作為一種優化演算法，拉格朗日乘子法主要用於解決約束優化問題，它的基本思想就是通過引入拉格朗日乘子來將含有n個變數和k個約束條件的約束優化問題轉化為含有（n+k）個變數的無約束優化問題。拉格朗日乘子背後的數學意義是其為約束方程梯度線性組合中每個向量的系數。

將一個含有n個變數和k個約束條件的約束優化問題轉化為含有（n+k）個變數的無約束優化問題，拉格朗日乘數法從數學意義入手，通過引入拉格朗日乘子建立極值條件，對n個變數分別求偏導對應了n個方程，然後加上k個約束條件（對應k個拉格朗日乘子）一起構成包含了（n+k）變數的（n+k）個方程的方程組問題，這樣就能根據求方程組的方法對其進行求解。

Ⅱ 2、牛頓法和最速下降法只能求解無約束優化，有約束的非線性規劃有哪些求解方法

Data Mining

無約束最優化方法

梯度的方向與等值面垂直，並且指向函數值提升的方向。

二次收斂是指一個演算法用於具有正定二次型函數時，在有限步可達到它的極小點。二次收斂與二階收斂沒有盡然聯系，更不是一回事，二次收斂往往具有超線性以上的收斂性。一階收斂不一定是線性收斂。

解釋一下什麼叫正定二次型函數：

n階實對稱矩陣Q，對於任意的非0向量X，如果有XTQX>0，則稱Q是正定矩陣。

對稱矩陣Q為正定的充要條件是：Q的特徵值全為正。

二次函數，若Q是正定的，則稱f(X)為正定二次函數。

黃金分割法

黃金分割法適用於任何單峰函數求極小值問題。

求函數在[a,b]上的極小點，我們在[a,b]內取兩點c,d，使得a<c<d<b。並且有

1）如果f(c)<f(d)，則最小點出現在[a,d]上，因此[a,d]成為下一次的搜索區間。

2）如果f(c)>f(d)，則[c,b]成為下一次的搜索區間。

假如確定了[a,d]是新的搜索區間，我們並不希望在[a,d]上重新找兩個新的點使之滿足(1)式，而是利用已經抗找到有c點，再找一個e點，使滿足：

可以解得r=0.382，而黃金分割點是0.618。

練習：求函數f(x)=x*x-10*x+36在[1,10]上的極小值。

+ View Code
最速下降法

泰勒級數告訴我們：

其中Δx可正可負，但必須充分接近於0。

X沿D方向移動步長a後，變為X+aD。由泰勒展開式：

目標函數：

a確定的情況下即最小化：

向量的內積何時最小？當然是兩向量方向相反時。所以X移動的方向應該和梯度的方向相反。

接下來的問題是步長a應該怎麼定才能使迭代的次數最少？

若f(X)具有二階連續偏導，由泰勒展開式可得：

H是f(X)的Hesse矩陣。

可得最優步長：

g是f(X)的梯度矩陣。

此時：

可見最速下降法中最優步長不僅與梯度有關，而且與Hesse矩陣有關。

練習：求函數f(x1,x2)=x1*x1+4*x2*x2在極小點，以初始點X0=(1,1)T。

+ View Code
梯度下降法開始的幾步搜索，目標函數下降較快，但接近極值點時，收斂速度就比較慢了，特別是當橢圓比較扁平時，收斂速度就更慢了。

另外最速下降法是以函數的一次近似提出的，如果要考慮二次近似，就有牛頓迭代法。

牛頓迭代法

在點Xk處對目標函數按Taylar展開：

令

得

即

可見X的搜索方向是，函數值要在此方向上下降，就需要它與梯度的方向相反，即。所以要求在每一個迭代點上Hesse矩陣必須是正定的。

練習：求的極小點，初始點取X=(0,3)。

+ View Code
牛頓法是二次收斂的，並且收斂階數是2。一般目標函數在最優點附近呈現為二次函數，於是可以想像最優點附近用牛頓迭代法收斂是比較快的。而在開始搜索的幾步，我們用梯度下降法收斂是比較快的。將兩個方法融合起來可以達到滿意的效果。

收斂快是牛頓迭代法最大的優點，但也有致命的缺點：Hesse矩陣及其逆的求解計算量大，更何況在某個迭代點Xk處Hesse矩陣的逆可能根本就不存在（即Hesse矩陣奇異），這樣無法求得Xk+1。

擬牛頓法

Hesse矩陣在擬牛頓法中是不計算的，擬牛頓法是構造與Hesse矩陣相似的正定矩陣，這個構造方法，使用了目標函數的梯度（一階導數）信息和兩個點的「位移」（Xk-Xk-1）來實現。有人會說，是不是用Hesse矩陣的近似矩陣來代替Hesse矩陣，會導致求解效果變差呢？事實上，效果反而通常會變好。

擬牛頓法與牛頓法的迭代過程一樣，僅僅是各個Hesse矩陣的求解方法不一樣。

在遠離極小值點處，Hesse矩陣一般不能保證正定，使得目標函數值不降反升。而擬牛頓法可以使目標函數值沿下降方向走下去，並且到了最後，在極小值點附近，可使構造出來的矩陣與Hesse矩陣「很像」了，這樣，擬牛頓法也會具有牛頓法的二階收斂性。

對目標函數f(X)做二階泰勒展開：

兩邊對X求導

當X=Xi時，有

這里我們用Hi來代表在點Xi處的Hesse矩陣的逆，則

(5)式就是擬牛頓方程。

下面給出擬牛頓法中的一種--DFP法。

令

我們希望Hi+1在Hi的基礎上加一個修正來得到：

給定Ei的一種形式：

m和n均為實數，v和w均為N維向量。

(6)(7)聯合起來代入(5)可得：

下面再給一種擬牛頓法--BFGS演算法。

(8)式中黑色的部分就是DFP演算法，紅色部分是BFGS比DFP多出來的部分。

BFGS演算法不僅具有二次收斂性，而且只有初始矩陣對稱正定，則BFGS修正公式所產生的矩陣Hk也是對稱正定的，且Hk不易變為奇異，因此BFGS比DFP具有更好的數值穩定性。

Ⅲ 最優化理論與演算法的圖書目錄

第1章引言
1.1學科簡述
1.2線性與非線性規劃問題
*1.3幾個數學概
1.4凸集和凸函數
習題
第2章線性規劃的基本性質
2.1標准形式及圖解法
2.2基本性質
習題
第3章單純形方法
3.1單純形方法原理
3.2兩階段法與大M法
3.3退化情形
3.4修正單純形法
*3.5變數有界的情形
*3.6分解演算法
習題
第4章對偶原理及靈敏度分析
4.1線性規劃中的對偶理論
4.2對偶單純形法
4.3原始對偶演算法
4.4靈敏度分析
*4.5含參數線性規劃
習題
第5章運輸問題
5.1運輸問題的數學模型與基本性
5.2表上作業法
5.3產銷不平衡運輸問題
習題
第6章線性規劃的內點演算法
*6.1Karmarkar演算法
*6.2內點法
6.3路徑跟蹤法
第7章最優性條件
7.1無約束問題的極值條件
7.2約束極值問題的最優性條件
*7.3對偶及鞍點問題
習題
*第8章演算法
8.1演算法概念
8.2演算法收斂問題
習題
第9章一維搜索
9.1一維搜索概念
9.2試探法
9.3函數逼近法
習題
第10章使用導數的最優化方法
10.1最速下降法
10.2牛頓法
10.3共軛梯度法
10.4擬牛頓法
10.5信賴域方法
10.6最小二乘
習題
第11章無約束最優化的直接方法
11.1模式搜索法
11.2Rosenbrock方法
11.3單純形搜索法
11.4Powell方法
習題
第12章可行方向法
12.1Zoutendijk可行方向法
12.2Rosen梯度投影法
*12.3既約梯度法
12.4Frank?Wolfe方法
習題
第13章懲罰函數法
13.1外點罰函數法
13.2內點罰函數法
*13.3乘子法
習題
第14章二次規劃
14.1Lagrange方法
14.2起作用集方法
14.3Lemke方法
14.4路徑跟蹤法
習題
*第15章整數規劃簡介
15.1分支定界法
15.2割平面法
15.301規劃的隱數法
15.4指派問
習題
第16章動態規劃簡介
16.1動態規劃的一些基本概念
16.2動態規劃的基本定理和基本方程
16.3逆推解法和順推解法
16.4動態規劃與靜態規劃的關系
16.5函數迭代法
習題
參考文獻

Ⅳ 什麼是高斯-牛頓演算法

用於解無約束最優化問題的

在解非線性方程組時,處理困難.因此用一個線性逼近(我理解是相似).
具體可以看運籌學或者是最優化書籍相關章節.

如果你已經看過了，那我也無能為力

Ⅳ 非線性最優的方法

最優化方法是一種數學方法，它是研究在給定約束之下如何尋求某些因素(的量)，以使某一(或某些)指標達到最優的一些學科的總稱。常見的最優化方法有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。

Ⅵ 牛頓法求解無約束最優化問題的方法

1. B6公式是從B2對x求導得到的

2. pk是定義的方向，沿著負梯度方向，後面是證明這樣確實是f(x)減小的方向。

   這些在《數值計算》這些書里都有。

Ⅶ 什麼是高斯-牛頓演算法 好像又有牛頓法，高斯法，牛頓-高斯法，找書也不好找啊

用於解無約束最優化問題的
在解非線性方程組時,處理困難.因此用一個線性逼近(我理解是相似).
具體可以看運籌學或者是最優化書籍相關章節.
如果你已經看過了,那我也無能為力

Ⅷ 最優化問題中，牛頓法為什麼比梯度下降法求解需要的迭代次數更少

不過牛頓法對初值的要求更為嚴格，很容易得到局部極小值

Ⅸ 用MATLAB體現牛頓高斯最優化方法

《應用最優化方法及MATLAB實現》系統講述如何將最優化方法實現為應用軟體。系統闡述了各種無約束和帶約束優化問題的計算方法和程序實現，內容包括：精確/非精確一維搜索、最速下降法、牛頓/擬牛頓法、共軛梯度法、單純形法、內點法、積極集法、序列二次規劃方法等。書中包含了必要的最優化理論知識，為得到最優化方法並用程序實現做准備。書中給出的許多應用優化技術是我們的最新研究成果，給出的優化程序是以專業編程技巧實現的最優化演算法。書中還給出了大量的例子和習題。《應用最優化方法及MATLAB實現》可作為高等院校自動化、控制、系統工程、工業工程、計算機、應用數學、經濟、管理、化工、材料、機械、能源等相關專業學生的教材，也可作為有關研究人員和工程技術人員的參考書。