最優(yōu)化方法課件01.4

§1.7

凸集與凸函數(shù)1凸集定義1.7.1

設(shè)集合D

Rn,若對(duì)于任意點(diǎn)x,y∈

D,及實(shí)數(shù)a,0≤a≤1,都有ax+(1-a)y∈

D,則稱集合D為凸集.常見(jiàn)的凸集:空集(補(bǔ)充定義),整個(gè)歐式空間Rn,超平面H={x∈

Rn|a1x1+a2x2+…anxn=b}半空間

H+={x∈Rn|a1x1+a2x2+…anxn≥b}2例3凸集的例例1.7.1

超球||x||≤r為凸集證明設(shè)x,y為超球中任意兩點(diǎn),0≤a≤1,則有||ax+(1-a)y||≤a||x||+(1-a)||y||≤a

r+(1-a)r=r,即點(diǎn)ax+(1-a)y屬于超球,所以超球?yàn)橥辜?4凸集的性質(zhì)(i)有限個(gè)(可以改成無(wú)限)凸集的交集為凸集.即:若Dj(j

∈

J)是凸集,則它們的交集D={x|x

∈

Dj,j

∈J}是凸集.(ii)設(shè)D是凸集,b是一實(shí)數(shù),則下面集合是凸集bD={y|y=bx,x∈

D}.5凸集的性質(zhì)(iii)設(shè)D1,D2是凸集,則D1與D2的和集D1+D2={y|y=x+z,x

∈

D1,z∈D2}是凸集.注:和集與并集有很大的區(qū)別,凸集的并集未必是凸集,而凸集的和集是凸集.例:D1={(x,0)T|x∈

R}表示x軸上的點(diǎn),D2={(0,y)T|y∈R},表示y軸上的點(diǎn).則D1∪D2表示兩個(gè)軸的所有點(diǎn),它不是凸集;D1+D2=R2是凸集6推論凸集的線性組合是凸集.定義1.7.2

設(shè)xi∈

Rn,i=1,…,k,實(shí)數(shù)li≥0,則稱為x1,x2,…,xk的凸組合.容易證明:凸集中任意有限個(gè)點(diǎn)的凸組合仍然在該凸集中.兩點(diǎn)的凸組合三點(diǎn)的凸組合多點(diǎn)的凸組合7極點(diǎn)定義1.7.3

設(shè)D為凸集,x∈D.若D中不存在兩個(gè)相異的點(diǎn)y,z及某一實(shí)數(shù)a∈(0,1)使得

x=ay+(1-a)z

則稱x為D的極點(diǎn).凸集極點(diǎn)凸集極點(diǎn)8極點(diǎn)例1.7.2D={x∈Rn|||x||≤a}(a>0),則||x||=a上的點(diǎn)均為極點(diǎn)證明:設(shè)||x||=a,若存在y,z

∈D及a∈(0,1),使得x=ay+(1-a)z.則a2=||x||2=（ay+(1-a)z,ay+(1-a)z）≤a2||y||2+(1-a)2||z||2+2a(1-a)||y||||z||≤a2不等式取等號(hào),必須||y||=||z||=a,且（y,z

）

=||y||||z||,

容易證明y=z=x,根據(jù)定義可知,x為極點(diǎn).9凸函數(shù)定義1.7.4

設(shè)函數(shù)f(x)定義在凸集DRn上,若對(duì)任意的x,y

∈D,及任意的a∈

[0,1]都有

f(ax+(1-a)y)≤af(x)+(1-a)f(y)

則稱函數(shù)f(x)為凸集D上的凸函數(shù).10凸函數(shù)定義1.7.5

設(shè)函數(shù)f(x)定義在凸集DRn上,若對(duì)任意的x,y∈D,x≠y,及任意的a∈(0,1)都有

f(ax+(1-a)y)<af(x)+(1-a)f(y)

則稱函數(shù)f(x)為凸集D上的嚴(yán)格凸函數(shù).將上述定義中的不等式反向,可以得到凹函數(shù)和嚴(yán)格凹函數(shù)的定義.11凸函數(shù)的例例1.7.3

設(shè)f(x)=(x–1)2,試證明f(x)在(–∞,+∞)上是嚴(yán)格凸函數(shù).證明:設(shè)x,y∈R,且x≠y,a∈(0,1)都有

f(ax+(1-a)y)-(af(x)+(1-a)f(y))

=(ax+(1-a)y-1)2-a(x-1)2-(1-a)(y-1)2=–a(1-a)(x-y)2<0因此f(x)在(–∞,+∞)上是嚴(yán)格凸函數(shù).例1.7.4

線性函數(shù)f(x)=cTx=c1x1+c2x2+···+cnxn既是Rn上凸函數(shù)也是Rn上凹函數(shù).12凸函數(shù)的幾何性質(zhì)對(duì)一元函數(shù)f(x),在幾何上af(x1)+(1-a)f(x2)

