最優(yōu)化方法第一次B

1、八八. 凸集與凸函數(shù)凸集與凸函數(shù)1.凸集凸集（1）凸組合：已知凸組合：已知 ，nRX 任取k個點 ， Xxi 如果存在常數(shù)0 ia，),2,1(ki 11 kiia，使得 xxakiii1，則稱 x為ix),2,1(ki 的凸組合。的凸組合。（2）凸集：設集合）凸集：設集合nRX ，如果X中任意兩點的凸組合仍然屬于X，則稱X為凸集。2.凸函數(shù)凸函數(shù)設設RRXfn :，任取任取Xxx 21,，如果如果1,0,2121 iiaaa，有有)()()(22112211xfaxfaxaxaf ，則稱則稱f為為X上的（嚴格）上的（嚴格）凸函數(shù)。凸函數(shù)。例子：例子： 2)(xxf 5. 凸規(guī)劃凸規(guī)劃（1）D

2、xtsxf .)(min其中其中)(xf是凸函數(shù)，是凸函數(shù)，D是凸集。是凸集。（2）)(minxf 0)(0)(0)(0)(.11xhxhxgxgtskl其中其中)(, )(xgxfi是凸函數(shù)，是凸函數(shù)，)(xhj是線性函數(shù)。是線性函數(shù)。水平集水平集： fXxxfxD,)(| 是凸函數(shù)是凸函數(shù)。性質(zhì)：水平集一定是凸集。性質(zhì)：水平集一定是凸集。3. 凸函數(shù)的性質(zhì)凸函數(shù)的性質(zhì)定理定理. 凸函數(shù)的局部極小點就是全局極小點。凸函數(shù)的局部極小點就是全局極小點。4. 凸函數(shù)的判斷條件凸函數(shù)的判斷條件定理定理1. )(xf是凸集是凸集X上的凸函數(shù)的充要條件是上的凸函數(shù)的充要條件是Xxx 21,，有，有)()

3、()()(12112xxxfxfxfT .定理定理2.設設)(xf在凸集在凸集X上有二階連續(xù)偏導數(shù)，則上有二階連續(xù)偏導數(shù)，則)(xf是凸是凸函數(shù)的充要條件是函數(shù)的充要條件是Xx ，有，有)(2xf 半正定。半正定。例：正定二次函數(shù)例：正定二次函數(shù)cxbAxxxfTT 21)(，其中，其中A是正定矩陣。是正定矩陣。十十. 算法及相關概念算法及相關概念1.一般迭代算法一般迭代算法集合集合S上的迭代算法上的迭代算法A：（1）初始點）初始點0 x；（2）按照某種規(guī)則）按照某種規(guī)則A產(chǎn)生下一個迭代點產(chǎn)生下一個迭代點)(1kkxAx 。（i）如果點列）如果點列kx收斂于最優(yōu)解收斂于最優(yōu)解*x，則稱算法，則

4、稱算法A收斂。收斂。（ii）如果）如果 )()()(10kxfxfxf，則稱算法，則稱算法A為為下降迭代算法。下降迭代算法。.0 x.1x.2x九九. 極小點的判定條件極小點的判定條件（1）必要條件：）必要條件：0)()(min)(xfxfxf（2）充分條件：）充分條件：0)(0)(2 xfxf)(min)(xfxf2.下降迭代算法步驟下降迭代算法步驟（1）給出初始點）給出初始點0 x，令，令0 k；（2）按照某種規(guī)則確定下降搜索方向）按照某種規(guī)則確定下降搜索方向kd；（3）按照某種規(guī)則確定搜索步長）按照某種規(guī)則確定搜索步長k ，使得，使得)()(kkkkxfdxf ；（4）令）令kkkkdxx 1，1: kk；（5）判斷）判斷kx是否滿足停止條件。是則停止，否則轉第是否滿足停止條件。是則停止，否則轉第2步。步。搜索步長確定方法：搜索步長確定方法：)(min)(kkkkkdxfdxf 稱稱0)( kTkkkddxf 。k 為最優(yōu)步長，且有為最優(yōu)步長，且有十一十一. 終止條件終止條件)(31kkkkxxxx)(41kkkkxfxfxfxf1111)()()(kkkkkkxfxfxfxxx22)(kkxxf1111)()(kkkkxfxfxx2.4.1.11kkxx21)()(kkxfxf3.5.最可靠法則最可靠法則