最優(yōu)化方法的應(yīng)用

1、最優(yōu)化方法 姓名 張 炯學(xué)號(hào) 201200144423一、一維搜索方法的分類為了每次縮短區(qū)間，只需要在區(qū)間內(nèi)再插入一點(diǎn)并計(jì)算其函數(shù)值。然而，對(duì)于插入點(diǎn)的位置，是可以用不同的方法來確定的。 黃金分割法 一類稱作解析法或函數(shù)逼近法：構(gòu)造一個(gè)插值函數(shù)來逼近原來函數(shù)，用插值函數(shù)的極小點(diǎn)作為區(qū)間的插入點(diǎn) 牛頓法、二次插值法等黃金分割法黃金分割法要求插入點(diǎn)a1、a2的位置相對(duì)于原區(qū)間a,b的兩端點(diǎn)具有對(duì)稱性，即黃金分割法的搜索過程2 出初始搜索區(qū)間a,b及收斂精度e，將l賦以0.618按前頁中坐標(biāo)點(diǎn)比例公式計(jì)算a1和a2 ，并計(jì)算其對(duì)應(yīng)的函數(shù)值f(aa1)和f（a2)。 比較函數(shù)值，利用進(jìn)退法縮短搜索區(qū)間

2、檢查區(qū)間是否縮短到足夠小和函數(shù)值是否收斂到足夠近，如果條件不滿足則返回到步驟如果條件滿足則取最后兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似值黃金分割法程序框圖牛頓法對(duì)于一維搜索函數(shù)，假定已給出極小點(diǎn)的一個(gè)較好的近似點(diǎn)a0，因?yàn)橐粋€(gè)連續(xù)可微的函數(shù)在極小點(diǎn)附近與一個(gè)二次函數(shù)很接近，所以可以在a0點(diǎn)附近用一個(gè)二次函數(shù)來逼近函數(shù)，即在點(diǎn)a0將f(a)進(jìn)行泰勒展開，并保留到二次項(xiàng)，有然后以二次函數(shù)的極小點(diǎn)作為極小點(diǎn)的一個(gè)新近似點(diǎn)，根據(jù)極值必要條件 得得牛頓法的計(jì)算步驟給定初始點(diǎn)a0，控制誤差e，令k=0計(jì)算f(x)在ak點(diǎn)的一階和二階導(dǎo)數(shù)利用牛頓法迭代公式求ak+1若|ak+1-ak|e，則求得近似解a*=a

3、k+1，停止計(jì)算，否則作第步令k=k+1，然后轉(zhuǎn)第步牛頓法的優(yōu)缺點(diǎn)最大優(yōu)點(diǎn)是收斂速度快缺點(diǎn)每一點(diǎn)處都要計(jì)算函數(shù)的導(dǎo)數(shù)和二階導(dǎo)數(shù)，因而增加了每次迭代的工作量用數(shù)值微分代替二階導(dǎo)數(shù)時(shí)，舍入誤差會(huì)影響牛頓法的收斂速度，當(dāng)二階導(dǎo)數(shù)很小時(shí)問題更嚴(yán)重牛頓法要求初始點(diǎn)選得比較好，即不能離極小點(diǎn)太遠(yuǎn)，否則在可能使極小化序列發(fā)散或收斂到非極小點(diǎn)二次插值法二次插值法又稱拋物線法，它的基本思路是：在尋求函數(shù)f()極小點(diǎn)的搜索區(qū)間內(nèi)，取三個(gè)點(diǎn)的函數(shù)值來構(gòu)造一個(gè)二次插值多項(xiàng)式p(),用它的極小點(diǎn)（第四個(gè)點(diǎn)）近似地作為原目標(biāo)函數(shù)的極小點(diǎn)。若近似程度不滿足精度要求時(shí)，可以反復(fù)使用此法，從四個(gè)點(diǎn)中選取三個(gè)點(diǎn)，使函數(shù)值呈現(xiàn)“高

4、-低-高”變化的前提下逐漸的縮短搜索區(qū)間，二次插值多項(xiàng)式的極小點(diǎn)就逼近原目標(biāo)函數(shù)的極小點(diǎn)。二次插值法區(qū)間縮短的4種情況 二次插值法的流程圖二、牛頓迭代法詳解牛頓迭代法（Newton's method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method），它是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。牛頓迭代法（Newton's method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method），它是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。多數(shù)方程不存在求根公式，因此求精確根非常困難，甚