(0≤a≤1)表示連接(x1,f(x1)),(x2,f(x2))的線段,f(ax1+(1-a)x2)表示在點(diǎn)ax1+(1-a)x2處的函數(shù)值,所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點(diǎn)的線段總是位于曲線弧的上方.13對(duì)于一元凸函數(shù)f(x),可以發(fā)現(xiàn),位于函數(shù)曲線上方的圖形是凸集.事實(shí)上這一結(jié)論對(duì)于多元函數(shù)也是成立的,而且是充要條件,即有下面的定理.定理:設(shè)f(x)是定義在凸集DRn上的函數(shù),則f(x)是凸函數(shù)的充要條件是其上圖epi(f)為凸集,其中epi(f)={(x,y)|x∈

D,y

∈

R,y≥f(x)}.證明:作業(yè)14凸函數(shù)的性質(zhì)(i)設(shè)f(x)是凸集DRn上的凸函數(shù),實(shí)數(shù)k≥0,則kf(x)也是D上的凸函數(shù).(ii)設(shè)f1(x),f2(x)是凸集DRn上的凸函數(shù),實(shí)數(shù)l,m≥0,則lf1(x)+mf2(x)也是D上的凸函數(shù).(iii)設(shè)f(x)是凸集DRn上的凸函數(shù),b為實(shí)數(shù),則水平集S(f,b)={x|x∈D,f(x)≤b

}是凸集.下面的圖形給出了凸函數(shù)f(x,y)=x4+3x2+y4+y2+xy的等值線(f(x,y)=2,4,6,8,10,12)的圖形.可以看出水平集為凸集.15凸函數(shù)的性質(zhì)16凸函數(shù)的判斷定理1.7.1

設(shè)f(x)定義在凸集DRn上,x,y∈D.令F(t)=f(tx+(1-t)y),t∈[0,1],則該定理的幾何意義是:凸函數(shù)上任意兩點(diǎn)之間的部分是一段向下凸的弧線.(i)f(x)是凸集D上的凸函數(shù)的充要條件是對(duì)任意的x∈D,一元函數(shù)F(t)為[0,1]上的凸函數(shù).(ii)f(x)是凸集D上的嚴(yán)格凸函數(shù)的充要條件是對(duì)任意的x,y∈D(x≠y),一元函數(shù)F(t)為[0,1]上的嚴(yán)格凸函數(shù).17凸函數(shù)的判斷18一階條件定理1.7.2

