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