目標(biāo)函數(shù)的幾種極值求解方法

1、目標(biāo)函數(shù)極值求解的幾種方法題目：min（Xi-22+2（x2-125取初始點(diǎn)xt）=（1,3/，分別用最速下降法，牛頓法，共腕梯度法編程實(shí)現(xiàn)。一維搜索法：迭代下降算法大都具有一個(gè)共同點(diǎn)，這就是得到點(diǎn)x（k歸需要按某種規(guī)則確定一個(gè)方向d），再?gòu)膞（k出發(fā)，7&方向d（k在直線（或射線）上求目標(biāo)函數(shù)的極小點(diǎn)，從而得到x（k的后繼點(diǎn)xf）,重復(fù)以上做法，直至求得問題的解，這里所謂求目標(biāo)函數(shù)在直線上的極小點(diǎn)，稱為一維搜索。一維搜索的方法很多，歸納起來大體可以分為兩類，一類是試探法：采用這類方法，需要按某種方式找試探點(diǎn)，通過一系列的試探點(diǎn)來確定極小點(diǎn)。另一類是函數(shù)逼近法或插值法：這類方法是用某種

2、較簡(jiǎn)單的曲線逼近本來的函數(shù)曲線，通過求逼近函數(shù)的極小點(diǎn)來估計(jì)目標(biāo)函數(shù)的極小點(diǎn)。本文采用的是第一類試探法中的黃金分割法。原理書上有詳細(xì)敘述，在這里介紹一下實(shí)現(xiàn)過程：（1）置初始區(qū)間ai,bi及精度要求L>0,計(jì)算試探點(diǎn)%和），計(jì)算函數(shù)值f（t邢f儼11計(jì)算公式是：X,=a1+0.382&a1）,21=a1+0.618bl-a1）。令k=1。若bkak<L則停止計(jì)算。否則，當(dāng)f®）>f儼k）時(shí)，轉(zhuǎn)步驟；當(dāng)“般）4f仁叫，轉(zhuǎn)步驟。置涿書=&，bk«=bk,人書=也，也中=烝書+0.618（bk書ak書），計(jì)算函數(shù)值f（k）,轉(zhuǎn)。置ak書=ak,b

3、k由=此,收書=叫，-k+=ak+0.3820由ak+）,計(jì)算函數(shù)值“£水）轉(zhuǎn)。置卜二卜+1返回步驟（2）01.最速下降法實(shí)現(xiàn)原理描述：在求目標(biāo)函數(shù)極小值問題時(shí)，總希望從一點(diǎn)出發(fā)，選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向，以利于盡快達(dá)到極小點(diǎn)，正是基于這樣一種愿望提出的最速下降法，并且經(jīng)過一系列理論推導(dǎo)研究可知，負(fù)梯度方向?yàn)樽钏傧陆捣较?。最速下降法的迭代公式是x（k*）=xC）+均d（k），其中d（k是從x（k）出發(fā)的搜索方向，這里取在點(diǎn)xf向最速下降方向,即dL-Vf（xk）。限是從x（k）出發(fā)沿方向d（k）進(jìn)行的一維搜索步長(zhǎng)，滿足f（xf）十嬴d（k）=minf（x（k）+Kd（k）。-

4、0實(shí)現(xiàn)步驟如下：給定初點(diǎn)xQwRn,允許誤差O0,置k=1。計(jì)算搜索方向d6=-fxk）。若M卜名，則停止計(jì)算；否則，從x（k加發(fā)，7&方向d（k世行的一維搜索，求,使f僅2+?%d）=minf（x2+九d（k）。0（4）x（k*Lx（k）+，*d2,置卜=卜+1返回步驟。2 .擬牛頓法基本思想是用不包括二階導(dǎo)數(shù)的矩陣近似牛頓法中的Hesse矩陣的逆矩陣，因構(gòu)造近似矩陣的方法不同，因而出現(xiàn)了不同的擬牛頓法。牛頓法迭代公式：x（k*Lx（k）+）*d（k）,d（k）是在點(diǎn)x（k）處的牛頓方向，d（）=-V2f（xNfvf（x）,均是從x（k柏發(fā)沿牛頓方向d（k進(jìn)行搜索的最優(yōu)步長(zhǎng)。用不包括

