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

1、（目標(biāo)管理）目標(biāo)函數(shù)的幾種極值求解方法10 / 10目標(biāo)函數(shù)極值求解的幾種方法題目：,取初始點(diǎn),分別用最速下降法,牛頓法,共軛梯度法編程實(shí)現(xiàn)。 壹維搜索法：迭代下降算法大均具有壹個(gè)配合點(diǎn),這就是得到點(diǎn)后需要按某種規(guī)則確定壹個(gè)方向,再從ft發(fā),沿方向于直線（或射線）上求目標(biāo)函數(shù)的極小點(diǎn),從而得到的后繼點(diǎn),重復(fù)之上做法,直至求得問題的解,這里所謂求目標(biāo)函數(shù)于直線上的極小點(diǎn),稱為壹維搜索。壹維搜索的方法很多,歸納起來大體能夠分為倆類,壹類是試探法：采用這類方法,需要按某種方式找試探點(diǎn),通過壹系列的試探點(diǎn)來確定極小點(diǎn)。另壹類是函數(shù)逼近法或插值法：這類方法是用某種較簡(jiǎn)單的曲線逼近本來的函數(shù)曲線, 通過求

2、逼近函數(shù)的極小點(diǎn)來預(yù)計(jì)目標(biāo)函數(shù)的極小點(diǎn)。本文采用的是第壹類試探法中的黃金分割法。原理書上有詳細(xì)敘述,于這里介紹壹下實(shí)現(xiàn)過程：置初始區(qū)間及精度要求L>0,計(jì)算試探點(diǎn)和,計(jì)算函數(shù)值和,計(jì)算公式是：,。令 k=1。若則停止計(jì)算。否則,當(dāng)>時(shí),轉(zhuǎn)步驟;當(dāng)時(shí),轉(zhuǎn)步驟。置,計(jì)算函數(shù)值,轉(zhuǎn)。置,計(jì)算函數(shù)值,轉(zhuǎn)。置 k=k+1 返回步驟。1. 最速下降法實(shí)現(xiàn)原理描述：于求目標(biāo)函數(shù)極小值問題時(shí),總希望從壹點(diǎn)ft發(fā),選擇壹個(gè)目標(biāo)函數(shù)值下降最快的方向,以利于盡快達(dá)到極小點(diǎn),正是基于這樣壹種愿望提ft的最速下降法,且且經(jīng)過壹系列理論推導(dǎo)研究可知,負(fù)梯度方向?yàn)樽钏傧陆捣较?。最速下降法的迭代公式?其中是從f

3、t發(fā)的搜索方向,這里取于點(diǎn)處最速下降方向,即。是從ft發(fā)沿方向進(jìn)行的壹維搜索步長(zhǎng),滿足。實(shí)現(xiàn)步驟如下：給定初點(diǎn),允許誤差,置 k=1。計(jì)算搜索方向。若,則停止計(jì)算；否則,從ft發(fā),沿方向進(jìn)行的壹維搜索,求,使。,置 k=k+1 返回步驟。2. 擬牛頓法基本思想是用不包括二階導(dǎo)數(shù)的矩陣近似牛頓法中的 Hesse 矩陣的逆矩陣,因構(gòu)造近似矩陣的方法不同,因而ft現(xiàn)了不同的擬牛頓法。牛頓法迭代公式：,是于點(diǎn)處的牛頓方向, 是從ft發(fā)沿牛頓方向進(jìn)行搜索的最優(yōu)步長(zhǎng)。用不包括二階導(dǎo)數(shù)的矩陣近似取代牛頓法中的 Hesse 矩陣的逆矩陣,需滿足擬牛頓條件。實(shí)現(xiàn)步驟：給定初點(diǎn),允許誤差。置（單位矩陣）,計(jì)算ft

4、于處的梯度,置 k=1。令。從ft發(fā)沿方向搜索,求步長(zhǎng),使它滿足,令。檢驗(yàn)是否滿足收斂標(biāo)準(zhǔn),若,則停止迭代,得到點(diǎn),否則進(jìn)行步驟。若 k=n,令,返回；否則進(jìn)行步驟。令,置 k=k+1。返回。3. 共軛梯度法若是中 k 個(gè)方向,它們倆倆關(guān)于 A 共軛,即滿足,稱這組方向?yàn)?A 的 k 個(gè)共軛方向。共軛梯度法的基本思想是把共軛性和最速下降法相結(jié)合,利用已知點(diǎn)處的梯度構(gòu)造壹組共軛方向,且沿這組方向進(jìn)行搜索,求ft目標(biāo)函數(shù)的極小點(diǎn),根據(jù)共軛方向的基本性質(zhì)這種方法具有二次終止性。實(shí)現(xiàn)步驟如下：給定初點(diǎn),允許誤差,置, k=j=1。若,則停止計(jì)算；否則,作壹維搜索,求,滿足,令。若,則進(jìn)行步驟,否則進(jìn)行

