牛頓法(Newton's method)是一種在實數域和復數域上近似求解方程的方法,，它使用函數f(x)的泰勒級數的前面幾項來尋找方程f(y)=0的根。 牛頓法最初由艾薩克·牛頓在《Method of Fluxions》(1671年完成，1736年公開發表)中提出。約瑟夫·鮑易也曾于1690年在Analysis Aequationum中提出此方法。

目錄

1. 問題提出?

2. 基本思想?

3. 迭代公式

4. 算法步驟?

5. 算法收斂性?

6. 解的情況

7. 阻尼牛頓法

8. 算法實現

9. 算法評價

1問題提出

對于無約束優化模型

其中為二階連續光滑且Hessian陣可逆。

2基本思想

用一個二次函數去近似目標函數f(x),然后精確地求出這個二次函數的極小點.

Newton法幾何解釋

3迭代公式

?Newton法的迭代公式為：

其中稱為牛頓方向。

考慮函數f(x)在點處的二次泰勒近似

由于可逆，則的一階穩定點滿足，即

由上式可得

這正是牛頓法的迭代公式。由此說明，牛頓法在每次迭代中考慮函數在當前的局部二次泰勒展開，其迭代步長為1，迭代方向是梯度方向經過Hessian逆陣的調整。如果函數f為凸函數，此時正定，從而,即牛頓方向是下降方向。

4算法步驟

牛頓法的算法步驟如下：

Step 0.?選取初始點，允許誤差ε>?0，令 k=1；

Step 1.?計算。若,算法停止；.否則，轉 Step 2；

Step 2.?計算。置k=k+1，轉 step 1.

5算法收斂性

這里討論牛頓算法的局部收斂性質，這是由于Hessian陣可能不總是正定，即牛頓方向可能不總是下降方向。我們假設目標函數f為凸函數，二階連續可微，最優解處正定。此時，在附近的點，其也是正定的。從而牛頓方法是有定義的，并且在迭代步長最終取1的情況下具有二次收斂性。

定理：假設函數f二階可微，其Hessian陣在最優解的鄰域是Lipschitz連續的，且在處滿足充分條件且正定。考慮迭代公式，則下面結論成立：

(i)如果初始點充分接近解點,算法產生的點列收斂到;

(ii)點列收斂速率是二次的；

(iii)梯度模長的點列二次收斂到0.

6解的情況

用Newton法求解無約束問題會出現以下情形：

• 算法收斂到極小點；

• 算法收斂到鞍點；

• Hesse矩陣不可逆，無法迭代下去。

7阻尼牛頓法

牛頓法的有效性嚴重依賴初始點的選擇，即初始點需要充分靠近極小值點，否則可能導致算法不收斂。由于實際問題的精確最小值點一般是不知道的，因此初始點的選擇給算法的實現帶來了很大的挑戰。為了解決這一問題，可引入線搜索技術以得到大范圍的收斂算法，即阻尼牛頓法。

阻尼牛頓法的算法步驟如下：

Step 0.?選取初始點，允許誤差ε>?0，令 k=1；

Step 1.?計算。若,算法停止；.否則，轉 Step 2；

Step 2.?取搜索方向，利用線搜索技術確定步長;

Step 3.?令。置k=k+1，轉 step 1.

8算法實現

例1：求解無約束優化問題

該問題有精確解

解：

方法1：牛頓法法

使用 MATLAB 編寫最速下降法的主函數如下：

function [X,Y,Error] = Newton(x0)

%使用牛頓法求解無約束問題：min f(x)

%輸入：x0為初始點，fun為目標函數，grad為梯度函數

%輸出:X,Y分別為每一步的迭代點及相應函數值，Error為誤差

tic

%% 定義目標函數及導函數信息(可以根據需要進行修改)

f = @(x)100*(x(1)^2-x(2))^2+(x(1)-1)^2;???????????????????? ?%目標函數

g = @(x)[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1);-200*(x(1)^2-x(2))];?? %一階導數

G = @(x)[1200*x(1)^2-400*x(2)+2,-400*x(1);-400*x(1), 200 ];? ??%二階導數??

%% 初始化算法參數

n = 1;

e = norm(g(x0));

X = x0;

Y = f(x0);

