最優(yōu)化理論方法

1、牛頓法牛頓法作為求解非線性方程的一種經(jīng)典的迭代方法，它的收斂速度快，有內(nèi)在 函數(shù)可以直接使用。結(jié)合著 matlab可以對其進(jìn)行應(yīng)用，求解方程。牛頓迭代法(Newton' method)又稱為牛頓-拉夫遜方法(Newton-Raphson method)，它是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法 ， 其基本思想是利用目標(biāo)函數(shù)的二次 Taylor展開，并將其極小化。牛頓法使用函數(shù)f x的泰勒級數(shù)的前面幾項(xiàng)來尋找方程 f x =0的根。牛頓法是求方程根的重要方法之一，其最大優(yōu)點(diǎn)是在方程 f x =0的單根附近具有平方收斂，而且該法還 可以用來求方程的重根、復(fù)根，此時非

2、線性收斂，但是可通過一些方法變成線性 收斂。牛頓法的幾何解釋: 方程f x =0的根x*可解釋為曲線y = f x與x軸的焦點(diǎn)的橫坐標(biāo)。如下圖:設(shè)Xk是根x*的某個近似值，過曲線y二f x上橫坐標(biāo)為兀的點(diǎn)Pk引切線，并 將該切線與x軸的交點(diǎn) 的橫坐標(biāo)Xk 1作為x*的新的近似值。鑒于這種幾何背景， 牛頓法亦稱為切線法。2牛頓迭代公式:(1)最速下降法:以負(fù)梯度方向作為極小化算法的下降方向，也稱為梯度法。設(shè)函數(shù)f x在Xk附近連續(xù)可微，且gkXk =0。由泰勒展開式：f X= f kXX kX ' f k X：Xk X (*)可知，若記為xXk =dk，則滿足d：gk ：0的方向dk是下

3、降方向。當(dāng):-取定后， d：gk的值越小，即-d：gk的值越大，函數(shù)下降的越快。由 Cauchy-Schwartz不等 式：dT g| d| 0k，故當(dāng)且僅當(dāng)dk=-gk時，d：gk最小，從而稱-gk是最速下降 方向。最速下降法的迭代格式為：兀-二 Xk-kg。(2)牛頓法：設(shè)f x是二次可微實(shí)函數(shù)，xk Rn，Hesse矩陣2 f xk正定。在兀附近用二次Taylor展開近似f，f 仇 +sq叫s )= f (Xk )丁 s"f 仏)丁 s+*sTN2f g )ss=x-xk， qf s)為f(x)的二次近似。將上式右邊極小化，便得：Xk仃Xk - |2 f Xk f Xk，這就是

4、牛頓法的迭代公式。在這個公式里，步長因子:k =1。令Gk八2 fx,gk八fxk，貝U上式也可寫成：1Xk i 二 Xk - Gk gk顯然，牛頓法也可以看成在橢球范數(shù)|人下的最速下降法。事實(shí)上，對于f Xk S、f Xk - g：s，TSk是極小化冋題當(dāng)采取12范gk s的解。該極小化問題依賴于所取的范數(shù),S數(shù)時，s -gk，所得方法為最速下降法。當(dāng)采用橢球范數(shù)G時,Sk = -Ggk，所得方法即為牛頓法。對于正定二次函數(shù)，牛頓法一步即可達(dá)到最優(yōu)解。 而對于非二次函數(shù)，牛頓法并 不能保證有限次迭代求得最優(yōu)解，但由于目標(biāo)函數(shù)在極小點(diǎn)附近近似于二次函 數(shù)，故當(dāng)初始點(diǎn)靠近極小點(diǎn)時，牛頓法的收斂速