5、二階導(dǎo)數(shù)的矩陣Hk近似取代牛頓法中的Hesse矩陣的逆矩陣v2f（x）廣,Hk卡需滿足擬牛頓條件。實(shí)現(xiàn)步驟：給定初點(diǎn)x1）,允許誤差名下0。置Hi=In（單位矩陣），計(jì)算出在xQ）處的,$度gi=Vf（xt）,置k=1o令d（k）=-Hkgk。從x（k）出發(fā)沿方向d（k）搜索，求步長(zhǎng)鼠，使它滿足f（x）+4d，）=min（x2+h2）令x（k+）=x1）+Kkd（k）。.：._0檢驗(yàn)是否滿足收斂標(biāo)準(zhǔn)，若fy（k"M2,則停止迭代，得到點(diǎn)X=x（k幸）,否則進(jìn)行步驟。若卜二口，令xCLxfk*）,返回；否則進(jìn)行步驟。令g«=fxS）,p2=x”）-x（k）,q2=gkgk，置

6、k=k+1 。返回HHPkPkTHkqkqkTHHk1k7一qkTHkqk3 .共軻梯度法若dQdC'dC）是Rn中k個(gè)方向，它們兩兩關(guān)于A共腕，即滿足dTAd（j）=0,i*j;i,j=1,，k,稱這組方向?yàn)锳的k個(gè)共腕方向。共腕梯度法的基本思想是把共腕性與最速下降法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共腕方向，并沿這組方向進(jìn)行搜索，求出目標(biāo)函數(shù)的極小點(diǎn)，根據(jù)共腕方向的基本性質(zhì)這種方法具有二次終止性。實(shí)現(xiàn)步驟如下：給定初點(diǎn)x（）,允許誤差40,置yC）=xf）,dC）="f（y。），k=j=1O若fy（j）bw,則停止計(jì)算；否則，作一維搜索，求%,滿足fyj%d（j»

7、;=minf（y（j）+九d（j»,令y（j*）=y（j）+九jd（j）。0若j<n,則進(jìn)行步驟，否則進(jìn)行步驟“yj”2令d（j”=-fy（g）HBjd（j）,其中Bj=24-，置可+1，轉(zhuǎn)?！皔j令x3+）=y"），y0）=x（k+）,d，）=Wf（y，），置j=1,k=k+1,轉(zhuǎn)。4.實(shí)驗(yàn)結(jié)果用以上三種方法通過Matlab編程得到實(shí)驗(yàn)數(shù)據(jù)。初始值xC)=(1,3)T。迭代精度sum(abs(x1-x).A2)<1e-4。最速卜降法擬牛頓法共腕梯度法第一次迭代結(jié)果xF)xQi)1.51516312861.51516312861.5151631286x42)0.

8、93934748540.9393474850.9393474854第二次迭代結(jié)果xf)xHn1.97300822752.01081080722.0000076259x.2)1.05389923740.98615771081.0000419788第三次迭代結(jié)果x(4)x(421.98691339342.0054101622.0000038167x(40.99836543780.98962692400.9999998271第四次迭代結(jié)果xf)xnD1.9992739761x2)1.0014531964實(shí)驗(yàn)結(jié)果分析：由上表格可以看到最速下降法需要四次迭代實(shí)現(xiàn)所要求的精度，擬牛頓法和共腕梯度法需要三次

9、。程序：%精確一維搜索法的子函數(shù)，0.618(黃金分割)法，gold.m%俞入的變量x為初始迭代點(diǎn)是二維的向量，d為初始迭代方向是二維的向量%俞出變量是在0,10區(qū)間上使函數(shù)取得極小值點(diǎn)的步長(zhǎng)因子functionalfa=gold(x,d)a=0;b=10;tao=0.618;lanmda=a+(1-tao)*(b-a);mu=a+tao*(b-a);alfa=lanmda;%初始化f=(x(1)+alfa*d(1)-2)A2+2*(x(2)+alfa*d(2)-1)A2;%目標(biāo)函數(shù)m=f;alfa=mu;n=f;while1ifm>nifabs(lanmda-b)<1e-4alf

