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