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

1、 目標(biāo)函數(shù)極值求解的幾種方法 題目：，取初始點(diǎn)，分別用最速下降法，牛頓法，共軛梯度法編程實(shí)現(xiàn)。一維搜索法：迭代下降算法大都具有一個(gè)共同點(diǎn)，這就是得到點(diǎn)后需要按某種規(guī)則確定一個(gè)方向，再?gòu)某霭l(fā)，沿方向在直線（或射線）上求目標(biāo)函數(shù)的極小點(diǎn)，從而得到的后繼點(diǎn)，重復(fù)以上做法，直至求得問(wèn)題的解，這里所謂求目標(biāo)函數(shù)在直線上的極小點(diǎn)，稱為一維搜索。一維搜索的方法很多，歸納起來(lái)大體可以分為兩類，一類是試探法：采用這類方法，需要按某種方式找試探點(diǎn)，通過(guò)一系列的試探點(diǎn)來(lái)確定極小點(diǎn)。另一類是函數(shù)逼近法或插值法：這類方法是用某種較簡(jiǎn)單的曲線逼近本來(lái)的函數(shù)曲線，通過(guò)求逼近函數(shù)的極小點(diǎn)來(lái)估計(jì)目標(biāo)函數(shù)的極小點(diǎn)。本文采用的是第

2、一類試探法中的黃金分割法。原理書(shū)上有詳細(xì)敘述，在這里介紹一下實(shí)現(xiàn)過(guò)程： 置初始區(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ù)極小值問(wèn)題時(shí),總希望從一點(diǎn)出發(fā),選擇一個(gè)目標(biāo)函數(shù)值下降最快的方向,以利于盡快達(dá)到極小點(diǎn),正是基于這樣一種愿望提出的最速下降法,并且經(jīng)過(guò)一系列理論推導(dǎo)研究可知,負(fù)梯度方向?yàn)樽钏傧陆捣较?。最速下降法的迭代公式是，其中是從出發(fā)的搜索方向，這里取在點(diǎn)處最速下降方向，即。是從

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

4、，使它滿足，令。 檢驗(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)锳的k個(gè)共軛方向。共軛梯度法的基本思想是把共軛性與最速下降法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行搜索，求出目標(biāo)函數(shù)的極小點(diǎn)，根據(jù)共軛方向的基本性質(zhì)這種方法具有二次終止性。實(shí)現(xiàn)步驟如下： 給定初點(diǎn) ，允許誤差，置 ，k=j=1。 若，則停止計(jì)算；否則，作一維搜索，求，滿足 ，令。 若，則進(jìn)行步驟，否則進(jìn)行步驟 令，其中，置j=j+1，轉(zhuǎn)。 令，置j=1，k=k+

5、1，轉(zhuǎn) 。4. 實(shí)驗(yàn)結(jié)果 用以上三種方法通過(guò)Matlab編程得到實(shí)驗(yàn)數(shù)據(jù)。初始值 。迭代精度sum(abs(x1-x).2)<1e-4。最速下降法擬牛頓法共軛梯度法第一次迭代結(jié)果1.51516312861.51516312861.51516312860.93934748540.9393474850.9393474854第二次迭代結(jié)果1.97300822752.01081080722.00000762591.05389923740.98615771081.0000419788第三次迭代結(jié)果1.98691339342.0054101622.00000381670.99836543780.98

6、962692400.9999998271第四次迭代結(jié)果1.99927397611.0014531964實(shí)驗(yàn)結(jié)果分析：由上表格可以看到最速下降法需要四次迭代實(shí)現(xiàn)所要求的精度，擬牛頓法和共軛梯度法需要三次。程序：%精確一維搜索法的子函數(shù),0.618（黃金分割）法,gold.m%輸入的變量x為初始迭代點(diǎn)是二維的向量,d為初始迭代方向是二維的向量%輸出變量是在0,10區(qū)間上使函數(shù)取得極小值點(diǎn)的步長(zhǎng)因子function alfa=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

7、)+alfa*d(1)-2)2+2*(x(2)+alfa*d(2)-1)2;%目標(biāo)函數(shù)m=f;alfa=mu;n=f;while 1 if m>n if abs(lanmda-b)<1e-4 alfa=mu; return else 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; end else if abs(mu-a)<1e-4 alfa=lanmda; return else b=mu; mu=lanmda; n=m; lanm

8、da=a+(1-tao)*(b-a); alfa=lanmda; m=(x(1)+alfa*d(1)-2)2+2*(x(2)+alfa*d(2)-1)2; end endend%梯度子函數(shù)，tidu.m,輸入的變量為二維的向量，返回梯度在x處的數(shù)值向量function g=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%輸入變量為初始的迭代點(diǎn)，輸出變量為極小值點(diǎn)function x0=zuisu(x)%判斷

9、梯度范數(shù)是否滿足計(jì)算精度1e-4的要求.是,標(biāo)志變量設(shè)為1，輸出結(jié)果; %否,標(biāo)志變量設(shè)為0if sum(abs(tidu(x).2)<1e-4 flag=1; x0=x;else flag=0;end%循環(huán)求解函數(shù)的極小點(diǎn)while flag=0 d=-tidu(x); a=gold(x,d); x=x+a*d %判斷梯度范數(shù)是否滿足計(jì)算精度的要求.是,標(biāo)志變量設(shè)為1，輸出結(jié)果; %否,標(biāo)志變量設(shè)為0，繼續(xù)迭代 if sum(abs(tidu(x).2)<1e-4 flag=1; x0=x; else flag=0; endEnd%擬牛頓法極小化函數(shù)的通用子函數(shù)，gonge.m%

10、輸入變量為初始的迭代點(diǎn)，輸出變量為極小值點(diǎn)function x0=ninewton(x)%判斷梯度范數(shù)是否滿足計(jì)算精度的要求.是,標(biāo)志變量設(shè)為1，輸出結(jié)果;%否,標(biāo)志變量設(shè)為0，繼續(xù)迭代if sum(abs(tidu(x).2)<1e-4 flag=1； x0=x;else flag=0;end%初始的H矩陣為單位矩陣h0=eye(2);%循環(huán)求解函數(shù)的極小點(diǎn)while flag=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'

11、; %校正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ù)迭代 if sum(abs(x-x1).2)<1e-4 flag=1; x0=x; else flag=0; end x=x1end %共軛剃度法極小化函數(shù)的通用子函數(shù)，gonge.m%輸入變量為初始的迭代點(diǎn)，輸出變量為極小值點(diǎn)function x0=gonge(x)%判斷梯度范數(shù)是否滿足計(jì)算精度的要求.是,標(biāo)志變量設(shè)為1，輸出結(jié)果;%否,標(biāo)志變量設(shè)為0，繼續(xù)迭代if sum(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)while flag=0 g1=tidu(x); g2=tidu(x1); %利用FR公式求解系數(shù)bata bata=(g2*g2