線性規(guī)劃問題基本概念和基本理論2、1數(shù)學(xué)規(guī)劃模型得一般形式(續(xù))局部最優(yōu)解:x*

S,

x*得鄰域N(x*),使?jié)M足f(x*)≤f(x),x

S

N(x*)。則稱x*為(fS)得局部最優(yōu)解,記l、opt、(localoptimum)在上述定義中,當(dāng)x

x*時有嚴格不等式成立,則分別稱x*

為(fS)得嚴格全局最優(yōu)解和嚴格局部最優(yōu)解。嚴格l、opt、嚴格g、opt、l、opt、2、1數(shù)學(xué)規(guī)劃模型得一般形式(續(xù))函數(shù)形式:f(x),gi(x),hj(x):RnRminf(x)(fgh)s、t、gi(x)

≤0,i=1,2,…,m

hj(x)=0,j=1,2,…,l矩陣形式:minf(x),f(x)

:Rn

R(fgh)s、t、g(x)

≤0,g(x):Rn

Rm

h(x)=0,h(x):Rn

Rl

當(dāng)f(x),gi(x),hj(x)均為線性函數(shù)時,稱線性規(guī)劃;若其中有非線性函數(shù)時,稱非線性規(guī)劃。2、2凸集、凸函數(shù)和凸規(guī)劃一、凸集1、凸集得概念:定義:設(shè)集合S

Rn,若x(1),x(2)

S,

[0,1],必有

x(1)＋(1-

)x(2)

S,則稱S為凸集。規(guī)定:單點集{x}為凸集,空集

為凸集。注:

x(1)＋(1-

)x(2)=x(2)＋

(x(1)-x(2))

就是連接x(1)與x(2)得線段。凸集非凸集非凸集2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集得概念:例:證明集合S={x∣Ax=b}就是凸集。其中,A為m

n矩陣,b為m維向量。凸組合:設(shè)x(1),x(2),…,x(m)

Rn,

j≥

0

mm

j=1,那么稱

jx(j)為x(1),x(2),…,x(m)得

j=1j=1凸組合。m比較:z=

jx(j)

j=1

j

R

—構(gòu)成線性組合——線性子空間

j≥0,

j>0—構(gòu)成半正組合——凸錐

j≥0,

j=0—構(gòu)成凸組合——凸集2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集1、凸集得概念:定理:S就是凸集

S中任意有限點得凸組合屬于S多胞形H(x(1),x(2),…,x(m)):由x(1),x(2),…,x(m)得所有凸組合構(gòu)成。單純形:若多胞形H(x(1),x(2),…,x(m))滿足,

x(2)-x(1),x(3)-x(1),…,x(m)-

x(1)

線性無關(guān)。多胞形單純形單純形2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集2、凸集得性質(zhì):凸集得交集就是凸集;(并？)凸集得內(nèi)點集就是凸集;(逆命題就是否成立？)凸集得閉包就是凸集。(逆命題就是否成立？)分離與支撐:凸集邊界上任意點存在支撐超平面兩個互相不交得凸集之間存在分離超平面支撐強分離分離非正常分離2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))一、凸集3、凸錐:定義:C

Rn,若x

C,

>0有

x

C,則稱C就是以0為頂點得錐。如果C還就是凸集,則稱為凸錐。集合{0}、Rn就是凸錐。命題:C就是凸錐

C中任意有限點得半正組合屬于S02、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集定義:設(shè)集合S

Rn為凸集,函數(shù)f:S

R

若x(1),x(2)

S,

(0,1),均有

f(

x(1)＋(1-

)x(2))≤f(x(1))+(1-

)f(x(2)),則稱f(x)為凸集S上得凸函數(shù)。若進一步有上面不等式以嚴格不等式成立,則稱f(x)為凸集S上得嚴格凸函數(shù)。當(dāng)-f(x)為凸函數(shù)(嚴格凸函數(shù))時,則稱f(x)為凹函數(shù)(嚴格凹函數(shù))。嚴格凸函數(shù)凸函數(shù)嚴格凹函數(shù)2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集:定理:f(x)為凸集S上得凸函數(shù)

