最優(yōu)化方法,匯總

1、最優(yōu)化方法結(jié)課作業(yè)年級(jí)數(shù)學(xué)121班學(xué)號(hào)201200144209姓名李強(qiáng)1、幾種方法比較無約束優(yōu)化：不對定義域或值域做任何限制的情況下，求解目標(biāo)函數(shù)的最小值。這是因?yàn)閷?shí)際應(yīng)用中，許多情形被抽象為函數(shù)形式后均為凸函數(shù)，對于凸函數(shù)來說局部最小值點(diǎn)即為全局最小值點(diǎn)，因此只要能求得這類函數(shù)的一個(gè)最小值點(diǎn)，該點(diǎn)一定為全局最小值。(直接法：又稱數(shù)值方法，它只需計(jì)算目標(biāo)函數(shù)駐點(diǎn)的函數(shù)數(shù)值，而不是求其倒數(shù)，如坐標(biāo)輪換法，單純型法等。間接法：又稱解析法，是應(yīng)用數(shù)學(xué)極值理論的解析方法。首先計(jì)算出目標(biāo)函數(shù)的一階或一階、二階導(dǎo)數(shù)，然后根據(jù)梯度及海賽矩陣提供的信息，構(gòu)造何種算法，從而間接地求出目標(biāo)函數(shù)的最優(yōu)解，如牛頓法、

2、最速下降法共軛梯度法及變尺度法。)在優(yōu)化算法中保證整體收斂的重要方法就是線搜索法與信賴域法,這兩種算法既相似又有所不同。根據(jù)不同的線搜索準(zhǔn)則就延伸出不同的線搜索算法,譬如比較常見和經(jīng)典的最速下降法,牛頓法,擬牛頓法以及共輒梯度法等。一維搜索又稱線性搜索(LineSearch)，就是指單變量函數(shù)的最優(yōu)化,它是多變量函數(shù)最優(yōu)化的基礎(chǔ),是求解無約束非線性規(guī)劃問題的基本方法之一。一維搜索技術(shù)既可獨(dú)立的用于求解單變量最優(yōu)化問題,同時(shí)又是求解多變量最優(yōu)化問題常用的手段,雖然求解單變量最優(yōu)化問題相對比較簡單,但其中也貫穿了求解最優(yōu)化問題的基本思想。由于一維搜索的使用頻率較高,因此努力提高求解單變量問題算法的

3、計(jì)算效率具有重要的實(shí)際意義。在多變量函數(shù)的最優(yōu)化中，迭代格式Xk+1=Xk+akdk其關(guān)鍵就是構(gòu)造搜索方向dk和步長因子ak設(shè)(a)=f(xk+adk)這樣從凡出發(fā)，沿搜索方向dk,確定步長因子ak,使e(a)<e(0)的問題就是關(guān)于步長因子a的一維搜索問題。其主要結(jié)構(gòu)可作如下概括:首先確定包含問題最優(yōu)解的搜索區(qū)間，然后采用某種分割技術(shù)或插值方法縮小這個(gè)區(qū)間，進(jìn)行搜索求解。一維搜索通常分為精確的和不精確的兩類。如果求得ak使目標(biāo)函數(shù)沿方向dk達(dá)到極小，即使得f(xk+akdk)=minf(xk+adk)(a>0)則稱這樣的一維搜索為最優(yōu)一維搜索，或精確一維搜索,ak叫最優(yōu)步長因子;

4、如果選取ak使目標(biāo)函數(shù)f得到可接受的下降量，即使得下降量f(xk)一f(xk+akdk)>0是用戶可接受的,則稱這樣的一維搜索為近似一維搜索,或不精確一維搜索,或可接受一維搜索。由于在實(shí)際計(jì)算中,一般做不到精確的一維搜索,實(shí)際上也沒有必要做到這一點(diǎn),因?yàn)榫_的一維搜索需要付出較高的代價(jià),而對加速收斂作用不大,因此花費(fèi)計(jì)算量較少的不精確一維搜索方法受到了廣泛的重視和歡迎。精確一維搜索,作為一種理想的狀態(tài),雖然在實(shí)際計(jì)算中被采用的概率較之不精確一維搜索要小,但有關(guān)精確一維搜索技術(shù)的研究歷史悠久成果相當(dāng)豐富,方法眾多,其理論體系也相對比較完備,對其進(jìn)行進(jìn)一步的研究仍有著重要的理論意義和現(xiàn)實(shí)意義

