【文章內容簡介】 xxfxf Tn?????? ?定理 1：（一階條件） ?上的嚴格凸函數是）（ S2 f 212112121 , ),()()()( xxSxxxfxfxxxf T ???????n=1時幾何意義：可微函數是凸的等價于切線不在函數圖像上方。 ? （ 3） 凸函數的判定 逆命題不成立）上的嚴格凸函數（此時是上是正定矩陣時在當上是半正定的。在上的凸函數是則二階連續(xù)可導是非空開凸集設,)(S)( ,:,S221SfSxfxfSfRSfRn???????????????????????????????????nnnnxxxfxxxfxxxfxxxfxfxf)(...)(......)(...)()(Hesse)(2121211222矩陣，為其中定理 2：（二階條件） ????????? ,1 0 ,1 0 .. miniqjxh pixgtsxfj ??）（）（）（?（ 4）凸規(guī)劃的定義及其性質： ???????????? ,1 0 ,1 0 qjxhpixgRxXjin??）（）（簡稱凸規(guī)劃。凸規(guī)劃為非線性稱上的凸函數是是凸集若,MP, )(SfX凸規(guī)劃定義： 定理 是凸規(guī)劃。上的凸函數，則是并且皆為線性函數，上的凸函數皆為若）（）（）（對于非線性規(guī)劃)( MP)(,)(g ,1 0 ,1 0 . min,(MP) iXfxhRxqjxh pixgxfjnij???????????凸規(guī)劃性質： 定理凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解。 ?凸規(guī)劃是以后重點討論的一類非線性規(guī)劃 凸函數 線性函數 ?（ 1）微分學方法的局限性： ?實際的問題中，函數可能是不連續(xù)或者不可微的。 ?需要解復雜的方程組，而方程組到目前仍沒有有效的算法。 ?實際的問題可能含有不等式約束，微分學方法不易處理。 6 非線性規(guī)劃方法概述 ?（ 2）數值方法的基本思路： 迭代 給定初始點 x0 根據 x0,依次迭代產生點列 {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方向的 步長 。 產生 tk和 pk的不同方法，形成了不同的算法。 ，使若存在設 0,0,: 1 ????? ?pRpRxRRf nnn ),0( ),()( ????? txftpxf 處的下降方向。在點是函數則稱向量xxfp )(處下降最快的方向。在就是可導，則在若xxfxfxxf)()()( ?定義 ：特殊搜索方向 —— 下降方向 ，使得若存在設 0t,0, ????? pRpXxRX nnXtpx ?? 的可行方向。關于處是點則稱向量Xxp定義： 特殊搜索方向 —— 可行 下降方向 解非線性規(guī)劃問題，關鍵在于找到某個方向，使得在此方向上，目標函數得到下降，同時還是可行方向。 這樣的方向稱為 可行下降方向。 定義：算法收斂、下降迭代算法 集合 S上的迭代算法： （ 1）初始點 0x； （ 2）按照某種搜索方向 pk產生下一個迭代點 .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 ? （２）目標函數值準則： （絕對差）。 ? ? ? ? ) ( ) ( ) 1 ( ) ( k k f f x x （３）目標函數值準則： （相對差）。 ? ? ? ? ) ( ) ( ) ( ) ( ) 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. 單峰函數 定義 ：設 )(xf是區(qū)間 ],[ ba上的一元函數， x是 )(xf在 ],[ ba上的極小點，且對任意的 ,],[, 2121 xxbax ??有 （ a）當 xx ?2時， 。)()( 21 xfx ?（ b）當 時，x?1 .f ?a. . b. x. . 12則稱 是單峰函數。 )(xf. . 性質 ：通過計算區(qū)間 [a, b] 內兩個不同點的函數值，就可以確定一個包含極小點的子區(qū)間。 定理 設 是區(qū)間 ],ba上的一元函數， x是 )(xf在 ],[ ba上的極小點。任取點 )(xf ,],[ badc ??則有 （ 1）如果 )()( dfcf ?，則 。],[ bc?（ 2）如果 ,)() df?則 。], daa. . b. x. . cd2 搜索法求解： )(min 0 xx ?? )(minmax0xxx ???或 基本過程： ?給出 [a,b],使得 x*在 [a,b]中。 [a,b]稱為 搜索區(qū)間 。 ?迭代縮短 [a,b]的長度。 ?當 [a,b]的長度小于某個預設的值，或者導數的絕對值小于某個預設的正數，則迭代終止。 二．進退法 思想 從一點出發(fā) ,按一定的