5、步驟令,其中,置 j=j+1,轉(zhuǎn)。令,置 j=1,k=k+1,轉(zhuǎn)。4. 實(shí)驗(yàn)結(jié)果最速下降法擬牛頓法共軛梯度法第壹次迭代結(jié)果1.51516312861.51516312861.51516312860.93934748540.9393474850.9393474854第二次迭代結(jié)果1.97300822752.01081080722.00000762591.05389923740.98615771081.0000419788第三次迭代結(jié)果1.98691339342.0054101622.00000381670.99836543780.98962692400.9999998271用 之 上 三 種 方

6、 法 通 過 Matlab 編 程 得 到 實(shí) 驗(yàn) 數(shù) 據(jù) 。 初 始 值 。 迭 代 精 度sum(abs(x1-x).2)<1e-4。第四次迭代結(jié)果1.99927397611.0014531964實(shí)驗(yàn)結(jié)果分析：由上表格能夠見到最速下降法需要四次迭代實(shí)現(xiàn)所要求的精度,擬牛頓法和共軛梯度法需要三次。程序：%精確壹維搜索法的子函數(shù),0.618（黃金分割）法,gold.m%輸入的變量 x 為初始迭代點(diǎn)是二維的向量,d 為初始迭代方向是二維的向量%輸ft變量是于0,10區(qū)間上使函數(shù)取得極小值點(diǎn)的步長(zhǎng)因子functionalfa=gold(x,d)a=0;b=10;tao=0.618;lanmd

7、a=a+(1-tao)*(b-a); mu=a+tao*(b-a);alfa=lanmda;%初始化f=(x(1)+alfa*d(1)-2)2+2*(x(2)+alfa*d(2)-1)2;%目標(biāo)函數(shù)m=f;alfa=mu;n=f;while1 ifm>nifabs(lanmda-b)<1e-4 alfa=mu;returnelse a=lanmda;lanmda=mu;m=n; mu=a+tao*(b-a);alfa=mu;n=(x(1)+alfa*d(1)-2)2+2*(x(2)+alfa*d(2)-1)2; endelseifabs(mu-a)<1e-4 alfa=lan

8、mda;return else b=mu;mu=lanmda;n=m;lanmda=a+(1-tao)*(b-a);alfa=lanmda; m=(x(1)+alfa*d(1)-2)2+2*(x(2)+alfa*d(2)-1)2; endend end%梯度子函數(shù),tidu.m,輸入的變量為二維的向量,返回梯度于 x 處的數(shù)值向量functiong=tidu(x)%待求解的函數(shù)f=(x(1)-2)2+2*(x(2)-1)2;%求函數(shù)的梯度表達(dá)式g=2*(x(1)-2)4*(x(2)-1); x1=x(1);x2=x(2);%最速下降法極小化函數(shù)的通用子函數(shù) zuisu.m%輸入變量為初始的迭代

9、點(diǎn),輸ft變量為極小值點(diǎn)functionx0=zuisu(x)%判斷梯度范數(shù)是否滿足計(jì)算精度 1e-4 的要求.是,標(biāo)志變量設(shè)為 1,輸ft結(jié)果;% 否 , 標(biāo) 志 變 量 設(shè) 為 0 ifsum(abs(tidu(x).2)<1e-4 flag=1;x0=x;else flag=0; end%循環(huán)求解函數(shù)的極小點(diǎn)whileflag=0d=-tidu(x);a=gold(x,d);x=x+a*d%判斷梯度范數(shù)是否滿足計(jì)算精度的要求.是,標(biāo)志變量設(shè)為 1,輸ft結(jié)果;%否,標(biāo)志變量設(shè)為 0,繼續(xù)迭代ifsum(abs(tidu(x).2)<1e-4 flag=1;x0=x;else

10、flag=0; endEnd%擬牛頓法極小化函數(shù)的通用子函數(shù),gonge.m%輸入變量為初始的迭代點(diǎn),輸ft變量為極小值點(diǎn)functionx0=ninewton(x)%判斷梯度范數(shù)是否滿足計(jì)算精度的要求.是,標(biāo)志變量設(shè)為 1,輸ft結(jié)果;%否,標(biāo)志變量設(shè)為 0,繼續(xù)迭代ifsum(abs(tidu(x).2)<1e-4 flag=1；x0=x;else flag=0; end%初始的 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)'

11、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, 輸ft結(jié)果;否,標(biāo)志變量設(shè)為 0,繼續(xù)迭代ifsum(abs(x-x1).2)<1e-4 flag=1;x0=x;else flag=0;end x=x1 end%共軛剃度法極小化函數(shù)的通用子函數(shù),gonge.m%輸入變量為初始的迭代點(diǎn),輸ft變量為極小值點(diǎn)functionx0=gonge(x)%判斷梯度范數(shù)是否滿足計(jì)算精度的要求.是,標(biāo)志變量設(shè)為 1,輸ft結(jié)果;%否,標(biāo)志變量設(shè)為 0,繼續(xù)迭代ifsum(abs(tidu(x).2)<1e-4 flag=1;x0=x;else flag=0; end%第壹次的迭代方法為負(fù)梯度方向d1=-tidu(x);a=gold(x,d1);x1=x+a*d1;%循環(huán)求解函數(shù)的極小點(diǎn)whileflag=0 g1=tidu(x);g2=tidu(x1);%利用 FR 公式求解系數(shù) bata bata=(g2*g2'