5、。通常我們根據(jù)算法中有無使用導(dǎo)數(shù)的情況,將精確一維搜索算法分為兩大類:一類是不用函數(shù)導(dǎo)數(shù)的方法,這其中就包括二分法（又稱作對分法或中點(diǎn)法）、0.618法（黃金分割腳、Fibonacci法（分?jǐn)?shù)法）、割線法、成功一失敗法等;另一類是使用函數(shù)導(dǎo)數(shù)的方法,包括經(jīng)典的Newton法、拋物線法以及各種插值類方法等。（1）在不用導(dǎo)數(shù)的方法中,二分法、0.618法（黃金分割法）以及Fibonacci法均是分割方法,其基本思想就是通過取試探點(diǎn)和進(jìn)行函數(shù)值比較,使包含極小點(diǎn)的搜索區(qū)間不斷縮短,當(dāng)區(qū)間長度縮短到一定程度時(shí),區(qū)間上各點(diǎn)的函數(shù)值均接近函數(shù)的極小值,從而各點(diǎn)均可看作極小點(diǎn)的近似。分割類方法僅需計(jì)算函數(shù)值

6、,因此使用的范圍較廣,尤其適用于非光滑及導(dǎo)數(shù)表達(dá)式復(fù)雜或?qū)懖怀龅惹樾?。二分法是一種最簡單的分割方法,每次迭代都將搜索區(qū)間縮短一半,故二分法的收斂速度是線性的,收斂比為0.5,收斂速度較慢。其優(yōu)勢就是每一步迭代的計(jì)算量都相對較小,程序簡單,而且總能收斂到一個(gè)局部極小點(diǎn)。黃金分割法是一種針對目標(biāo)函數(shù)是單峰函數(shù)亦即目標(biāo)函數(shù)為凸的情形的分割類方法,因其不要求函數(shù)可微,且每次迭代只需計(jì)算一個(gè)函數(shù)值,程序簡單容易實(shí)現(xiàn)而被廣泛采用。由于黃金分割法是以等比例T=0.618分割縮小區(qū)間的,因此它是一種近似最優(yōu)方法。針對在實(shí)際中遇到的目標(biāo)函數(shù)往往不是單峰函數(shù)的情況HPonfiger（1976）提出了.0618法的

7、改進(jìn)形式，即在縮小區(qū)間時(shí),不只是比較兩個(gè)內(nèi)點(diǎn)處的函數(shù)值,而是對兩內(nèi)點(diǎn)及其兩端點(diǎn)處的函數(shù)值進(jìn)行綜合比較,以避免搜索得到的函數(shù)值反而比初始區(qū)間端點(diǎn)處的函數(shù)值大的情況。經(jīng)過這樣的修改,算法比.0618法要更加可靠。Fibonacci法是另一種與.0618法相類似的分割類方法,兩者的主要區(qū)別在于Fibonacci法搜索區(qū)間的縮短比率不是采用黃金分割數(shù)T，而是采用Fibonacci數(shù)列。在使用Fibonacci法時(shí),通常是由用戶給定最終區(qū)間長度的上限,從而確定探索點(diǎn)的個(gè)數(shù),逐步進(jìn)行搜索。通過對Fibonacci數(shù)列進(jìn)行分析表明,在迭代次數(shù)n趨于無窮的情形。Fibonacci法與.0618法的區(qū)間縮短率相

8、同,因而Fibonacci法的收斂速度也是線性的,收斂比也是黃金分割數(shù)T?？梢宰C明Fibonacci法是分割方法求解一維極小化問題的最優(yōu)策略而0.618法只是近似最優(yōu)的，但因0.618法不必預(yù)先知道探索點(diǎn)的個(gè)數(shù),程序?qū)崿F(xiàn)更加容易,因而應(yīng)用也更加廣泛。拋物線法也可稱作三點(diǎn)二次插值法,其基本思想與下面要敘述的牛頓法相同,也是用二次函數(shù)近似目標(biāo)函數(shù),并以其極小點(diǎn)去近似目標(biāo)函數(shù)的極小點(diǎn),不同之處是牛頓法是利用目標(biāo)函數(shù)fx()在X0處的二階Tyalor展式來逼近f(x),而拋物線法則是利用目標(biāo)函數(shù)fx()在三個(gè)點(diǎn)x0,xl,xZ處的函數(shù)值構(gòu)造一個(gè)二次函數(shù)作為其近似。一般地,拋物線法并不能保證算法一定收斂

