【正文】 ?????????????????????????????212121 0,21113,21xxxxxxxf( 0 ) 24x???????? ( 0 )0126g Gx b???? ? ?????(1) 0126d ??? ?????17500000 ??? GdddgTT?( 1 ) ( 0 )0026173817x x d???????? ? ???????116171217g Gx b??????? ? ??????? ?g(2) 289100110 ?? ggggTT???????????????????289210289900011 dgd ?171011111 ??? GdddgTT? ( 2 ) ( 1 )1111x x d???? ? ?????02 ?g * ( 2 ) 11xx ???? ????例 5： 用 FR共軛梯度法求解： ? ? ? ? ? ?2 2 ( 0 )1 2 011mi n 1 , 1 1 , 022 TTf x x x x d? ? ? ? ?解： 化成 ? ? cxbGxxxf TT ??? 21形式 ? ? ? ? ?????????????????2121 1001,21xxxxxf(0 ) 11x??????? (0 )011g Gx b??? ? ?????(1) ???????? ??010d100000 ??? GdddgTT? ( 1 ) ( 0 ) 0001x x d???? ? ?????( 1 )101g Gx b??? ? ?????11 ?g(2) 2100110 ?? ggggTT? ??????????????1210011 dgd ?5411111 ??? GdddgTT? ( 2 ) ( 1 )112515x x d????????? ? ???????( 2 )22515g Gx b???????? ? ???????2 1 / 5g ?(3)2211115TTgggg? ??2 2 1 131025d g d???????? ? ? ????????2222225TTgdd Gd? ? ? ?( 3 ) ( 2 )22125125x x d????????? ? ???????( 3 )3125125g Gx b???????? ? ???????32 ,25g ?注意： FR方法中初始搜索方向必須取最速下降方向，才滿足二次終止性。 。 第一次迭代： ? ?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)讀者自己寫(xiě)出算法和程序 二分法 若 ? ?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。 （１）最后的兩個(gè)試點(diǎn)的選取方式： ? ? ? ?abxxabx ????? ,2/ 121例 （ Fibonacci法） 用 Fibonacci法求函數(shù) ? ? 22 ??? xxxf 在區(qū)間 ? ?3,1? 上的極小點(diǎn)。 按什么方式取點(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)度。 如果知道兩個(gè)試點(diǎn) ,21 xx ? 根據(jù) ? ? ? ?21 , xfxf的大 小關(guān)系， 可以得到縮小的區(qū)間 ? ?2,xa或者 ? ?.,1 bx 它與 ：搜索區(qū)間長(zhǎng) 度的縮短率不是采用 ，而是采用 Fibonacci數(shù)。 要求最終區(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ū)間縮小的盡量小。 在 ? ?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。 ? 計(jì)算步驟：見(jiàn) P96 ? 計(jì)算框圖 :見(jiàn) P97 0?0 0 0( ) ( )h? ? ? ???黃金分割法（ ） ? 基本思想： 它通過(guò)對(duì)試探點(diǎn)的函數(shù)值進(jìn)行比較，使得包含極小點(diǎn)的區(qū)間不斷縮短，當(dāng)區(qū)間長(zhǎng)度小到精度范圍之內(nèi)時(shí)，可以粗略地認(rèn)為區(qū)間上各點(diǎn)的函數(shù)值均接近于極小值。這樣便得到一個(gè)搜索區(qū)間。 具體地說(shuō)，就是給出初始點(diǎn) ， 初始步長(zhǎng) ，若 ，則下一步從新點(diǎn) 出發(fā)，加大步長(zhǎng)，再向前搜索，直到 目標(biāo)函數(shù)上升為止。 搜索區(qū)間： **0: , [ 0 , ) , ) m in ( )RR ?? ? ? ? ? ??? ? ? ? ?設(shè) 并 且 (*[ , ] [ 0 , ) , [ , ] [ , ]a b a b a b?? ? ? ?若 存 在 使 ， 則 稱0m in? ???是 （ ） 的 搜 索 區(qū) 間 。221 2 1 21212123 ( , ) ( 1 ) ( 2) . . 2 0 0 0 1 0KTf x x x xs t x xxxxx? ? ? ?? ? ???? ? ? ?例 ： 用 條 件 求 下 列 問(wèn) 題min 一維最優(yōu)化方法（線性搜索方法） 已知 ,kx并且求出了 kx處的可行下降方向 ,kp從 kx出發(fā)， 沿方向 kp求目標(biāo)函數(shù)的最優(yōu)解， 或者選取 ? ? ? ???? ?? 00 m inm in ?? ?? kk pxf0?k? 使得： ? ? 0Tk k k kf x p p?? ? ?問(wèn)題描述 ( ) 0k??? ?即 設(shè)其最優(yōu)解為 k?（叫精確步長(zhǎng)因子）， kkkk pxx ???? 1所以線性搜索是求解一元函數(shù) ? ???的最優(yōu)化問(wèn) 題（也叫一維最優(yōu)化問(wèn)題）。記則 稱 * * ****( ) ( ) ( ) = ( ) ( ) ( )( , , ) 0( ) 0 ,0,i i j ji I j JTTxiiix g x h xf x g x h xL agran ge L agran geLxK T g x i IiI????????????????? ???? ? ????????是 非 線 性 規(guī) 劃 問(wèn) 題 的 函 數(shù) ， 其 中 和 叫 乘 子 。 若是 問(wèn) 題 （ *) 的 局 部 最 優(yōu) 解 ， 則 存 在和 使 得? ? *( \ )ig x i I I? 在（ KT條件） 一階必要條件 定理 1‘: (KuhnTucker一階必要條件 ) ? ?** 0iigx? ? Ii?? ? ? ? ? ?? ?** * * *** * *, ( ) ( )( ) ( ) , ( )0( ) ( ) ,ijijijf x g x i I x h x j Jx g x i I h x j Jxi I j J????? ? ? ?? ? ?設(shè) 在 點(diǎn) 處 可 微 , 在點(diǎn) 處 連 續(xù) 可 微 , 且線 性 無(wú) 關(guān) 。 ( ) 0 , 1 , 2 , ,1 , 2 , , , 1 , 2 , , ijnijfxs t g x i ph x j qD x R g x i p h x j qJ q I p????? ? ? ? ? ???一 般 約 束 問(wèn) 題 的 最 優(yōu) 性（ *