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

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

2、面，特別是在軍事、經(jīng)濟(jì)、管理、生產(chǎn)過程自動化、工程設(shè)計和產(chǎn)品優(yōu)化設(shè)計等方面都有著重要的應(yīng)用。因此，研究最速下降法和牛頓法的原理及其算法對我們有著及其重要的意義。關(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, an

3、d a lot of constrained optimization 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

4、 two kinds of algorithm as the basic 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, lo

5、w efficiency. Newtonian method has 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 th

6、e military, economic, management, 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: unconstra

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

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

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

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