5、度一般是快的。牛頓法收斂定理：設(shè)f C 2，兀充分靠近X*,，f x* = 0 ,如果12 f x*正定，且Hesse矩陣G x滿足Lipschitz條件，即存在一：.0，使得對所有i,j，有：Gj(x)Gj (yy，其中Gij x是Hesse矩陣G x的i,j元素，則對一切k，牛頓迭代公式有意義，且所得序列兀？收斂到x*，并且具有二階收斂速度。在實(shí)際求解中，當(dāng)初始點(diǎn)遠(yuǎn)離最優(yōu)解時，Hesse矩陣Gk不一定正定。牛頓方向不一定是下降方向，其收斂性不能保證。這說明恒取步長因子為1的牛頓法是 不合適的，應(yīng)該在牛頓法中采用某種一維搜索來確定步長因子。但是應(yīng)該強(qiáng)調(diào)， 僅當(dāng)步長因子:收斂到1時，牛頓法才是

6、二階收斂的。這時牛頓法的迭代公式 為：Xkkd其中:k是一維搜索產(chǎn)生的步長因子。帶步長因子的牛頓法步1選取初始數(shù)據(jù)，取初始點(diǎn)xd，終止誤差； 0，令k: = 0。 步2計(jì)算gk。若|gk| £芯，停止迭代，輸出Xk，否則進(jìn)行步3.步3解方程組構(gòu)造牛頓方向，即解 Gkd二-gk，求出dk。步4進(jìn)行一維搜索，求 亠使得f x k dk = mi nf x， a令Xk 1 二Xk dk,k : = k 1 轉(zhuǎn)步 2牛頓法的計(jì)算步驟:步驟1準(zhǔn)備選定初始近似值X），計(jì)算fo =f ( Xo )，fo=f (Xo )。步驟2迭代按公式：Xifo=xof0迭代一次，得新的近似值Xi，fi=f (X

7、i )，1 1f1 = f(X-1 )。步驟3控制女口果X1滿足卩£坷，或t S，則終止迭代，以X1作為所求的根；否則轉(zhuǎn)步驟4.此處，；1, ；2是允許誤差，而: Xo ,當(dāng)刈cC時；°F二,當(dāng)卜存c時，其中C是取絕對誤差或相對誤差的控制常數(shù)，一般可取 c = 10步驟4 修改 如果迭代次數(shù)達(dá)到預(yù)先制定的次數(shù) N，或者f；=0 ,則方法失敗;否則以 心辦"'代替Xo, fo, fo，轉(zhuǎn)步驟2繼續(xù)迭代。4牛頓法的改進(jìn)在優(yōu)化問題的計(jì)算中，牛頓迭代法是非線性方程求根中一種很實(shí)用的方法，它具有簡單的迭代格式和較快的收斂速度，它二次收斂到單根，線性收斂到重根。 數(shù)值

8、計(jì)算中的經(jīng)典牛頓法面臨的主要問題是 Hesse矩陣Gk不正定，這時候二次模型不一定有極 小點(diǎn)，甚至沒有平穩(wěn)點(diǎn)。當(dāng)Gk不定時，二次模型函數(shù)是無界的。Goldstein和Price（ 1967）提出當(dāng)Gk非正定時，采用最速下降方向-gk。Goldfeld 等人（1966年）提出了一種修正方法，即使牛頓方向偏向最速下降方向 -gk。更 明確的說，就是將模型的Hesse矩陣Gk改變成Gk vkI，其中vk - 0 ,使得Gk vkI 正定。該算法的框架如下：給出初始點(diǎn)X。 Rn。第k步迭代為：(1 令 Gk =Gk vkI，其中：Vk = 0 ,如果Gk正定；Vk 0,否則。(2) 計(jì)算 Gk 的 C

9、holesky 分解，Gk 二 LkD：。(3) 解 Gk d = -gk 得 dk。(4) 令 Xk 1 二 Xk dk牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)一是每步迭代要計(jì)算f Xk及f' Xk ,計(jì)算量較大且有時f' Xk計(jì)算較困難，二是初始近似值 X0只在根X*附近才能保證收斂， 如X0給的不合適可能不收斂。為克服這兩個缺點(diǎn)，通?？梢韵率鰞蓚€方法：(1) 簡化牛頓法，也稱平行弦法。其迭代公式為，Xk 1 二Xk -Cf Xk ,C =0,1川|迭代函數(shù)Xjux-Cf X。(2) 牛頓下山法：牛頓法的收斂性依賴于初始值 X0的選取。如果X0偏離所求根 X*較遠(yuǎn)，則牛頓法可能發(fā)散。為防止迭代發(fā)散， 對迭代過程再附加一項(xiàng)要求，即 具有單調(diào)性：f (Xk+ p f (xj滿足這項(xiàng)要求的算法稱下山法。將牛頓法與下山法結(jié)合