最速下降法與牛頓法及其區(qū)別

1、最速下降法與牛頓法及其區(qū)別摘要：無約束優(yōu)化方法是優(yōu)化技術(shù)中極為重要和基本內(nèi)容之一。它不僅可以直接用來求解無約束優(yōu)化問題，而且很多約束優(yōu)化問題也常將其轉(zhuǎn)化為無約束優(yōu)化問題，然后用無約束優(yōu)化方法來求解。最速下降法和牛頓法是比較常見的求解無約束問題的最優(yōu)化方法，這兩種算法作為基本算法，在最優(yōu)化方法中占有重要的地位。其中最速下降法又稱梯度法，其優(yōu)點(diǎn)是工作量少，存儲(chǔ)變量較少，初始點(diǎn)要求不高；缺點(diǎn)是收斂慢，效率低。牛頓法的優(yōu)點(diǎn)是收斂速度快；缺點(diǎn)是對(duì)初始點(diǎn)要求嚴(yán)格，方向構(gòu)造困難，計(jì)算復(fù)雜且占用內(nèi)存較大。同時(shí)，這兩種算法的理論和方法滲透到許多方面，特別是在軍事、經(jīng)濟(jì)、管理、生產(chǎn)過程自動(dòng)化、工程設(shè)計(jì)和產(chǎn)品優(yōu)化設(shè)

2、計(jì)等方面都有著重要的應(yīng)用。因此，研究最速下降法和牛頓法的原理及其算法對(duì)我們有著及其重要的意義。關(guān)鍵字：無約束優(yōu)化 最速下降法 牛頓法 Abstract: unconstrained optimization method is to optimize the technology is extremely important and basic content of. It not only can be directly used to solve unconstrained optimization problems, and a lot of constrained optimizati

3、on problems are often transformed into unconstrained optimization problem, and then use the unconstrained optimization methods to solve. The steepest descent method and Newton-Raphson method is relatively common in the unconstrained problem optimization method, these two kinds of algorithm as the ba

4、sic algorithm, the optimization method plays an important role in. One of the steepest descent method also known as gradient method, its advantages are less workload, storage variable is less, the initial requirements is not high; drawback is the slow convergence, low efficiency. Newtonian method ha

5、s the advantages of fast convergence speed; drawback is the initial point of strict construction difficulties, directions, complicated calculation and larger memory. At the same time, these two kinds of algorithm theory and methods into many aspects, especially in the military, economic, management,

6、 production process automation, engineering design and product optimization design has important applications. Therefore, to study the steepest descent method and Newton-Raphson method principle and algorithm for us with its important significance.Keywords: unconstrained optimization steepest descen

7、t method1、 算法的基本原理1. 1 最速下降法的基本原理在基本迭代公式中，每次迭代搜索方向取為目標(biāo)函數(shù)的負(fù)梯度方向，即，而每次迭代的步長(zhǎng)取為最優(yōu)步長(zhǎng)，由此確定的算法稱為最速下降法。為了求解問題，假定我們已經(jīng)迭代了次，獲得了第個(gè)迭代點(diǎn)?，F(xiàn)在從出發(fā)，可選擇的下降方法很多，一個(gè)非常自然的想法是沿最速下降方向（即負(fù)梯度方向)進(jìn)行搜索應(yīng)該是有利的，至少在鄰近的范圍內(nèi)是這樣。因此，去搜索方向?yàn)?為了使目標(biāo)函數(shù)在搜索方向上獲得最多的下降，沿進(jìn)行一維搜索，由此得到第個(gè)跌帶點(diǎn)，即，其中步長(zhǎng)因子按下式確定， . （1）顯然，令就可以得到一個(gè)點(diǎn)列,其中是初始點(diǎn)，由計(jì)算者任意選定。當(dāng)滿足一定的條件時(shí)，由式（