10、a=mu;returnelsea=lanmda;lanmda=mu;m=n;mu=a+tao*(b-a);alfa=mu;n=(x(1)+alfa*d(1)-2)A2+2*(x(2)+alfa*d(2)-1)A2;endelseifabs(mu-a)<1e-4alfa=lanmda;returnelseb=mu;mu=lanmda;n=m;lanmda=a+(1-tao)*(b-a);alfa=lanmda;m=(x(1)+alfa*d(1)-2)A2+2*(x(2)+alfa*d(2)-1)A2;endendend%弟度子函數(shù)，tidu.m,輸入的變量為二維的向量，返回梯度在x處的數(shù)值

11、向量functiong=tidu(x)%待求解的函數(shù)f=(x(1)-2)A2+2*(x(2)-1)A2;%求函數(shù)的梯度表達(dá)式g=2*(x(1)-2)4*(x(2)-1);x1=x(1);x2=x(2);%!速下降法極小化函數(shù)的通用子函數(shù)zuisu.m%俞入變量為初始的迭代點(diǎn)，輸出變量為極小值點(diǎn)functionx0=zuisu(x)%斷梯度范數(shù)是否滿足計(jì)算精度1e-4的要求.是,標(biāo)志變量設(shè)為1,輸出結(jié)果;%5,標(biāo)志變量設(shè)為0ifsum(abs(tidu(x).A2)<1e-4flag=1;x0=x;elseflag=0;end%循環(huán)求解函數(shù)的極小點(diǎn)whileflag=0d=-tidu(x)

12、;a=gold(x,d);x=x+a*d%判斷梯度范數(shù)是否滿足計(jì)算精度的要求.是,標(biāo)志變量設(shè)為1,輸出結(jié)果；%否，標(biāo)志變量設(shè)為0,繼續(xù)迭代ifsum(abs(tidu(x).A2)<1e-4flag=1;x0=x;elseflag=0;endEnd%以牛頓法極小化函數(shù)的通用子函數(shù)，gonge.m%俞入變量為初始的迭代點(diǎn)，輸出變量為極小值點(diǎn)functionx0=ninewton(x)師U斷梯度范數(shù)是否滿足計(jì)算精度的要求.是,標(biāo)志變量設(shè)為1,輸出結(jié)果；%否,標(biāo)志變量設(shè)為0,繼續(xù)迭代ifsum(abs(tidu(x).A2)<1e-4flag=1；x0=x;elseflag=0;end%

13、初始的H矩陣為單位矩陣h0=eye(2);%循環(huán)求解函數(shù)的極小點(diǎn)whileflag=0%計(jì)算新的迭代方向d=-h0*tidu(x)'a=gold(x,d);x1=(x'+a*h0*d)'s=x1-x;y=tidu(x1)-tidu(x);v=s*y'%校正H矩陣h0=(eye(2)-s'*y./v)*h0*(eye(2)-y'*s./v)+s'*s./v;%判斷下一次和上一次迭代點(diǎn)之差是否滿足計(jì)算精度的要求.是，標(biāo)志變量設(shè)為1,輸出結(jié)果；否，標(biāo)志變量設(shè)為0,繼續(xù)迭代ifsum(abs(x-x1).A2)<1e-4flag=1;x0=x;elseflag=0;endx=x1end%共腕剃度法極小化函數(shù)的通用子函數(shù)，gonge.m%輸入變量為初始的迭代點(diǎn)，輸出變量為極小值點(diǎn)functionx0=gonge(x)師U斷梯度范數(shù)是否滿足計(jì)算精度的要求.是,標(biāo)志變量設(shè)為1,輸出結(jié)果；%否,標(biāo)志變量設(shè)為0,繼續(xù)迭代ifsum(abs(tidu(x).A2)<1e-4flag=1;x0=x;elseflag=0;end%第一次的迭代方法為負(fù)梯度方向d1=-tidu(x);a=gold(x,d1);x1=x+a*d1;%循環(huán)求解函數(shù)的極小點(diǎn)whileflag=0g1=tid