最優(yōu)化理論與方法-牛頓法

PAGEPAGE5牛頓法牛頓法作為求解非線性方程的一種經典的迭代方法，它的收斂速度快，有內在函數可以直接使用。結合著matlab可以對其進行應用，求解方程。牛頓迭代法（Newton’smethod）又稱為牛頓-拉夫遜方法（Newton-Raphsonmethod）,它是牛頓在17世紀提出的一種在實數域和復數域上近似求解方程的方法,其基本思想是利用目標函數的二次Taylor展開，并將其極小化。牛頓法使用函數的泰勒級數的前面幾項來尋找方程的根。牛頓法是求方程根的重要方法之一，其最大優(yōu)點是在方程的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復根，此時非線性收斂，但是可通過一些方法變成線性收斂。牛頓法的幾何解釋：方程的根可解釋為曲線與軸的焦點的橫坐標。如下圖：設是根的某個近似值，過曲線上橫坐標為的點引切線，并將該切線與軸的交點的橫坐標作為的新的近似值。鑒于這種幾何背景，牛頓法亦稱為切線法。2牛頓迭代公式：（1）最速下降法：以負梯度方向作為極小化算法的下降方向，也稱為梯度法。設函數在附近連續(xù)可微，且。由泰勒展開式：（*）可知，若記為，則滿足的方向是下降方向。當取定后，的值越小，即的值越大，函數下降的越快。由Cauchy-Schwartz不等式：，故當且僅當時，最小，從而稱是最速下降方向。最速下降法的迭代格式為：。（2）牛頓法：設是二次可微實函數，，Hesse矩陣正定。在附近用二次Taylor展開近似，，為的二次近似。將上式右邊極小化，便得：，這就是牛頓法的迭代公式。在這個公式里，步長因子。令，則上式也可寫成：顯然，牛頓法也可以看成在橢球范數下的最速下降法。事實上，對于，是極小化問題的解。該極小化問題依賴于所取的范數，當采取范數時，，所得方法為最速下降法。當采用橢球范數時，，所得方法即為牛頓法。對于正定二次函數，牛頓法一步即可達到最優(yōu)解。而對于非二次函數，牛頓法并不能保證有限次迭代求得最優(yōu)解，但由于目標函數在極小點附近近似于二次函數，故當初始點靠近極小點時，牛頓法的收斂速度一般是快的。牛頓法收斂定理：設，充分靠近，，如果正定，且Hesse矩陣滿足Lipschitz條件，即存在，使得對所有i,j，有：，其中是Hesse矩陣的元素，則對一切k，牛頓迭代公式有意義，且所得序列收斂到，并且具有二階收斂速度。在實際求解中，當初始點遠離最優(yōu)解時，Hesse矩陣不一定正定。牛頓方向不一定是下降方向，其收斂性不能保證。這說明恒取步長因子為1的牛頓法是不合適的，應該在牛頓法中采用某種一維搜索來確定步長因子。但是應該強調，僅當步長因子收斂到1時，牛頓法才是二階收斂的。這時牛頓法的迭代公式為：，其中是一維搜索產生的步長因子。帶步長因子的牛頓法步1選取初始數據，取初始點，終止誤差，令。步2計算。若，停止迭代，輸出，否則進行步3.步3解方程組構造牛頓方向，即解，求出。步4進行一維搜索，求使得，令轉步2牛頓法的計算步驟：步驟1準備選定初始近似值，計算，。步驟2迭代按公式：迭代一次，得新的近似值，，。步驟3控制如果滿足，或，則終止迭代，以作為所求的根；否則轉步驟4.此處，是允許誤差，而：其中C是取絕對誤差或相對誤差的控制常數，一般可取。步驟4修改如果迭代次數達到預先制定的次數N，或者，則方法失?。环駝t以代替，轉步驟2繼續(xù)迭代。4牛頓法的改進在優(yōu)化問題的計算中，牛頓迭代法是非線性方程求根中一種很實用的方法，它具有簡單的迭代格式和較快的收斂速度，它二次收斂到單根，線性收斂到重根。數值計算中的經典牛頓法面臨的主要問題是Hesse矩陣不正定，這時候二次模型不一定有極小點，甚至沒有平穩(wěn)點。當不定時，二次模型函數是無界的。Goldstein和Price（1967）提出當非正定時，采用最速下降方向。Goldfeld等人（1966年）提出了一種修正方法，即使牛頓方向偏向最速下降方向。更明確的說，就是將模型的Hesse矩陣改變成，其中，使得正定。該算法的框架如下：給出初始點。第k步迭代為：（1）令，其中：，如果正定；否則。（2）計算的Cholesky分解，。（3）解得。（4）令牛頓法的優(yōu)點是收斂快，缺點一是每步迭代要計算，計算量較大且有時計算較困難，二是初始近似值只在根附近才能保證收斂，如給的不合適可能不收斂。為克服這兩個缺點，通?？梢韵率鰞蓚€方法：（1）簡化牛頓法，也稱平行弦法。其迭代公式為，迭代函數。（2）牛頓下山法：牛頓法的收斂性依賴于初始值的選取。如果偏離所求根較遠，則牛頓法可能發(fā)散。為防止迭代發(fā)散，對迭代過程再附加一項要求，即具有單調性：滿足這項要求的算法稱下山