S上任意有限點得凸組合得函數(shù)值不大于各點函數(shù)值得凸組合。思考:設(shè)f1,f2就是凸函數(shù),設(shè)

1,

2>0,

1f1+

2f2,

1f1-

2f2就是否凸函數(shù)？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}就是否凸函數(shù)？

2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)1、凸函數(shù)及水平集:定義:設(shè)集合S

Rn,函數(shù)f:S

R,

R,稱S

={x

S∣f(x)≤

}為f(x)在S上得

水平集。定理:設(shè)集合S

Rn就是凸集,函數(shù)f:S

R就是凸函數(shù),則對

R,S

就是凸集。注:水平集得概念相當(dāng)于在地形圖中,海拔高度不高于某一數(shù)值得區(qū)域。上述定理得逆不真。考慮分段函數(shù)f(x)=1(x≥0)或0(x<0),函數(shù)非凸,但任意水平集就是凸集。12大家應(yīng)該也有點累了，稍作休息大家有疑問的，可以詢問和交流2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)得性質(zhì):方向?qū)?shù):設(shè)S

Rn為非空凸集,函數(shù)f:S

R,再設(shè)x*

S,d為方向,使當(dāng)

>0

充分小時有x*+

d

S,

如果lim

[f(x*+

d)-f(x*)]/

存在(包括

)

則稱f(x)為在點沿方向得方向?qū)?shù)存在,記f`(x*;d)=lim

[f(x*+

d)-f(x*)]/

若f(x)在x*可導(dǎo),則f`(x*;d)=[

f(x*)]Td、2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)得性質(zhì):以下設(shè)S

Rn為非空凸集,函數(shù)f:S

R2)若f凸,則f在S得內(nèi)點集上連續(xù);注:f在S上不一定連續(xù)。例:f(x)＝2(當(dāng)

x

=1);f(x)＝x2(當(dāng)

x<1)、3)設(shè)f凸,則對任意方向方向?qū)?shù)存在。4)設(shè)S就是開集,f在S上可微,則

f凸

x*

S,有f(x)≥f(x*)+

fT(x*)(x-x*),

x

S、5)設(shè)S就是開集,f在S上二次可微,則a)

f凸

x

S,2f(x)半正定;

b)若

x

S,2f(x)正定,則f嚴格凸。2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))二、凸函數(shù)2、凸函數(shù)得性質(zhì):例:

f(x)＝x12+2x1x2+2x22+10x1-4;

f(x)＝-3x12+x1x2-x22-2x32-2x2x3+26;

f(x)＝3x12+ax1x2+2x22-4x1+6(a=5,4、5);2、2凸集、凸函數(shù)和凸規(guī)劃(續(xù))三、凸規(guī)劃:當(dāng)(fS)中,S為凸集,f就是S上得凸函數(shù)(求min),稱(fS)為凸規(guī)劃;對于(fgh),f,gi為凸函數(shù),hj為線性函數(shù)時,(fgh)為凸規(guī)劃。定理:設(shè)集合S

Rn為凸集,函數(shù)f:S

Rf(x)為凸集S上得凸函數(shù)。x*為問題(fs)得l、opt,則x*為g、opt;又如果f就是嚴格凸函數(shù),那么x*就是(fs)得唯一g、opt。2、3多面體、極點、極方向1)多面體:有限個半閉空間得交例:S={x

Rn

Ax=b,x≥0}2、3多面體、極點、極方向2)多面體得極點(頂點):

x

S,不存在S中得另外兩個點x(1)和x(2),及λ(0,1),使x=λx(1)+(1-λ)x(2)、3)方向:x

S,d

Rn,d

0及λ>0,總有x+λd

S、

d(1)=λd(2)(λ>0)時,稱d(1)和d(2)同方向。4)極方向:方向d不能表示為兩個不同方向得組合(d=d(1)+d(2))、2