版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、 從本章起,以后兩章將討論非線性規(guī)劃問題。本章首先討論無約束最優(yōu)化問題,其一般形式為)(minxf(3.1) 其中 1:RRfn 求解無約束問題的最優(yōu)化方法可以分為兩大類:一類是根據(jù)目標(biāo)函數(shù)的梯度(即一階導(dǎo)數(shù)),有時(shí)還要根據(jù)Hesse矩陣(即二階導(dǎo)數(shù))提供的信息構(gòu)造出來的方法導(dǎo)數(shù)方法導(dǎo)數(shù)方法。本章介紹其中的最速下降法、Newton法、共軛梯度法和擬Newton法。另一類是不使用導(dǎo)數(shù),僅僅利用目標(biāo)函數(shù)值的信息構(gòu)造出來的方法直接方法直接方法。本章將介紹其中的步長(zhǎng)加速法、方法加速法和單純形替換法。兩類方法各有利弊。前者收斂速度快,但需要計(jì)算梯度,甚至需要計(jì)算Hesse矩陣;后者不涉及導(dǎo)數(shù),適應(yīng)性強(qiáng),
2、但收斂速度慢。一般的經(jīng)驗(yàn)是,在可以求得目標(biāo)函數(shù)導(dǎo)數(shù)的情況下,盡可能使用導(dǎo)數(shù)方法。3.1 直線搜索直線搜索 直線搜索(一維搜索)是指求解如下一元函數(shù)極小化問題min( ) t(3.3) 的迭代方法,其中11:RR 。在微積分中,解決問題(3.3)的范圍一般限于方程0)( t(3.4)可以直接解出的情況。而這里介紹的直線搜索對(duì) 嚴(yán)格的要求。當(dāng)然,對(duì)于可以求出導(dǎo)數(shù)的情況,相應(yīng)的求解方法一般也會(huì)簡(jiǎn)單些。不作直線搜索,理論上,分為精確的和不精確的。 精確的直線搜索方法主要分為兩類:一類為區(qū)間收縮法,另一類為函數(shù)逼近法。本節(jié)將相應(yīng)地介紹兩種常用的精確的直線搜索方法:適用于一般函數(shù)的黃金分割法和適用于一般連
3、續(xù)函數(shù)的拋物線插值法。最后還將介紹實(shí)用的不精確一維搜索技術(shù)。 精確的直線搜索算法的實(shí)現(xiàn)通常是在所謂的搜索區(qū)間上進(jìn)行的 1. 搜索區(qū)間的確定搜索區(qū)間的確定在以下討論中,總假定一元函數(shù))(t是單谷函數(shù)。11:RRL*t)(t定義定義3.1 設(shè),是 在L上的全局極小點(diǎn)。如果對(duì)于L上任意的兩點(diǎn) 1212,t ttt,當(dāng)*2tt 時(shí), )()(21tt;當(dāng)*1tt 時(shí), )()(21tt,那么稱 )(t是區(qū)間L上的單谷函數(shù)單谷函數(shù)。下圖給出了單谷函數(shù)的基本圖形。定義定義3.2 設(shè) 11:RRL,*t是)(t在L上的全局極小點(diǎn)。如果能夠找到 Ltt21,*12 , ,tt t,使得 ,21tt)(t那么閉
4、區(qū)間就稱為極小點(diǎn)的一個(gè)搜索區(qū)間搜索區(qū)間,記為 ,21tt132 , , t t t132ttt。搜索區(qū)間有時(shí)也記作,其中顯然,單谷函數(shù)的定義域區(qū)間是搜索區(qū)間。單谷函數(shù)的性質(zhì)。,ba)(t定理定理3.1 設(shè)是單谷函數(shù)極小點(diǎn)的一個(gè)搜索區(qū)間。),(ba1212,t ttt在內(nèi)任取兩點(diǎn) ,若)()(21tt,則 ,2ta)(t是極小點(diǎn)的一個(gè)搜索區(qū)間;若 )()(21tt,1bt)(t,則是極小點(diǎn)的一個(gè)搜索區(qū)間。 直線搜索算法的第一步一般得先確定)(t的一個(gè) (初始)搜索區(qū)間。根據(jù)定理3.1,可以給出確定搜索區(qū)間的如下算法。算法算法3.1(確定搜索區(qū)間)已知:目標(biāo)函數(shù))(t。0th選定初始點(diǎn)和步長(zhǎng)。)(
5、00thtt02)(22t計(jì)算,。0201tt 若,則置,01tt 0120tt 20hh2,。01,hh ,轉(zhuǎn); 否則轉(zhuǎn)。置htt02)(22t02計(jì)算,。若,則轉(zhuǎn);否則轉(zhuǎn)。,min21tta ,max21ttb ,ba置,(即為搜索區(qū)間),計(jì)算結(jié)束。上述過程開始時(shí),必須選定初試點(diǎn) 0th和步長(zhǎng) 。對(duì)于 任意給定的 )(t,一般來說, 無固定選取模式。)()(kkp txft0t但對(duì)于在下降算法模式中所引入的而言,可選取等于0(理論上)或接近0(實(shí)際計(jì)算中)。而對(duì)于 ,如果選得過小,那么需要迭代許多次才能找到一個(gè)搜索區(qū)間;如果選得太大,雖然很少幾步就可能把極小點(diǎn)包括進(jìn)來,但是這又會(huì)給下一步搜
6、索極小點(diǎn)的過程增加負(fù)擔(dān)。下面是確定 的一種比較合理而有效的方法。hh0k0 x1x第一次迭代(,即從到的迭代)時(shí), )(t的初始步長(zhǎng)可取為1,或根據(jù)問題中出現(xiàn)的數(shù)據(jù)的數(shù)量級(jí)估計(jì)選定。而以后各次迭代的初始步長(zhǎng)可按公式(3.5)計(jì)算, kkkpxxh1(3.5)其中 。這是因?yàn)閺?到 的距離 一般比從 到 的距離 小或接近,所以把按(3.5)算出的作為下一次迭代的初始步長(zhǎng)是合適的。在實(shí)際計(jì)算中,當(dāng) 較小時(shí),相應(yīng)的 可取得小些,而隨著的 增大,相應(yīng)的 可取得接近1。kx1kxkkxx1101kxkx1kkxxkk2. 直線搜索的方法直線搜索的方法(1)黃金分割法 黃金分割法屬于區(qū)間收縮法。它適用于任
7、何單谷函數(shù)求極小值問題。對(duì)函數(shù)除“單谷”外,不作其它要求,甚至可以不連續(xù)。因此這種方法的適用面相當(dāng)廣。 黃金分割法的思想是:在每次迭代中,合理地設(shè)置兩個(gè)插入點(diǎn)的位置,以使得在計(jì)算函數(shù)值次數(shù)同樣多的條件下,將區(qū)間縮小得最快。 a設(shè)區(qū)間 的長(zhǎng)為1。在距點(diǎn) 分別為 和 的地方插入 和 。為了確定 和 ,提出以下條件: 1t2t,baa 第一,希望 和 在 中的位置是對(duì)稱的。按這一條件,有1t2t,babtat21即 1. (3.6)這樣無論刪去哪一段,總保留長(zhǎng)為的區(qū)間。,2bt第二,刪掉一段,例如刪掉3t,在保留下來的區(qū)間,使得里再插入一個(gè)點(diǎn)13,tt,2ta12,t t,ba在中的位置與在中的位置
8、具有相同的比例,從而保證每次迭代都能縮小區(qū)間。按這一條件,有以同一比率abatatat221即 1或 2. (3.7)把(3.7)代入(3.6)中,得到關(guān)于的一元二次方程其合理的根是618. 0215(3.8)代回(3.6),得382. 0253 在古代,人們認(rèn)為按比率0.618分割線段是最協(xié)調(diào)的,勝似黃金,故稱黃金分割。因此,上述按比率0.618縮小搜索區(qū)間的迭代方法稱為黃金分割法黃金分割法或0.618法法。算法算法3.2 (黃金分割法)(黃金分割法)P145(2)拋物線插值法 拋物線插值法屬于函數(shù)逼近法。它適用于連續(xù)的單谷函數(shù)求極小值問題。 拋物線插值法的思想是:設(shè) 11:RR 在搜索區(qū)間
9、,321ttt上連續(xù)。記 1122( ),( )tt)(33t和。 如果321ttt(3.9) 與123(3.10)(兩等號(hào)不同時(shí)成立)同時(shí)成立,那么可以過 1122( ,),( ,)tt),(33t和 三點(diǎn)作拋物線插值,設(shè)拋物線方程為rqtpttQ2)((3.11)( )yQ t13 , t t( )yt其實(shí)是在區(qū)間上對(duì)所作的一個(gè)曲線擬合。( )yQ t4t4t記的極小點(diǎn)為,則根據(jù) 提供的信息,我們可以將搜索區(qū)間 13 , t t縮小,然后在縮小了的區(qū)間上再作拋物線插值。如此下去,最終可以求到 )(t,31tt在 中的極小點(diǎn)*t。 令( )20Q tptq(3.12)解出 pqt24(3.1
10、3)1122( ),( )Q tQ t33)(tQ根據(jù)插值條件和,列出關(guān)于 qp,r和的線性方程組211122222333ptqtrptqtrptqtr由此解出)()()()()(133221321213132ttttttttttttp,)()()()()(133221322212212312322ttttttttttttq,并代入(3.13)中,得)()()(2)()()(3212131323222122123123224ttttttttttttt(3.14)1122( ,),( ,)tt),(33t這個(gè)公式的使用條件僅僅是和 三點(diǎn)不共線??梢宰C明(習(xí)題3.5),在(3.9)和(3.10)(
11、兩等號(hào)不同時(shí)成立)同時(shí)成立的條件下,由(3.14)所確定的 4t)(tQ341ttt是的極小點(diǎn),并且。以下討論算法的終止準(zhǔn)則和縮小搜索區(qū)間的方法。按(3.14)計(jì)算出4t。由極限理論知道,如果 *2tt *4tt 42tt24與都很小,那么也必然很小,當(dāng)然也應(yīng)該很小。 計(jì)算經(jīng)驗(yàn)指出,可以采用1224(3.15) 作為終止準(zhǔn)則。4t2t4t,321ttt當(dāng)終止準(zhǔn)則滿足時(shí),取和中函數(shù)值較小的點(diǎn)提供的縮小。這個(gè)過程如下:作為極小點(diǎn);當(dāng)終止準(zhǔn)則未滿足時(shí),則需要利用信息將原來的搜索區(qū)間4t2t24tt 比較和的大小,有兩種情況:若,則轉(zhuǎn);否則,轉(zhuǎn)。243434,tt若,則置,轉(zhuǎn); 2421tt 2412
12、24,tt 若,則,轉(zhuǎn)。 置241414,tt若,則置,轉(zhuǎn); 2423tt 243224,tt 若,則,轉(zhuǎn)。置,321ttt轉(zhuǎn)向計(jì)算新的搜索區(qū)間上的插值拋物線的極小點(diǎn)算法流程圖見書上圖3-5。 包括黃金分割法和拋物線插值法在內(nèi)的許多一維問題的迭代方法全部依賴于函數(shù)單谷性的假設(shè)。但在許多問題中,這一假設(shè)不成立或難以驗(yàn)證。解決這一困難的辦法,尤其當(dāng)初始搜索區(qū)間很大的時(shí)候,是將搜索區(qū)間分成若干個(gè)較小區(qū)間,然后在每個(gè)子區(qū)間上尋求極小,最后又在所有子區(qū)間的極小中選取最小的一個(gè)作為問題的最優(yōu)解。(3)不精確一維搜索技術(shù) 精確的一維搜索過程往往需要花費(fèi)很大的計(jì)算量才有可能求到符合精度要求的最優(yōu)步長(zhǎng)因子。當(dāng)多
13、維問題的迭代點(diǎn)距極小點(diǎn)較遠(yuǎn)時(shí),顯然精確地求解一維子問題對(duì)求解多維問題本身沒有太大的意義。另外很多最優(yōu)化方法,如Newton法和擬Newton法,其收斂速度也并不依賴于精確的一維搜索過程。因此,在實(shí)際計(jì)算中,只要選取的步長(zhǎng)因子能夠保證目標(biāo)函數(shù)在每一步的迭代中都有“滿意的”下降就可以了。這樣,既會(huì)大大地節(jié)省計(jì)算量,同時(shí)還會(huì)從整體上加快計(jì)算進(jìn)程??紤]由多維問題引出的一維問題),()(minkkp txft(3.16)其中1:RRfn具有一階連續(xù)偏導(dǎo)數(shù)。 Goldstein(1965年)和Powell(1975年)給出了用來設(shè)計(jì)(3.16)不精確一維搜索過程的兩個(gè)條件: )1()()()Tkkkkkf
14、 xf xtf xp ; (3.17)1()()TTkkkkf xpf xp (3.18).ktkkkkptxx1) 10(,其中使得,而是給定的常數(shù),通常取 210。條件)表示應(yīng)使新迭代點(diǎn)1kx的函數(shù)值相對(duì)上一迭代點(diǎn) kx的函數(shù)值的下降幅度須不低于某個(gè)量,而條件)則表示目標(biāo)函數(shù) f在新迭代點(diǎn)1kx處沿 kp方向的方向?qū)?shù)應(yīng)不小于 ff在上一迭代點(diǎn) kx處沿kp方向的方向?qū)?shù)的 倍。換句話說,若 1kx滿足 條件),則認(rèn)為在點(diǎn) 1kx處已獲得“滿意的”函數(shù)值的下降。 而若1kx滿足條件),這時(shí)有兩種可能性, 要么kp已是點(diǎn) 方向1kx處的上升方向, kp1kx要么方向雖然還是點(diǎn)下降方向, 處的
15、f1kx但函數(shù)在點(diǎn) 處沿kp方向的下降率已低于 處沿kp方向的下降率f在點(diǎn)kx 倍,這時(shí)若繼續(xù)沿 kp方向作一維搜索,只會(huì)徒增計(jì)算量,而不會(huì)再獲得函數(shù)值的較大下降量,因此,一旦 1kx滿足條件)就需要確定1kp。新的搜索方向 以上分析表明,在實(shí)際計(jì)算中,選取滿足(3.17)和(3.18)的 kt作為確定1kx的步長(zhǎng)因子是合適的, 即kkkkptxx1。一般地, 越小,一維搜索越精確,但計(jì)算量也越大。 不精確的一維搜索不要求過小的而越小,條件)越容易滿足。 0.14 . 0在實(shí)際計(jì)算中,通常取或更小的值值的選取不太敏感),。(由此得出的解通常對(duì)算法算法3.3(不精確一維搜索)( )()kktf
16、xtp()0Tkkf xp已知:,且。給定1),1 ,(),21, 0( 2t(通常?。跏迹扇?或參照(3.5)給出)。步長(zhǎng)(),()kkkkff xgf x 0,0abj 計(jì)算。置。計(jì)算11111,(),()kkkkkkkxxt pff xgf x ;若(3.18)成立,則轉(zhuǎn);否則,置,min,1abat tajj,然后轉(zhuǎn); ttk,1abbt tjj若(3.17)成立,則打印,計(jì)算結(jié)束;否則,然后轉(zhuǎn)。置 算法說明:)第步中若(3.18)不成立,則表明沿kp方向有繼續(xù)前進(jìn)的必要; )第步中若(3.17)不成立,這表明當(dāng)前步長(zhǎng)過大,需縮小搜索范圍。不精確一維搜索的算法流程圖3.2 最速下
17、降法最速下降法 最速下降法是最早的求解多元函數(shù)極值的數(shù)值方法。它直觀、簡(jiǎn)單。它的缺點(diǎn)是,收斂速度較慢、實(shí)用性差。1. 基本思想基本思想1,kxxkx求解問題(3.1)。假設(shè)迭代已得到。在點(diǎn)處,取搜索方向?yàn)?)kkpf x (3.19)沿kp進(jìn)行直線搜索,由此確定1()kkkkxxtf x (3.20) 其中步長(zhǎng)因子kt滿足()min()kkkkktf xtf xf xt f x (3.21) (3.20)、(3.21)簡(jiǎn)單地合記為1(,()kkkxls xf x(3.22) 3.20)或(3.22)稱為最速下降迭代公式最速下降迭代公式,由該公式產(chǎn)生的算法稱為最速下降法最速下降法。 今后記()(
18、)kkkgg xf x 2. 算法算法算法算法3.4(最速下降法) P151將最速下降法應(yīng)用于正定二次函數(shù)1( )2TTf xx Qxb xc(3.23) 可以推出顯式迭代公式。kkx1kx設(shè)第迭代點(diǎn)為,求的表達(dá)式。由( )g xQxb(3.24)kkgQxb (3.25)1kkkkxxt g, (3.26),10Tkkgg,(直線搜索性質(zhì))得 ()0TkkkkQ xt gbg即0Tkkkkgt Qgg由此解出TkkkTkkg gtg Qg (3.27) 例例3.1 P1523. 鋸齒現(xiàn)象鋸齒現(xiàn)象 最速下降法的迭代點(diǎn)在向極小點(diǎn)靠近的過程中,走的是曲折的路線:后一次搜索方向 1kp與前一次搜索方
19、向 kp總是相互垂直的,稱它為鋸齒現(xiàn)象鋸齒現(xiàn)象。這一點(diǎn)在前面的例題中已得到驗(yàn)證。除極特殊的目標(biāo)函數(shù)(如等值面為球面的函數(shù))和極特殊的初始點(diǎn)外,這種現(xiàn)象一般都要發(fā)生。 從直觀上可以看到,在遠(yuǎn)離極小點(diǎn)的地方,每次迭代都有可能使目標(biāo)函數(shù)值有較多的下降,但在接近極小點(diǎn)的地方,由于鋸齒現(xiàn)象,每次迭代行進(jìn)的距離開始逐漸變小。因而收斂速度不快。 已有結(jié)論表明,最速下降法對(duì)于正定二次函數(shù)關(guān)于任意初始點(diǎn)都是收斂的,而且恰好是線性收斂的。3.3 Newton法法( )f xnR如果目標(biāo)函數(shù)在上具有連續(xù)的二階偏導(dǎo)數(shù),其Hesse矩陣 2( )f x正定且可以表達(dá)成顯式(今后記 2( )( )G xf x ),那么使
20、用Newton法求解(3.1)會(huì)很快地得到極小點(diǎn)。 1. 基本思想基本思想kx1kxkx( )f x考慮從到的迭代過程。在點(diǎn)處,對(duì)按Taylor級(jí)數(shù)展開到第三項(xiàng),即1( )( )()() ()()()()2TTkkkkkkf xQ xf xg xxxxxG xxx (3.29) ()kG x( )Q x因?yàn)檎?,所以是正定二次函?shù)。令( )()()()0kkkQ xG xxxg x 得()()()kkkG xxxg x (3.30) ( )Q x1kx由此解出的極小點(diǎn),記為,即11()()kkkkxxG xg x(3.31) 1kx( )f x*x是極小點(diǎn)的新的近似點(diǎn)。 (3.31)稱為New
21、ton迭代公式迭代公式,由該公式產(chǎn)生的算法稱為Newton法法。( )f x( )( )f xQ x注意到,當(dāng)目標(biāo)函數(shù)是正定二次函數(shù)(3.36)時(shí),。這說明:對(duì)于正定二次函數(shù),Newton法一次迭代就會(huì)得到最優(yōu)解。( )f xkx(3.31)有直觀的幾何解釋。函數(shù)過點(diǎn)的等值面方程為( )()kf xf x(3.32)在點(diǎn)kx處,用一個(gè)與曲面(3.32)最密切的二次曲面來代替它,這個(gè)二次曲面的方程即是( )()kQ xf x()kG x( )Q x當(dāng)正定時(shí),它是一個(gè)超橢球面,的極小點(diǎn) 1kx正是這個(gè)超橢球面的中心。我們就用 1kx( )f x*x作為極小點(diǎn) 的新的近似點(diǎn)。下圖畫出了二維情況時(shí)的幾何解釋。例例3.2 P1542. 算法算法算法算法3.5(Newton法) P1553. 修正修正Newton法法 Newton法的優(yōu)點(diǎn)是收斂速度快、程序簡(jiǎn)單。特別是前一個(gè)優(yōu)點(diǎn),在最優(yōu)化方法中
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 景區(qū)臨時(shí)工合同模板
- 農(nóng)業(yè)房屋抵押合同模板
- 北京簽供暖合同模板
- 采購(gòu)巴西糖 合同模板
- 廠地出租合同模板
- 綠化管理合同模板
- 解除一期租房合同模板
- 美容員員工合同模板
- 餐飲經(jīng)營(yíng)購(gòu)買合同模板
- 香港抵押貸款合同模板
- 青島版(五年制)五年級(jí)數(shù)學(xué)上冊(cè)教案:第八單元第四節(jié)稍復(fù)雜的分?jǐn)?shù)除法應(yīng)用題
- 六年級(jí)保護(hù)環(huán)境演講稿2篇
- 【川教版】《生命 生態(tài) 安全》五上第5課《安全標(biāo)志提醒你》課件
- 鄉(xiāng)村休閑旅游項(xiàng)目策劃書
- 小學(xué)教學(xué)設(shè)計(jì)案例分析
- 唾液腺腫瘤的外科手術(shù)治療方法
- 2023年乒乓球二級(jí)裁判考試題庫(kù)(含答案)
- 房車營(yíng)地規(guī)劃設(shè)施方案
- 胎兒四維報(bào)告
- 水泥市場(chǎng)調(diào)研報(bào)告模板
- 水泵行業(yè)分析報(bào)告
評(píng)論
0/150
提交評(píng)論