基本概念.PPT

1、1第一章第一章 基本概念基本概念Basic conceptions最優(yōu)化問題簡(jiǎn)介最優(yōu)化問題簡(jiǎn)介凸集和凸函數(shù)凸集和凸函數(shù)非線性規(guī)劃方法概述非線性規(guī)劃方法概述2345678922212121231( )20,( )10,22( )0(,)22Tc xxxcxxxc xxxx 例設(shè)。 令，求點(diǎn) 的積極約束指標(biāo)集.解：解：2122( )2()0,22c x 22222( )1 ()()0,22cx 1032( )02c x .1,2xA.1x2xO1( )0c x 2( )0c x 3( )0c x x111213二二 . 凸集和凸函數(shù)凸集和凸函數(shù)141516 凸集：設(shè)集合凸集：設(shè)集合nRX ，如果X

2、中任意兩點(diǎn)的凸組合仍然屬于X，則稱X為凸集.17181920212223242526272829303132(1)凸函數(shù)：凸函數(shù)：1:,01nDRfDR 設(shè)是非空凸集，若對(duì)（ ， ）有定義定義DDff則稱 是上的凸函數(shù)，或 在上是凸的.DDff則稱 是上的嚴(yán)格凸函數(shù)，或 在上是嚴(yán)格凸的.D()D(),D()fff若是上的 嚴(yán)格 凸函數(shù)，稱 是上的 嚴(yán)格凹函數(shù) 或 在上是 嚴(yán)格 凹的.2 凸函數(shù)和凸規(guī)劃凸函數(shù)和凸規(guī)劃121212(1)()(1) (),fxxf xf xx xD121212(1)()(1) (),fxxf xf xx xD若33即是凸的也是凹的。即是凸的也是凹的。其中其中例例1,

3、)( RRxxxfnT 是凸函數(shù)是凸函數(shù)其中其中例例nRxxxf |)( 例：正定二次函數(shù)例：正定二次函數(shù),21)(cxbAxxxfTT 其中其中A是正定矩陣，是正定矩陣，f(x)是凸函數(shù)是凸函數(shù).34nDR設(shè)是非空凸集性質(zhì)性質(zhì)1:(1)D0Dff若 是 上的凸函數(shù)，則是 上的凸函數(shù)；1212(2),D,Dffff若是上的凸函數(shù)是上的凸函數(shù).（2）凸函數(shù)的性質(zhì)）凸函數(shù)的性質(zhì)性質(zhì)性質(zhì)2:1,nDRfcR設(shè)是非空凸集是凸函數(shù)則集合 cxfSxcfHS )(|),(是凸集是凸集.證明證明:略略.351D,nRfDR設(shè)是非空開凸集， ：可微 則1Df（） 是上的凸函數(shù)1212112() ()()(),

4、Tf xxxf xf xx xD11111()()(),Tnf xf xf xxxx其中（）是函數(shù)在點(diǎn) 處的梯度.定理定理1：（一階條件）：（一階條件）2Df（ ） 是上的嚴(yán)格凸函數(shù)121211212() ()()(), ,Tf xxxf xf xx xD xxn=1時(shí)幾何意義：可微函數(shù)是凸的等價(jià)于切線不在函數(shù)圖像時(shí)幾何意義：可微函數(shù)是凸的等價(jià)于切線不在函數(shù)圖像上方上方. （3） 凸函數(shù)的判定凸函數(shù)的判定36122D, :, ( )D( ),nRfDRfDf xf xDfD設(shè)是非空開凸集二階連續(xù)可導(dǎo)則 是上的凸函數(shù)在 上是半正定的.當(dāng)在 上是正定矩陣時(shí)是 上的嚴(yán)格凸函數(shù)（此時(shí) 逆命題不成立）

5、nnnnxxxfxxxfxxxfxxxfxfxf)(.)(.)(.)()(Hesse)(2121211222矩陣，矩陣，為為其中其中定理定理2：（二階條件）：（二階條件）37 , 1 0 , 1 0 . miniqjxh pixgtsxfj）（）（）（4）凸規(guī)劃的定義及其性質(zhì)：）凸規(guī)劃的定義及其性質(zhì)： , 1 0 , 1 0 qjxhpixgRxXjin）（）（,(MP),XfD若 是凸集是 上的凸函數(shù) 稱為非線性凸規(guī)劃 簡(jiǎn)稱凸規(guī)劃.凸規(guī)劃定義：凸規(guī)劃定義：38定理定理是凸規(guī)劃。是凸規(guī)劃。上的凸函數(shù)，則上的凸函數(shù)，則是是并且并且皆為線性函數(shù)，皆為線性函數(shù)，上的凸函數(shù)上的凸函數(shù)皆為皆為若若）（）

6、（）（對(duì)于非線性規(guī)劃對(duì)于非線性規(guī)劃)( MP)(,)(g , 1 0 , 1 0 s.t. min,(MP) iXfxhRxqjxh pixgxfjnij 凸規(guī)劃性質(zhì)：凸規(guī)劃性質(zhì)：定理定理凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解凸規(guī)劃的任一局部最優(yōu)解都是它的整體最優(yōu)解.凸規(guī)劃是以后重點(diǎn)討論的一類非線性規(guī)劃凸規(guī)劃是以后重點(diǎn)討論的一類非線性規(guī)劃凸函數(shù)凸函數(shù)線性函數(shù)線性函數(shù)39（1）微分學(xué)方法的局限性：）微分學(xué)方法的局限性：實(shí)際的問題中，函數(shù)可能是不連續(xù)或者不可微的.需要解復(fù)雜的方程組，而方程組到目前仍沒有有效的算法.實(shí)際的問題可能含有不等式約束，微分學(xué)方法不易處理.3 3 非線性規(guī)劃方法概述非線性規(guī)劃方法概述40（2）數(shù)值方法的基本思路：迭代給定初始點(diǎn)x0根據(jù)x0,依次迭代產(chǎn)生點(diǎn)列xkxk的最后一點(diǎn)為最優(yōu)解xk有限xk無限xk收斂于最優(yōu)解41迭代格式迭代格式xkxk+1kx kkkxxx 1p