线性规划问题基本概念和基本理论

线性规划问题基本概念和基本理论2、1数学规划模型得一般形式(续)局部最优解:x*

S,

x*得邻域N(x*),使满足f(x*)≤f(x),x

S

N(x*)。则称x*为(fS)得局部最优解,记l、opt、(localoptimum)在上述定义中,当x

x*时有严格不等式成立,则分别称x*

为(fS)得严格全局最优解和严格局部最优解。严格l、opt、严格g、opt、l、opt、2、1数学规划模型得一般形式(续)函数形式: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

当f(x),gi(x),hj(x)均为线性函数时,称线性规划;若其中有非线性函数时,称非线性规划。2、2凸集、凸函数和凸规划一、凸集1、凸集得概念:定义:设集合S

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

S,

[0,1],必有

x(1)＋(1-

)x(2)

S,则称S为凸集。规定:单点集{x}为凸集,空集

为凸集。注:

x(1)＋(1-

)x(2)=x(2)＋

(x(1)-x(2))

就是连接x(1)与x(2)得线段。凸集非凸集非凸集2、2凸集、凸函数和凸规划(续)一、凸集1、凸集得概念:例:证明集合S={x∣Ax=b}就是凸集。其中,A为m

n矩阵,b为m维向量。凸组合:设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

—构成线性组合——线性子空间

j≥0,

j>0—构成半正组合——凸锥

j≥0,

j=0—构成凸组合——凸集2、2凸集、凸函数和凸规划(续)一、凸集1、凸集得概念:定理:S就是凸集

S中任意有限点得凸组合属于S多胞形H(x(1),x(2),…,x(m)):由x(1),x(2),…,x(m)得所有凸组合构成。单纯形:若多胞形H(x(1),x(2),…,x(m))满足,

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

x(1)

线性无关。多胞形单纯形单纯形2、2凸集、凸函数和凸规划(续)一、凸集2、凸集得性质:凸集得交集就是凸集;(并？)凸集得内点集就是凸集;(逆命题就是否成立？)凸集得闭包就是凸集。(逆命题就是否成立？)分离与支撑:凸集边界上任意点存在支撑超平面两个互相不交得凸集之间存在分离超平面支撑强分离分离非正常分离2、2凸集、凸函数和凸规划(续)一、凸集3、凸锥:定义:C

Rn,若x

C,

>0有

x

C,则称C就是以0为顶点得锥。如果C还就是凸集,则称为凸锥。集合{0}、Rn就是凸锥。命题:C就是凸锥

C中任意有限点得半正组合属于S02、2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集定义:设集合S

Rn为凸集,函数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上得凸函数。若进一步有上面不等式以严格不等式成立,则称f(x)为凸集S上得严格凸函数。当-f(x)为凸函数(严格凸函数)时,则称f(x)为凹函数(严格凹函数)。严格凸函数凸函数严格凹函数2、2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集:定理:f(x)为凸集S上得凸函数

S上任意有限点得凸组合得函数值不大于各点函数值得凸组合。思考:设f1,f2就是凸函数,设

1,

2>0,

1f1+

2f2,

1f1-

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

2、2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集:定义:设集合S

Rn,函数f:S

R,

R,称S

={x

S∣f(x)≤

}为f(x)在S上得

水平集。定理:设集合S

Rn就是凸集,函数f:S

R就是凸函数,则对

R,S

就是凸集。注:水平集得概念相当于在地形图中,海拔高度不高于某一数值得区域。上述定理得逆不真。考虑分段函数f(x)=1(x≥0)或0(x<0),函数非凸,但任意水平集就是凸集。12大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流2、2凸集、凸函数和凸规划(续)二、凸函数2、凸函数得性质:方向导数:设S

Rn为非空凸集,函数f:S

R,再设x*

S,d为方向,使当

>0

充分小时有x*+

d

S,

如果lim

[f(x*+

d)-f(x*)]/

存在(包括

)

则称f(x)为在点沿方向得方向导数存在,记f`(x*;d)=lim

[f(x*+

d)-f(x*)]/

若f(x)在x*可导,则f`(x*;d)=[

f(x*)]Td、2、2凸集、凸函数和凸规划(续)二、凸函数2、凸函数得性质:以下设S

Rn为非空凸集,函数f:S

R2)若f凸,则f在S得内点集上连续;注:f在S上不一定连续。例:f(x)＝2(当

x

=1);f(x)＝x2(当

x<1)、3)设f凸,则对任意方向方向导数存在。4)设S就是开集,f在S上可微,则

f凸

x*

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

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

x

S、5)设S就是开集,f在S上二次可微,则a)

f凸

x

S,2f(x)半正定;

b)若

x

S,2f(x)正定,则f严格凸。2、2凸集、凸函数和凸规划(续)二、凸函数2、凸函数得性质:例:

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凸集、凸函数和凸规划(续)三、凸规划:当(fS)中,S为凸集,f就是S上得凸函数(求min),称(fS)为凸规划;对于(fgh),f,gi为凸函数,hj为线性函数时,(fgh)为凸规划。定理:设集合S

Rn为凸集,函数f:S

Rf(x)为凸集S上得凸函数。x*为问题(fs)得l、opt,则x*为g、opt;又如果f就是严格凸函数,那么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