9、,在迭代過程中有可能會(huì)出現(xiàn)相鄰迭代點(diǎn)xk，xk+1充分接近且xk+1并非函數(shù)近似極小點(diǎn)的退化情況。但在己知迭代點(diǎn)列收斂到目標(biāo)函數(shù)極小點(diǎn)的情況,可以證明:在一定的條件下,拋物線法是超線性收斂的,收斂的階約為1.3。割線法與分割法類似,也是通過取試探點(diǎn)和進(jìn)行函數(shù)值比較,使包含所求點(diǎn)的搜索區(qū)間縮小,但試探點(diǎn)的取法與分割法不同,它是選取連接兩個(gè)端點(diǎn)的線段與橫軸的交點(diǎn)作為試探點(diǎn)。割線法不能保證每次都使搜索區(qū)間縮小一定的比例,因而不具有全局線性收斂性,但是它卻利用了函數(shù)的一些性質(zhì)。在函數(shù)接近線性時(shí),它是非?？斓摹Ｈ绻瘮?shù)本身是線性函數(shù)時(shí),它可以一步找到解。(ii)一般地，使用導(dǎo)數(shù)的方法通常包括牛頓法、插值

10、法等，其中插值法又有一點(diǎn)二次插值法(牛頓法)、二點(diǎn)二次插值法)、三點(diǎn)二次插值法以及三次插值法、有理插植法等常用方法。求一維無約束極小化問題的牛頓法是從計(jì)算方法中方程求根的牛頓法演化而來的,其基本思想是用目標(biāo)函數(shù)f(x)在己知點(diǎn)x0處的二階Tylor展式g(x)來近似代替目標(biāo)函數(shù)，用g(x)的極小點(diǎn)作為f(x)的近似極小點(diǎn)，迭代公式是嘰一gy77忘牛頓法的優(yōu)點(diǎn)是收斂速度快,具有局部二階收斂速度;缺點(diǎn)是要在每個(gè)迭代點(diǎn)處計(jì)算函數(shù)的二階導(dǎo)數(shù)值,增加了每次迭代的工作量,而且它要求迭代初始點(diǎn)要選的好,也就是說初始點(diǎn)不能離極小值太遠(yuǎn),在極小點(diǎn)未知的情況下,做到這一點(diǎn)是很困難的,這就限制了算法的應(yīng)用范圍,導(dǎo)致

11、算法不實(shí)用。事實(shí)上,牛頓法也是插值類方法的一種。插值法是一類重要的一維搜索方法,其基本思想是在搜索區(qū)間內(nèi)不斷用低次(通常不超過三次)多項(xiàng)式來逼近目標(biāo)函數(shù),并用插值多項(xiàng)式的極小點(diǎn)去近似目標(biāo)函數(shù)的極小點(diǎn)。實(shí)踐表明,在目標(biāo)函數(shù)具有較好的解析性質(zhì)時(shí),插值方法比直接方法(如.0618或Fibonacci法)效果更好。所謂不精確一維搜索方法是指應(yīng)用各種可接受的步長選擇律的線性搜索方法。常用的不精確一維搜索算法包括利用簡單準(zhǔn)則的后退方法、經(jīng)典的Armijo-Goldstein方法Wolfe-Powell方法和強(qiáng)Wolfe-Powell方法、以及其后發(fā)展起來的利用Curry-Altman步長律、改進(jìn)的Curr

12、y-Altman步長律、Danilin-Pshenichuyi步長律、DeLeone-Grippo步長律、Backtracking步長律等的各種方法方法特占八、可靠性有效性簡便性備注度程特點(diǎn)度程特點(diǎn)度程特點(diǎn)問題大小接法坐標(biāo)輪換法對背中穩(wěn)問題舍入誤差不具低有收斂性程序簡高單，內(nèi)存少n<10鮑威爾法Si(k)有高高的共軛程度近似二次收斂性程序較繁,內(nèi)存量較大n<1020V接法梯度法舍入中誤差不具侑二次收斂性結(jié)構(gòu)簡高單，內(nèi)存少低維間牛頓法函數(shù)低次性要求嚴(yán)具有二次收斂性程序復(fù)低雜，內(nèi)存大低維變尺度法對函高數(shù)要求低高二高次收斂性程序較繁，內(nèi)存量一般高維V坐標(biāo)輪換法：可靠性較高，算法效率太低，

13、操作方便，一般只用于低維問題，n<10鮑威爾法：可靠性高，算法效率較高，操作較復(fù)雜，一般適用于n<1020的問題梯度法：可靠性較高，算法效率低，操作方便用于低維、低精度的問題。牛頓法：可靠性低，算法效率高，操作不方便，很少用。變尺度法：可靠性高(BFGS比DFP更高)，算法效率高，使用較復(fù)雜，適用于高維問題2、牛頓法如前面所提到的，最速下降法在最初幾步迭代中函數(shù)值下降很快外，總的說來下降的并不快，且愈接近極值點(diǎn)下降的愈慢。因此，應(yīng)尋找使目標(biāo)函數(shù)下降更快的方法。牛頓法就是一種收斂很快的方法，其基本思路是利用二次曲線來逐點(diǎn)近似原目標(biāo)函數(shù)，以二次曲線的極小值點(diǎn)來近似原目標(biāo)函數(shù)的極小值點(diǎn)并