8、1）所產(chǎn)生的點(diǎn)列必收斂于的極小點(diǎn)。下面為書寫方便，記。因此.1.2 牛頓法的基本原理設(shè)最優(yōu)化問題為，其中二階可導(dǎo)，矩陣正定。不妨設(shè)經(jīng)過次迭代已獲點(diǎn)，現(xiàn)將在處展成二階泰勒公式，于是有顯然是二次函數(shù)，特別由假設(shè)知還是正定二次函數(shù)，所以是凸函數(shù)且存在唯一全局極小點(diǎn)。為求此極小點(diǎn)，令即可解得，亦即 。 （2）對(duì)照基本迭代公式易知，式（2）中的搜索方向 ， （3）步長(zhǎng)因子。換句話說從點(diǎn)出發(fā)沿搜索方向并取步長(zhǎng)即可得的極小點(diǎn)。因此，是直指點(diǎn)處近似二次函數(shù)的極小點(diǎn)的方向。此時(shí)稱為從點(diǎn)出發(fā)的方向。從初始點(diǎn)開始，每一輪從當(dāng)前迭代點(diǎn)出發(fā)，沿方向并取步長(zhǎng)的算法稱為牛頓法。2、 算法的迭代步驟及流程圖2.1 最速下降法

9、迭代步驟已知目標(biāo)函數(shù)及其梯度，終止限和.（1） 選定初始點(diǎn)，計(jì)算；置.（2） 作直線搜索：；計(jì)算.用終止準(zhǔn)則檢驗(yàn)是否滿足：若滿足，則打印最優(yōu)解，結(jié)束；否則，置，轉(zhuǎn)（2）（3） 最速下降法算法流程圖如圖所示.結(jié)束 終止準(zhǔn)則滿足？ 選定開始YN2.2 牛頓法迭代步驟已知目標(biāo)函數(shù)及其梯度，矩陣，終止限.（1） 選定初始點(diǎn)；計(jì)算；置.（2） 計(jì)算.（3） 由方程解出.（4） 計(jì)算.（5） 判別終止準(zhǔn)則是否滿足：若滿足，則打印最優(yōu)解結(jié)束；否則，置，轉(zhuǎn)（2）。牛頓法的流程如圖所示。終止準(zhǔn)則滿足？ 開始選定 N Y結(jié)束3、 實(shí)例分析分別用牛頓法和最速下降法求解,選取.3.1 最速下降法求解由題意可知，故.記

10、，則.為最佳步長(zhǎng)，應(yīng)滿足.則有或故有.繼續(xù)迭代，要經(jīng)過10次迭代才可滿足精度的要求，以下計(jì)算從略。3.2 牛頓法求解由題意可知,故有是正定矩陣。又.由（3）式計(jì)算.由計(jì)算.計(jì)算為故有.停止迭代，并輸出作為極小點(diǎn)。4、 算法的優(yōu)缺點(diǎn)分析4.1 最速下降法的優(yōu)缺點(diǎn)分析最速下降法的優(yōu)點(diǎn)是算法簡(jiǎn)單，每次迭代計(jì)算量小，占用內(nèi)存量小，且對(duì)初始點(diǎn)要求不高，即使從一個(gè)不好的初始點(diǎn)出發(fā)，往往也能收斂到局部極小點(diǎn)，但它有一個(gè)嚴(yán)重缺點(diǎn)就是收斂速度慢，特別是當(dāng)橢圓比較扁平時(shí)，最速下降法的收斂速度越慢。4.2 牛頓法的優(yōu)缺點(diǎn)分析牛頓法收斂速度非?？?，具有二次收斂的優(yōu)點(diǎn)，但它存在下面四個(gè)嚴(yán)重的缺點(diǎn)：（1） 每次迭代不能保證下降，當(dāng)矩陣非正定時(shí)，牛頓法的搜索將會(huì)失??；（2） 對(duì)初始點(diǎn)要求嚴(yán)格，一般要求比較接近或有利于接近極小點(diǎn)，但這在實(shí)際生活中很難辦到；（3） 在進(jìn)行迭代時(shí)可能求不出搜索方向；（4） 構(gòu)造困難，計(jì)算復(fù)雜，占用機(jī)器內(nèi)存較大。5、 設(shè)計(jì)總結(jié)通過上面的實(shí)例中兩種算法的對(duì)比，可以看出牛頓法對(duì)于二次正定函數(shù)只需作一次迭代就得到最優(yōu)解，特別是在極小點(diǎn)附近，收斂性很好、速度快，而最速下降法在極小點(diǎn)附近收斂速度很差。但牛頓