【文章內(nèi)容簡(jiǎn)介】 ????????????????????????nnnnxxxfxxxfxxxfxxxfxfxf)(...)(......)(...)()(Hesse)(2121211222矩陣，為其中定理 2：（二階條件） ????????? ,1 0 ,1 0 .. miniqjxh pixgtsxfj ??）（）（）（?（ 4）凸規(guī)劃的定義及其性質(zhì)： ???????????? ,1 0 ,1 0 qjxhpixgRxXjin??）（）（簡(jiǎn)稱凸規(guī)劃。凸規(guī)劃為非線性稱上的凸函數(shù)是是凸集若,MP, )(SfX凸規(guī)劃定義： 定理 是凸規(guī)劃。上的凸函數(shù)，則是并且皆為線性函數(shù)，上的凸函數(shù)皆為若）（）（）（對(duì)于非線性規(guī)劃)( MP)(,)(g ,1 0 ,1 0 . min,(MP) iXfxhRxqjxh pixgxfjnij???????????凸規(guī)劃性質(zhì)： 定理凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。 ?凸規(guī)劃是以后重點(diǎn)討論的一類非線性規(guī)劃 凸函數(shù) 線性函數(shù) ?（ 1）微分學(xué)方法的局限性： ?實(shí)際的問題中，函數(shù)可能是不連續(xù)或者不可微的。 ?需要解復(fù)雜的方程組，而方程組到目前仍沒有有效的算法。 ?實(shí)際的問題可能含有不等式約束，微分學(xué)方法不易處理。 6 非線性規(guī)劃方法概述 ?（ 2）數(shù)值方法的基本思路： 迭代 給定初始點(diǎn) x0 根據(jù) x0,依次迭代產(chǎn)生點(diǎn)列 {xk} {xk}的最后一點(diǎn)為最優(yōu)解 {xk}有限 {xk}無限 {xk}收斂于最優(yōu)解 ?迭代格式 xk xk+1 kx? kkk xx ???? 1pk kkk ptx ?? kkk x ??? 1稱 pk為第 k輪 搜索方向 ， tk為第 k輪沿 pk方向的 步長(zhǎng) 。 產(chǎn)生 tk和 pk的不同方法，形成了不同的算法。 ，使若存在設(shè) 0,0,: 1 ????? ?pRpRxRRf nnn ),0( ),()( ????? txftpxf 處的下降方向。在點(diǎn)是函數(shù)則稱向量xxfp )(處下降最快的方向。在就是可導(dǎo)，則在若xxfxfxxf)()()( ?定義 ：特殊搜索方向 —— 下降方向 ，使得若存在設(shè) 0t,0, ????? pRpXxRX nnXtpx ?? 的可行方向。關(guān)于處是點(diǎn)則稱向量Xxp定義： 特殊搜索方向 —— 可行 下降方向 解非線性規(guī)劃問題，關(guān)鍵在于找到某個(gè)方向，使得在此方向上，目標(biāo)函數(shù)得到下降，同時(shí)還是可行方向。 這樣的方向稱為 可行下降方向。 定義：算法收斂、下降迭代算法 集合 S上的迭代算法： （ 1）初始點(diǎn) 0x； （ 2）按照某種搜索方向 pk產(chǎn)生下一個(gè)迭代點(diǎn) .1 kkkk pxx ????（ i）如果點(diǎn)列 }{ kx收斂于最優(yōu)解 *，則稱此 算法收斂 。 （ ii）如果 ?? ???? )()()( 10 kxfxfxf，則稱此算法為 下降迭代算法 。 . 0x. 1. 2x ?（ 3）下降迭代算法步驟 （ 1）給出初始點(diǎn) 0x，令 0?k； （ 2）按照某種規(guī)則確定下降搜索方向 kd； （ 3）按照某種規(guī)則確定搜索步長(zhǎng) k?，使得 )()( kkkk xfdxf ?? ?； （ 4）令 kkkk dx ???? 1， 1: ?? k； （ 5）判斷 kx是否滿足 停止條件 。是則停止，否則轉(zhuǎn)第 2步。 搜索步長(zhǎng)確定方法： )(min)( kkkkk dxfdxf ?? ? ???稱 0)( ??? kTkkk ddxf ?k?為 最優(yōu)步長(zhǎng) ，且有對(duì) ?k的梯度 ?（ 4） 終止條件 )(31?? ???? kkkkxxxx ? ? ? ?? ? ? ? )(41?? ???? kkkkxfxfxfxf② ④ ① 11 ???? kk xx21 )()( ???? kk xfxf③ （ 5）常用的收斂性判別準(zhǔn)則 : （１）點(diǎn)收斂準(zhǔn)則 : ( 可取 Rn中任一種模 )。 ? ? ? ? ) 1 ( ) ( k k x x ? （２）目標(biāo)函數(shù)值準(zhǔn)則： （絕對(duì)差）。 ? ? ? ? ) ( ) ( ) 1 ( ) ( k k f f x x （３）目標(biāo)函數(shù)值準(zhǔn)則： （相對(duì)差）。 ? ? ? ? ) ( ) ( ) ( ) ( ) 1 ( ) ( k k k f f f x x x 取其中之一 ,也可同時(shí)取 (1)與 (2)。(1)與 (3)?；?(1),(2)和 (3)等。 ?（ 6）算法的收斂速度 則稱 的收斂階為 。 設(shè)算法所得的點(diǎn)列為 }{ kx，如果 ,|||| |||| **1?? ?? ??xxxxkk.0, ???? }{ kx（當(dāng) k充分大時(shí)）： ： ： （ *）式中 ? =2時(shí)成立。 1|||| |||| *)(*)1(????xxxxkk0|||| ||||lim *)(*)1(?????? xxxxkkk（ *） 單變量 (一維 )最優(yōu)化 ? 一維最優(yōu)化問題 ? 進(jìn)退法 ? 黃金分割法 ? 拋物線搜索法 ? 三次插值法 下降迭代算法 中最優(yōu)步長(zhǎng)的確定 )(min)( kkkkk dxfdxf ?? ? ???. kx kd. k?一維最優(yōu)化問題： )(min xf Rxts ?..解析的方法 （ 極值點(diǎn)的必要條件） 0)(39。 ?xf一、一維最優(yōu)化問題 1. 單峰函數(shù) 定義 ：設(shè) )(xf是區(qū)間 ],[ ba上的一元函數(shù)， x是 )(xf在 ],[ ba上的極小點(diǎn)，且對(duì)任意的 ,],[, 2121 xxbax ??有 （ a）當(dāng) xx ?2時(shí)， 。)()( 21 xfx ?（ b）當(dāng) 時(shí)，x?1 .f ?a. . b. x. . 12則稱 是單峰函數(shù)。 )(xf. . 性質(zhì) ：通過計(jì)算區(qū)間 [a, b] 內(nèi)兩個(gè)不同點(diǎn)的函數(shù)值，就可以確定一個(gè)包含極小點(diǎn)的子區(qū)間。 定理 設(shè) 是區(qū)間 ],ba上的一元函數(shù)， x是 )(xf在 ],[ ba上的極小點(diǎn)。任取點(diǎn) )(xf ,],[ badc ??則有 （ 1）如果 )()( dfcf ?，則 。],[ bc?（ 2）如果 ,)() df?則 。], daa. . b. x. . cd 2 搜索法求解： )(min 0 xx ?? )(minmax0xxx ???或 基本過程： ?給出 [a,b],使得 x*在 [a,b]中。 [a,b]稱為 搜索區(qū)間 。 ?迭代縮短 [a,b]的長(zhǎng)度。 ?當(dāng) [a,b]的長(zhǎng)度小于某個(gè)預(yù)設(shè)的值，或者導(dǎo)數(shù)的絕對(duì)值小于某個(gè)預(yù)設(shè)的正數(shù)，則迭代終止。 二．進(jìn)退法 思想 從一點(diǎn)出發(fā) ,按一定的步長(zhǎng) , 試圖確定出函數(shù)值呈現(xiàn)“高 低 高” 的三點(diǎn)。一個(gè)方向不成功，就退回來，再沿相反方向?qū)ふ摇? 進(jìn)退法的計(jì)算步驟 ,.1 )0( Rx ?給定初始點(diǎn) ,00 ?h初始步長(zhǎng) ,0hh ?令 ,)0()1( xx ),( )1(xf計(jì)算 .0?k并令 ,.2 )1()4( hxx ??令 ),( )4(xf計(jì)算 .1: ?? kk令 ),()(.3 )1()4( xfxf ?若，則轉(zhuǎn) 4 ，轉(zhuǎn) ,.4 )1()2( xx ?令 ,)4()1( xx ? ),()( )1()2 xfxf ? ),()( )4()1( xfxf .2,2: 轉(zhuǎn)令 hh ?如何確定包含極小點(diǎn)的一個(gè)區(qū)間？ , k若 ；則轉(zhuǎn) 6 .7否則，轉(zhuǎn) ,:.6 hh ??令 ,)4()2( xx ? ),()( )4()2( xfxf ?.2轉(zhuǎn) ,.7 )2((3) xx ?令 )1 ,)()1(x停止計(jì)算。例： )0(x1 hxx ?? )1()4()2( )1(x )4(321 )0(x1)4x hh ??:)( 2)4(x )3(21。即為包含極小點(diǎn)的區(qū)間或區(qū)間 ],[],[ )1()3()3()1( xxxx ],[ )1()3( xx：極小點(diǎn)區(qū)間 ],[ )3()1(x極小點(diǎn)區(qū)間： 假定：已經(jīng)確定了單峰區(qū)間 [a,b] )(min 0 xx ?? )(minmax0xxx ??? )(min