【文章內(nèi)容簡(jiǎn)介】 ?黃金分割法（ ） ? 基本思想： 它通過(guò)對(duì)試探點(diǎn)的函數(shù)值進(jìn)行比較，使得包含極小點(diǎn)的區(qū)間不斷縮短，當(dāng)區(qū)間長(zhǎng)度小到精度范圍之內(nèi)時(shí)，可以粗略地認(rèn)為區(qū)間上各點(diǎn)的函數(shù)值均接近于極小值。 設(shè) ? ?xf在 ? ?ba,上為下單峰函數(shù)， 即有唯一 的極小點(diǎn) ,*x 在 *x 左邊 ? ?xf 嚴(yán)格下降， 在 *x 右邊 ? ?xf 嚴(yán)格上升。 在 ? ?ba,內(nèi)任取 ,21 xx ?若 ? ? ? ?,21 xfxf ? 則 ? ?2* , xax ?若 ? ? ? ?,21 xfxf ? 則 ? ?bxx ,1* ?單峰函數(shù)： 黃金分割法 黃金分割法 若第一次選取的試點(diǎn)為 ,21 xx ? 則下一步保留 的區(qū)間為 ? ?2,xa 或 ? ?,1 bx 兩者的機(jī)會(huì)是均等的． 因此我們選取試點(diǎn)時(shí)希望 .12 xbax ???設(shè) ? ?,1 abpax ??? 則 ? ?? ? .12 abpax ????另外，我們希望如果縮小的區(qū)間包含原來(lái)的 試點(diǎn)，則該試點(diǎn)在下一步被利用．若保留的區(qū) 我們希望原來(lái)的 間為 ? ?, 2xa 前一次的試點(diǎn) 1x在這個(gè)區(qū)間內(nèi)． 1x在縮小的區(qū)間內(nèi)成為 新的 .2x 我們根據(jù)這條件 來(lái)計(jì)算 .p計(jì)算 2x的公式為： ? ?? ?abpax ???? 12因此我們希望： ? ? ? ?221 , ,x a p b a a a b x? ? ? ? ? ?? ? ? ? ? ?即： ? ? ? ? ? ?? ?? ?aabpapaabpa ????????? 1139。21 xx ?化簡(jiǎn)得： 530132 ???????? pppp若保留區(qū)間為 ? ?,1 bx我們得到的結(jié)果是 一致的． 該方法稱為黃金分割法，實(shí)際計(jì)算?。? ? ? ? ?abaxabax ?????? 21所以黃金分割法又稱為 ． 黃金分割法每次縮小區(qū)間的比例是一致的， 每次將區(qū)間長(zhǎng)度縮小到原來(lái)的 ． 黃金分割法的算法步驟 Step1 給定 ? ?baba ?, 以及 0??令 ? ? ? ?1 1 82 , ,x a b a f f x? ? ? ?Step2 Step3 轉(zhuǎn) Step２ . 令 ? ? ? ?2 2 18 , ,x a b a f f x? ? ? ?轉(zhuǎn) Step３ . 若 ,??? ab則 ,2* bax ??停； 否則 轉(zhuǎn) Step４ . Step4 若 ,21 ff ? 則 ,12122 ffxxxb ???? ? ? ?1 1 82 , ,x a b a f f x? ? ? ?轉(zhuǎn) Step3. 黃金分割法的算法步驟 Step5 若 ,21 ff ?則 , 21 xbxa ??? ? ? ?1 1 82 , ,x a b a f f x? ? ? ?? ? ? ?2 2 18 , ,x a b a f f x? ? ? ?轉(zhuǎn) Step3. 若 ,21 ff ? 則 , 21211 ffxxxa ???? ? ? ?2 2 18 , ,x a b a f f x? ? ? ?轉(zhuǎn) Step3. 例 1（黃金分割法） 用黃金分割法求函數(shù) ? ? 22 ??? xxxf 在區(qū)間 ? ?3,1? 上的極小點(diǎn)。 要求最終區(qū)間長(zhǎng)度不大于 原始區(qū)間長(zhǎng)度的 ． 解： 函數(shù) ? ?xf 在區(qū)間 ? ?3,1? 上為下單峰函數(shù)， ? ? ?????第一次迭代： ? ?3,1 ??? ba ? ?1 82 28x a b a? ? ? ? ?f? ?2 18 72x a b a? ? ? ? ?f,21 ff ? 縮短后區(qū)間為 ? ?,1?第二次迭代： ? ?,1 ??? ba ?? xx ?? ff ?f,21 ff ? 縮短后區(qū)間為 ? ?,?? ?1 82 56x a b a? ? ? ? ?迭代 次數(shù) ０ 否 １ 否 ２ 否 ３ 否 ４ 否 ５ 否 ６ 是 ? ?ba,1x 2x1f 2f ??? ab? ?3,1?? ?,1?? ?,?? ?,?? ?,? ?,? ?,? ? 5 5 * ???xFibonacci法 為了盡快得到結(jié)果，希望區(qū)間縮小的盡量小。 如果在區(qū)間只有一個(gè)試點(diǎn)，我們無(wú)法將區(qū)間縮小。 如果知道兩個(gè)試點(diǎn) ,21 xx ? 根據(jù) ? ? ? ?21 , xfxf的大 小關(guān)系， 可以得到縮小的區(qū)間 ? ?2,xa或者 ? ?.,1 bx 它與 ：搜索區(qū)間長(zhǎng) 度的縮短率不是采用 ，而是采用 Fibonacci數(shù)。 下面我們考慮任給一個(gè) 另外一種思維方式為， ? ?xf 的單峰區(qū)間 ? ?,ab如果給定試點(diǎn)的個(gè)數(shù) ,n 如何使最后確定 最優(yōu)值的區(qū)間盡量的小。 按什么方式取點(diǎn)， 求 n 次函數(shù)值之后， 可最多將多長(zhǎng)的原始區(qū)間 長(zhǎng)度縮小為 .1 設(shè) nL為試點(diǎn)個(gè)數(shù)為 、n 最終區(qū)間 長(zhǎng)度為 1 時(shí)、 原始區(qū)間 ? ?ba,的最大可能長(zhǎng)度。 的包含 設(shè)最初兩個(gè)試點(diǎn)為 1x 和 ,2x 若極小點(diǎn)在 ? ?1,xa 內(nèi)， 至多還有 2?n 個(gè)試點(diǎn)， 則 ,21 ??? nLax若極小點(diǎn)在 ? ?bx ,1內(nèi)， 包括 2x 在內(nèi)可以有 1?n 個(gè)試點(diǎn)， 則 ,11 ??? nLxb因此， ,21 ?? ?? nnn LLL如果我們采取合適的技巧，可以使得： ,21 ?? ?? nnn LLL 另外， 顯然， .110 ?? LL從而 nL滿足差分方程： ? ????????? ??121021LLnLLL nnn此為 Fibonacci數(shù)列，一般寫為： ? ????????? ??121021FFnFFF nnn若原始區(qū)間為 ? ?,ba要求最終區(qū)間長(zhǎng)度 ,??則 ,? abF n ??由此可確定 ,n 區(qū)間縮短之后與 之前的比依次為： 21,32,53,121 ????nnnnFFFFn 確定之后，最初兩個(gè)試點(diǎn)分別為： ? ? ? ?abFFaxabFFaxnnnn ?????? ?? 122121 ,xx 關(guān)于 ? ?ba, 對(duì)稱 1 112()n n n nFb a b aF ??? ? ? 112 1123()nnFFF baF F F?? ? ?111 ()nbaF??由于 上述過(guò)程完成了依次迭代，新區(qū)間仍記為 1?i? ?ba,若已經(jīng)進(jìn)行了 次迭代， 第 i 次迭代時(shí)， 還有 1??in 個(gè)試點(diǎn)（包括已經(jīng)計(jì)算過(guò)的函數(shù)值的一個(gè)） ? ? ? ?abFFaxabFFaxinininin ?????????????12111注意 ： （２）若在一定的誤差范圍內(nèi)， ? ? ? ?,21 xfxf ?則認(rèn)為 *x 在 ? ?21, xx內(nèi)。 （１）最后的兩個(gè)試點(diǎn)的選取方式： ? ? ? ?abxxabx ????? ,2/ 121例 （ Fibonacci法） 用 Fibonacci法求函數(shù) ? ? 22 ??? xxxf 在區(qū)間 ? ?3,1? 上的極小點(diǎn)。 要求最終區(qū)間長(zhǎng)度不大于 原始區(qū)間長(zhǎng)度的 ． 解： 函數(shù) ? ?xf在區(qū)間 ? ?3,1?上為下單峰函數(shù)， ? ? ?????由 ,??nF可知 n 應(yīng)?。? ? ?.136 ?FFibonacci算法與 。 第一次迭代： ? ?3,1 ??? ba? ?abFFax ???64141351 ?????? ? 4 1381652 ???????? abFFax, 21 ?? ff,21 ff ?縮短后區(qū)間為 ? ?,1?第二次迭代 ： ? ?,1 ??? ba ?x ?f? ? 0 531 ?????? FFx ?f,21 ff ? 縮短后區(qū)間為 ? ?,?第三次迭代： ? ?, ??? ba ?x ?f? ? 432 ????? FFx ?f,21 ff ? 縮短后區(qū)間為 ? ?,?第四次迭代： ? ?84 ,07 ??? ba ?x ?f? ? 311 ????? FFx ?f,21 ff ? 縮短后區(qū)間為 ? ?,第五次迭代： ? ?, ?? ba ?x ?f? ? ????? xx 1 ?f,21 ff ? 取最優(yōu)解 5 21* ??? xxxFibonacci方法評(píng)價(jià) Fibonacci法的優(yōu)點(diǎn) （１）如果縮小的區(qū)間包含原來(lái)的試點(diǎn)，則該 試點(diǎn)在下一步被利用； （２）效率最高，有限個(gè)試點(diǎn)的情況下，可將 最優(yōu)點(diǎn)所在的區(qū)間縮小到最?。? Fibonacci法的缺點(diǎn) （１）搜索前先要計(jì)算搜索的步數(shù)； （２）每次搜索試點(diǎn)計(jì)算的公式不一致． 黃金分割法（ ）與 Fibonacci法 的區(qū)別與聯(lián)系是什么？ 請(qǐng)讀者自己寫出算法和程序 二分法 若 ? ?xf的導(dǎo)數(shù)存在且容易計(jì)算， 則線性搜索 的速度可以得到提高． 下面的二分法每次將 區(qū)間縮小至原來(lái)的二分之一． 設(shè) ? ?xf為下單峰函數(shù)， 若 ? ?xf 在 ? ?ba,內(nèi) 具有連續(xù)的一階導(dǎo)數(shù)， 且 ? ? ? ?0,0 ???? bfaf取 ? ? ,2/bac ?? 若 ? ? ,0?? cf 則 c 為極小點(diǎn)； 若 ? ?,0?? cf 則以 ? ?ca, 代替 ? ?,ab；若 ? ?,0?? cf 則以 ? ?cb, 代替 ? ?,ab。 二分法每次迭代都將區(qū)間縮短一半，故二分法的收斂速度也是線性的，收斂比為 1/2。 。 ? 計(jì)算步驟：見(jiàn) P105 ? 計(jì)算框圖 :見(jiàn) P106 多維無(wú)約束最優(yōu)化方法 ? 最速下降法 ? (阻尼 )牛頓法 ? 共軛梯度法 最速下降法 問(wèn)題提出 問(wèn)題： 在點(diǎn) ()kx 處， 沿什么方向 ,kd ? ?xf下降最快 ? 分析： ? ? ? ? ? ? ? ?( ) ( ) 0kk Tk k k kf x d f x g d o d? ? ? ?? ? ? ? ?考查： ?c oskkkTk dgdg ?顯然當(dāng) 1c os ??? 時(shí)， kTkdg取極小值． 因此： kk gd ??結(jié)論： 負(fù)梯度方向使 ? ?xf下降最快， 亦即最速 下降方向． 最速下降法算法 Step1: 給出 ( 0 ) , 0 1 , : 0nx R k?? ? ? ? ?Step2: 計(jì)算 ? ?() ,kfx?如果 ? ?() ,kfx ???停． Step3: 計(jì)算下降方向 .kk gd ??Step4: 計(jì)算步長(zhǎng)因子 ( ) ( )0( ) m i n ( )kkk k kf x d f x d??? ?? ? ?Step5: 令 ( 1 ) ( ) ,kk kkx x d?? ??轉(zhuǎn)步２ . ,k? 使 得問(wèn)題： 設(shè) ? ? cxbGxxxf TT ??? 21是正定二次函數(shù) , 由精確的線搜索確定的 ??k?特別當(dāng)： Tkkk Tkkgdd G d? ??則kk gd ??kTkkTkk Ggggg??? ?( ) ( )( ) 0kk TTk k k kd f x d d G x d b dd ??? ? ? ? ? ?() g ,kk Gx b??又例 1： 用最速下降法求解： ? ? ? ?2 2 ( 0 )1219m i n 9 , 122 Tf x x x x? ? ?解： ? ? ? ? ? ? TxxGxxxg 0,090019*21 ???????????????????? ? ? ? ? ?( 0 ) 009 , 1 9 , 9TTx g f x? ? ? ?( 1 ) ( 0 ) 00000TTggx x gg G g