(一階條件)設(shè)在凸集DRn上f(x)可微,則f(x)在D上為凸函數(shù)的充要條件是對(duì)任意的x,y∈D,都有f(y)≥f(x)+f(x)T(y-x)定理1.7.3(一階條件)設(shè)在凸集DRn上f(x)可微,則f(x)在D上為嚴(yán)格凸函數(shù)的充要條件是對(duì)任意的x,y∈D,x≠y,都有f(y)>f(x)+f(x)T(y-x)19二階條件定理1.7.4(二階條件)設(shè)在開(kāi)凸集DRn上f(x)可微,則(i)f(x)是D內(nèi)的凸函數(shù)的充要條件為,在D內(nèi)任一點(diǎn)x處,f(x)的Hesse矩陣G(x)半正定,其中(ii)若在D內(nèi)G(x)正定,則f(x)在D內(nèi)是嚴(yán)格凸函數(shù).20+(1-)-a)(1xfa)(2xf])1([21xxfaa-+=2221)1(xxaa-+221])1([xxaa-+-=2221)1(xxaa-+-])1(2)1([21222212xxxxaaaa-+-+=212221)1(2)1()1(xxxxaaaaaa---+-=(1-)aa)2(212221xxxx-+=(1-)aa(x1-x2)≥02∴+(1-)≥a)(1xfa)(2xf])1([21xxfaa-+所以，=

x是R上凸函數(shù)。)(xf2例如，對(duì)=x，因x1,x2∈R，∈(0,1))(xf"a"221例：判斷下列函數(shù)的凹凸性。（1）（2）解：

22凸規(guī)劃定義1.7.6

設(shè)DRn為凸集,則f(x)為D上的凸函數(shù),則稱規(guī)劃問(wèn)題

minf(x)

s.t.x∈D

為凸規(guī)劃問(wèn)題.定理1.7.5(i)f(x)是凸函數(shù)，凸規(guī)劃的任一局部極小點(diǎn)x是整體極小點(diǎn),全體極小點(diǎn)組成凸集.(ii)若f(x)是DRn上的嚴(yán)格凸函數(shù),且凸規(guī)劃問(wèn)題minf(x)s.t.x∈D的整體極小點(diǎn)存在,則整體極小點(diǎn)唯一.23定理1.7.5證明(思路)(i)x*為局部極小點(diǎn),若存在x0使得f(x0)<f(x*),

則f(tx0

+(1-t)x*)≤tf(x0)+(1-t)f(x*)

令t取一個(gè)足夠小的正數(shù),可導(dǎo)出矛盾.(ii)若存在x*,y*都是整體極小點(diǎn)(f(x*)=f(y*)),則f(tx*+(1-t)y*)<tf(x*)+(1-t)f(y*)=f(x*)矛盾.24定義1.7.7:若規(guī)劃中，和為凸函數(shù)，是線性函數(shù)，則上述問(wèn)題為凸規(guī)劃25例：線性規(guī)劃是凸規(guī)劃。例：數(shù)學(xué)規(guī)劃易知，與都是凸函數(shù)，所以該規(guī)劃是凸規(guī)劃。26

對(duì)于一般的規(guī)劃（P），其局部最優(yōu)解不一定是全局最優(yōu)解，其可行集也未必是凸集。但若（P）是凸規(guī)劃，則有下面的結(jié)論。定理1.7.6：設(shè)規(guī)劃（P）是凸規(guī)劃，則（1）（P）的可行集R為凸集；（2）（P）的最優(yōu)解集合R*是凸集；（3）（P）的任何局部最優(yōu)解都是全局最優(yōu)解。定理1.7.7：（1)凸規(guī)劃的任意局部極小點(diǎn)就是整體極小點(diǎn)，且極小點(diǎn)集合是凸集。（2）如果凸規(guī)劃的目標(biāo)函數(shù)是嚴(yán)格凸函數(shù)，又存在極小點(diǎn)，則它的極小點(diǎn)還是唯一的。27練習(xí)：1、求的梯度和Hesse矩陣。2、判斷函數(shù)的凹凸性。3、判斷下述非線性規(guī)劃是否為凸規(guī)劃？28例:證明集合是凸集。其中，A為mn矩陣，b為m維向量。證明：任取，則所以，29

§1.8極小點(diǎn)的判定條件30最優(yōu)化問(wèn)題的一般形式為:(1.1)(目標(biāo)函數(shù))(1.3)(不等式約束)(1.2)(等式約束)其中x是n維向量.在實(shí)際應(yīng)用中,可以將求最大值的目標(biāo)函數(shù)取相反數(shù)后統(tǒng)一成公式中求最小值的形式.我們總是討論P(yáng):31

函數(shù)在局部極小點(diǎn)滿足什么條件？反之滿足什么條件的是局部極小點(diǎn)？什么是整體（全局）極小點(diǎn)？那么怎樣找到全局極小點(diǎn)呢？下面我們給出各類極小點(diǎn)的定義32無(wú)約束優(yōu)化:最優(yōu)解的分類和條件給定一個(gè)函數(shù),尋找

使得

最小，即局部最優(yōu)解全局最優(yōu)解x*f(x)xlxgo

怎樣尋求局部最優(yōu)解，和全局最優(yōu)解？33鄰域的定義34整體最優(yōu)解定義1.2.3

若x*∈D,對(duì)于一切x∈D恒有f(x*)≤f(x),則稱x*為最優(yōu)化問(wèn)題(P)的整體最優(yōu)解.若x*∈D,x≠x*,恒有f(x*)<f(x),則稱x*為最優(yōu)化問(wèn)題(P)的嚴(yán)格整體最優(yōu)解.35定義1.2.4(局部最優(yōu)解)

若x*∈D,存在x*的某鄰域Ne(x*),使得對(duì)于一切x∈D∩Ne(x*),恒有f(x*)≤f(x),則稱x*為最優(yōu)化問(wèn)題(P)的局部最優(yōu)解.當(dāng)x≠x*時(shí),若上面的不等式為嚴(yán)格不等式則稱x*為問(wèn)題(P)的嚴(yán)格局部最優(yōu)解.顯然,整體最優(yōu)解一定是局部最優(yōu)解,而局部最優(yōu)解不一定是整體最優(yōu)解.x*對(duì)應(yīng)的目標(biāo)函數(shù)值f(x*)稱為最優(yōu)值，記為f

*.36１必要條件：設(shè)Ｒ是n維歐氏空間的某一區(qū)域，

為定義在Ｒ上的實(shí)值函數(shù)，是區(qū)域Ｒ的內(nèi)點(diǎn)，若在處可微，且在該點(diǎn)取得局部極小值，則必有或極值存在的條件37其中，為函數(shù)

在處的梯度，梯度的方向?yàn)?/p>

的等值面（等值線）的法線方向，沿這個(gè)方向函數(shù)值增加最快．滿足上式的點(diǎn)稱為駐點(diǎn)，在區(qū)域內(nèi)部，極值點(diǎn)必為駐點(diǎn)；但駐點(diǎn)不一定是極值點(diǎn)．

38２充分條件：設(shè)Ｒ是n維歐氏空間的某一區(qū)域，為定義在Ｒ上的實(shí)值函數(shù)，是區(qū)域Ｒ的內(nèi)點(diǎn)，

在Ｒ上二次連續(xù)可微，若則是的嚴(yán)格局部極小點(diǎn).極