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

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

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

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

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

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

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

7、;=minf（y（j）+九d（j»,令y（j*）=y（j）+九jd（j）。0若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.實驗結(jié)果用以上三種方法通過Matlab編程得到實驗數(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實驗結(jié)果分析：由上表格可以看到最速下降法需要四次迭代實現(xiàn)所要求的精度，擬牛頓法和共腕梯度法需要三次

9、。程序：%精確一維搜索法的子函數(shù)，0.618(黃金分割)法，gold.m%俞入的變量x為初始迭代點是二維的向量，d為初始迭代方向是二維的向量%俞出變量是在0,10區(qū)間上使函數(shù)取得極小值點的步長因子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;%目標函數(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ù)的梯度表達式g=2*(x(1)-2)4*(x(2)-1);x1=x(1);x2=x(2);%!速下降法極小化函數(shù)的通用子函數(shù)zuisu.m%俞入變量為初始的迭代點，輸出變量為極小值點functionx0=zuisu(x)%斷梯度范數(shù)是否滿足計算精度1e-4的要求.是,標志變量設(shè)為1,輸出結(jié)果;%5,標志變量設(shè)為0ifsum(abs(tidu(x).A2)<1e-4flag=1;x0=x;elseflag=0;end%循環(huán)求解函數(shù)的極小點whileflag=0d=-tidu(x)

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

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