5、至不可能，從而尋找方程的近似根就顯得特別重要。方法使用函數(shù)f(x）的泰勒級(jí)數(shù)的前面幾項(xiàng)來尋找方程f(x) = 0的根。牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點(diǎn)是在方程f(x) = 0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復(fù)根，此時(shí)線性收斂，但是可通過一些方法變成超線性收斂。另外該方法廣泛用于計(jì)算機(jī)編程中。設(shè)r是 的根，選取 作為r的初始近似值，過點(diǎn) 做曲線 的切線L，L的方程為 ，求出L與x軸交點(diǎn)的橫坐標(biāo) ，稱x1為r的一次近似值。過點(diǎn) 做曲線 的切線，并求該切線與x軸交點(diǎn)的橫坐標(biāo) ，稱 為r的二次近似值。重復(fù)以上過程，得r的近似值序列，其中， 稱為r的 次近似值，上式

6、稱為牛頓迭代公式。用牛頓迭代法解非線性方程，是把非線性方程 線性化的一種近似方法。把 在點(diǎn) 的某鄰域內(nèi)展開成泰勒級(jí)數(shù) ，取其線性部分（即泰勒展開的前兩項(xiàng)），并令其等于0，即 ，以此作為非線性方程 的近似方程，若 ，則其解為 ， 這樣，得到牛頓迭代法的一個(gè)迭代關(guān)系式： 。已經(jīng)證明，如果是連續(xù)的，并且待求的零點(diǎn)是孤立的，那么在零點(diǎn)周圍存在一個(gè)區(qū)域，只要初始值位于這個(gè)鄰近區(qū)域內(nèi)，那么牛頓法必定收斂。 并且，如果不為0, 那么牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結(jié)果的有效數(shù)字將增加一倍。1 軍人在進(jìn)攻時(shí)常采用交替掩護(hù)進(jìn)攻的方式，若在數(shù)軸上的點(diǎn)表示A，B兩人的位置，規(guī)定在前

7、面的數(shù)大于后面的數(shù)，則是A>B，B>A交替出現(xiàn)。但現(xiàn)在假設(shè)軍中有一個(gè)膽小鬼，同時(shí)大家又都很照顧他，每次沖鋒都是讓他跟在后面，每當(dāng)前面的人占據(jù)一個(gè)新的位置，就把位置交給他，然后其他人再往前占領(lǐng)新的位置。也就是A始終在B的前面，A向前邁進(jìn)，B跟上，A把自己的位置交給B（即執(zhí)行B = A），然后A 再前進(jìn)占領(lǐng)新的位置，B再跟上，直到占領(lǐng)所有的陣地，前進(jìn)結(jié)束。像這種兩個(gè)數(shù)一前一后逐步向某個(gè)位置逼近的方法稱為迭代法。迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程，跟迭代法相對(duì)應(yīng)的是直接法（或者稱為一次解法），即一次性解決問題。迭代算法是用計(jì)算機(jī)解決問題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算

8、速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對(duì)一組指令（或一定步驟）重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。利用迭代算法解決問題，需要做好以下三個(gè)方面的工作：一、確定迭代變量在可以用迭代算法解決的問題中，至少存在一個(gè)可直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。二、建立迭代關(guān)系式所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來完成。三、對(duì)迭代過程進(jìn)行控制在什么時(shí)候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地執(zhí)行下去。迭代過程的控制

9、通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí)現(xiàn)對(duì)迭代過程的控制；對(duì)于后一種情況，需要進(jìn)一步分析得出可用來結(jié)束迭代過程的條件。關(guān)于牛頓迭代法有一個(gè)很典型的例子是斐波那契（Fibonacci）數(shù)列。斐波那契數(shù)列為：0、1、1、2、3、5、8、13、21、，即 fib=0; fib=1;fib(n)=fib(n-1)+fib(n-2) （當(dāng)n>2時(shí)）。在n>2時(shí)，fib(n)總可以由fib(n-1)和fib(n-2)得到，由舊值遞推出新值，這是一個(gè)典型的迭代關(guān)系，所以我們可以考慮迭代算法

10、。int Fib(int n) /斐波那契（Fibonacci）數(shù)列if (n < 1）/*預(yù)防錯(cuò)誤*/return 0;if (n = 1 | n = 2)/*特殊值，無需迭代*/return 1;int f1 = 1,f2 = 1,fn;/*迭代變量*/int i;for(i=3; i<=n; +i)/*用i的值來限制迭代的次數(shù)*/fn = f1 + f2; /*迭代關(guān)系式*/f1 = f2;/f1和f2迭代前進(jìn)，其中f2在f1的前面f2 = fn;return fn;三、牛頓迭代法的程序?qū)崿F(xiàn)牛頓迭代法Matlab程序（帶下山因子）本文程序可用于求解線性和非線性方程組，在使用牛

11、頓迭代法的同時(shí)，加入了下山因子，加入下山因子后，對(duì)于初值的選取更為寬泛。使用方法：請(qǐng)將本文function所定義的函數(shù)存為m文件，將matlab路徑改為存儲(chǔ)newton函數(shù)的路徑，然后參照本文例子的格式定義變量、表達(dá)式、初值、收斂閾值、迭代次數(shù)后，輸入X=newton(f,x,x0,esp,N)即可求解。%例子syms x1 x2 x3%定義變量名稱f1=x1+x2+x3+3;f2=2*x1-x2-x3;f3=x1+2*x2-2*x3-3;%定義方程表達(dá)式（方程全都移到等號(hào)左邊的表達(dá)式）f=f1;f2;f3;x=x1;x2;x3;x0=0;0;0;%設(shè)定初值esp=0.00001;0.0000

12、1;0.00001;%閾值N=1000;%迭代次數(shù)X=newton(f,x,x0,esp,N)%求解%真值為-1 0 -2%function x1=newton(f,x,x0,esp,N)%此函數(shù)用于解非線性方程，方法為牛頓下山法。R=jacobian(f,x);ph=size(f,1);ty(1:ph,1)=1;coo=1;while abs(coo-1)<1e-6%這代表coo=1 coo=0;R1=subs(R,x,x0);%f1=subs(f,x,x0);x1=x0-ty.*(R1f1);f11=subs(f,x,x1);f12=double(f1);f112=double(f11);for i=1:size(f12,1); j=