14、逐漸逼近改點(diǎn)。一維目標(biāo)函數(shù)f(x)在x(k)點(diǎn)逼近用的二次曲線(即泰勒二次多項(xiàng)式)為9(x(k)=f(x(k)+f'(x(k)(x一x(k)+f"(X(k)(X一X(k)22此二次函數(shù)的極小點(diǎn)可由®'(x(k)=0求得。對于n維問題，n為目標(biāo)函數(shù)f(X)在X(k)點(diǎn)逼近用的二次曲線為：9(X(k)二f(x(k)+vf(X(k).X-X(k)+1X-X(k)T,v2f(X(k).X-X(k)2令式中的HessianV2f(X(k)=H(X(k)，則上式可改寫為：9(X(k)=f(x(k)+Vf(X(k).X-X(k)+丄X-X(k)t.H(X(k).X-X(k

15、)2沁f(X)當(dāng)V9(X)二0時(shí)可求得二次曲線9(X)的極值點(diǎn)，且當(dāng)且僅當(dāng)改點(diǎn)處的Hessian矩陣為正定時(shí)有極小值點(diǎn)。由上式得：V9(X)=Vf(X(k)+H(X(k)X-X(k)令V9(X)二0，則Vf(X(k)+H(X(k)X-X(k)=0若H(X(k)為可逆矩陣，將上式等號(hào)兩邊左乘H(X(k)-1，貝y得-1Vf(X(k)+1X-X(k)=0n整理后得X=X(k)-H(X(k)-1Vf(X(k)當(dāng)目標(biāo)函數(shù)/(X)是二次函數(shù)時(shí)，牛頓法變得極為簡單、有效，這時(shí)H(X(k)是一個(gè)常數(shù)矩陣，式確表達(dá)式，而利用式X二X(k)-H(X(k)-1Vf(X(k)作一次迭代計(jì)算所得的X就是最優(yōu)點(diǎn)X*。在

16、一般情況下/(X)不一定是二次函數(shù)，則不能一步就能求出極小值，即極小值點(diǎn)不在-H(X(k)-1Vf(X(k)方向上，但由于在X(k)點(diǎn)附近函數(shù)p(X)與/(X)是近似的，所以這個(gè)方向可以作為近似方向，可以用式X二X(k)-H(X(k)-1Vf(X(k)求出點(diǎn)X作為一個(gè)逼近點(diǎn)X(k+1)。這時(shí)式X=X(k)-H(X(k)-1Vf(X(k)可改成牛頓法的一般迭代公式：9(X(k)=f(x(k)+.X-X(k)+1X-X(k)T.H(X(k).X-X(k)變成精X(k+1)二X(k)-H(X(k)-1Vf(X(k)式中-h(X(k)-1Vf(X(k)稱為牛頓方向，通過這種迭代，逐次向極小值點(diǎn)X*逼近

17、。牛頓法是基于多元函數(shù)的泰勒展開而來的，它將-H(X(k)-1Vf(X(k)作為探索方向，因此它的迭代公式可直接寫出來：X(k+1)二X(k)-H(X(k)-1Vf(X(k)83、牛頓法實(shí)例分析例：試用牛頓法求目標(biāo)函數(shù)f(X)=x2+25x2的極小值點(diǎn)12解：設(shè)取x(k)=h2卜，貝ydx1dx2Id2/Idx2H(X(k)=V2f(X(k)=|iId2fIdxdx2i則，2xi50x24i00d2fIdxdxIdf|dx2I2X=X(k)X(k+1)=X(k)-H(X(k)-1Vf(X(k)I2I1I500II4II0III2I100II02III100III0II0If(X(k+1)=0，

18、故x(k+i)=o為極小點(diǎn)050例：試用牛頓法求目標(biāo)函數(shù)f(X)=x2+x2-xx-10x-4x+60的極小點(diǎn)。121212解：取x(k)=o0b,貝yVf(X(k)=dx1 dfdx2I-10III-4I2x-x-10I122x-x-4I2d2fH(X(k)=V2f(X(k)=IIdx1Id2fdxdx21d2fIdxdxIdf|dx2I2X=X(k)2-1-12X(k+1)=X(k)-IIH(X(k)II-1Vf(X(k)I0I1I21II-10II8III0I3II12III-4III6IX(k+1)=即為最小點(diǎn)X*，只迭代一次就達(dá)到了X*。6算法過程(1) 給定初始點(diǎn)x(o)，及精度