Error = e;

%% 設定終止條件

N = 5000; ???????????????????????????????????????%最大迭代步

E = 1e-6;??????????????????? ?????????????????????%給定誤差

%% 迭代

while n < N && e > E

??? n = n+1;

??? %判斷Hesse矩陣是否可逆

??? ifdet(G(x0)) == 0

???????disp('Hesse矩陣不可逆，無法進行迭代！');

???? ???break

??? else

??????? d =-inv(G(x0))*g(x0);???????????????????? %迭代方向

??????? x0 =x0+d;?????????? ????????????????????%迭代公式

??????? X(:,n)= x0;

??????? Y(n) =f(x0);

??????? e =norm(g(x0));

???????Error(n) = e;

??? end

end

toc

end

調用格式如下：

x0 = [0;0];???????????????? %迭代初始點(可以根據需要修改)

[X,Y,E]=Newton(x0);

本問題求解結果如下：

方法2：阻尼牛頓法

使用 MATLAB 編寫最速下降法的主函數如下：

function [X,Y,Error] =ZNNewton(x0)

%使用阻尼牛頓法求解無約束問題：min f(x)

%使用非精確Armijo搜索步長規則

%輸入：x0為初始點，fun為目標函數，grad為梯度函數

%輸出:X,Y分別為每一步的迭代點及相應函數值，Error為誤差

tic

%% 初始化參數

f = @(x)100*(x(1)^2-x(2))^2+(x(1)-1)^2;??????????????????????? %目標函數

g =@(x)[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1);-200*(x(1)^2-x(2))];??? %一階導數

G =@(x)[1200*x(1)^2-400*x(2)+2, -400*x(1);-400*x(1), 200 ];???? ?%二階導數??

%% 初始化算法參數

n = 1;

e = norm(g(x0));

X = x0;

Y = f(x0);

Error = e;

beta=0.5;sigma=0.4;

%% 設定終止條件

N = 5000;?????????????????????????????????????? %最大迭代步???????????????

E = 1e-6;??????? ????????????????????????????????%給定誤差

%% 迭代

while n < N &&e > E

??? n = n+1;

??????? %判斷Hesse矩陣是否可逆

??????? if det(G(x0)) == 0

? ??????????disp('Hesse矩陣不可逆，無法進行迭代！');

??????????? break

??????? else

??????????? d = -inv(G(x0))*g(x0);???????????????? %迭代方向

??????????? %使用Armijo法求步長

??????????? m=0; mk=0;

??????????? while(m<20)

???????????????if(f(x0+beta^m*d)

??????????????????? mk=m; break;

??????????????? end

??????????????? m=m+1;

??????????? end

??????????? x0 = x0+beta^mk*d;?????????????????? %迭代公式

??????????? X(:,n) = x0;

?????????? ?Y(n) = f(x0);

??????????? e = norm(g(x0));

??????????? Error(n) = e;

??????? end

end

toc

end

調用格式如下：

x0 = [0;0];???????????????? %迭代初始點(可以根據需要修改)

[X,Y,E]=ZNNewton(x0);

本問題求解結果如下：

9算法評價

1)優點:

• Newton法產生的點列若收斂，則收斂速度快---具有至少二階收斂速率；

• Newton法具有二次終止性，即對強凸函數Newton法只需迭代一次就能得到最優值。

2)缺點:

• Newton法可能會出現在某步迭代時，目標函數值上升；

• 當初始點遠離極小點時，Newton法產生的點列可能不收斂，或者收斂到鞍點，或者Hesse矩陣不可逆，無法計算；

• Newton法需要計算Hesse矩陣，計算量大.

往期回顧

算法丨優化算法之最速下降法

算法丨經典優化算法大合集(比賽備用，值得收藏)

算法丨優化算法系列之遺傳算法原理

算法丨優化算法系列之遺傳算法MATLAB程序設計及應用實例

算法丨優化算法系列之模擬退火算法(1)

算法丨優化算法系列之模擬退火算法(2)——0-1背包問題

參考文獻：馬昌鳳.最優化方法及其 Matlab 程序設計[M]. 科學出版社, 2010.

總結

以上是生活随笔為你收集整理的matlab共轭梯度法_优化算法之牛顿法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。