资源描述：
《第二章 线性规划--最优化方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最优化方法目录第一章最优化问题概述第二章线性规划第三章无约束最优化方法第四章约束最优化方法2第二章线性规划§2.1凸集与凸函数4凸集定义2.1.1设集合DRn,若对于任意点x,y∈D,及实数a,0≤a≤1,都有ax+(1-a)y∈D,则称集合D为凸集.常见的凸集:空集(补充定义),整个欧式空间Rn,超平面H={x∈Rn
2、a1x1+a2x2+…anxn=b}半空间H+={x∈Rn
3、a1x1+a2x2+…anxn≥b}5凸集的例例2.1.2超球
4、
5、x
6、
7、≤r为凸集证明设x,y为超球中任意两点,0≤a≤1,则有
8、
9、ax+(1-a)y
10、
11、≤a
12、
13、x
14、
15、+(1-
16、a)
17、
18、y
19、
20、≤ar+(1-a)r=r,即点ax+(1-a)y属于超球,所以超球为凸集.6凸集的性质(i)有限个(可以改成无限)凸集的交集为凸集.即:若Dj(j∈J)是凸集,则它们的交集D={x
21、x∈Dj,j∈J}是凸集.(ii)设D是凸集,b是一实数,则下面集合是凸集bD={y
22、y=bx,x∈D}.7凸集的性质(iii)设D1,D2是凸集,则D1与D2的和集D1+D2={y
23、y=x+z,x∈D1,z∈D2}是凸集.注:和集与并集有很大的区别,凸集的并集未必是凸集,而凸集的和集是凸集.例:D1={(x,0)T
24、x∈R}表示x轴上的点,D2={(0,y)
25、T
26、y∈R},表示y轴上的点.则D1∪D2表示两个轴的所有点,它不是凸集;D1+D2=R2是凸集8推论凸集的线性组合是凸集.定义2.1.2设xi∈Rn,i=1,…,k,实数li≥0,则称为x1,x2,…,xk的凸组合.容易证明:凸集中任意有限个点的凸组合仍然在该凸集中.两点的凸组合三点的凸组合多点的凸组合9极点定义2.1.3设D为凸集,x∈D.若D中不存在两个相异的点y,z及某一实数a∈(0,1)使得x=ay+(1-a)z则称x为D的极点.凸集极点凸集极点10极点例D={x∈Rn
27、
28、
29、x
30、
31、≤a}(a>0),则
32、
33、x
34、
35、=a上的点均为极点证明:设
36、
37、x
38、
39、
40、=a,若存在y,z∈D及a∈(0,1),使得x=ay+(1-a)z.则a2=
41、
42、x
43、
44、2=＜ay+(1-a)z,ay+(1-a)z＞≤a2
45、
46、y
47、
48、2+(1-a)2
49、
50、z
51、
52、2+2a(1-a)
53、
54、y
55、
56、
57、
58、z
59、
60、≤a2不等式取等号,必须
61、
62、y
63、
64、=
65、
66、z
67、
68、=a,且＜y,z＞=
69、
70、y
71、
72、
73、
74、z
75、
76、,容易证明y=z=x,根据定义可知,x为极点.11凸函数定义2.1.4设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,及任意的a∈[0,1]都有f(ax+(1-a)y)≤af(x)+(1-a)f(y)则称函数f(x)为凸集D上的凸函数.12凸函数定
77、义2.1.5设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,x≠y,及任意的a∈(0,1)都有f(ax+(1-a)y)78、y)2<0因此f(x)在(–∞,+∞)上是严格凸函数.例2.1.4线性函数f(x)=cTx=c1x1+c2x2+···+cnxn既是Rn上凸函数也是Rn上凹函数.14凸函数的几何性质对一元函数f(x),在几何上af(x1)+(1-a)f(x2) (0≤a≤1)表示连接(x1,f(x1)),(x2,f(x2))的线段,f(ax1+(1-a)x2)表示在点ax1+(1-a)x2处的函数值,所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.15凸函数的几何性质16上图对于一元凸函数f(x),可以发现,位于函数曲线上方的图形是凸集.事实上这一
79、结论对于多元函数也是成立的,而且是充要条件,即有下面的定理.定理:设f(x)是定义在凸集DRn上的函数,则f(x)是凸函数的充要条件是其上图epi(f)为凸集,其中epi(f)={(x,y)
80、x∈D,y∈R,y≥f(x)}.证明:作业17凸函数的性质(i)设f(x)是凸集DRn上的凸函数,实数k≥0,则kf(x)也是D上的凸函数.(ii)设f1(x),f2(x)是凸集DRn上的凸函数,实数l,m≥0,则lf1(x)+mf2(x)也是D上的凸函数.(iii)设f(x)是凸集DRn上的凸函数,b为实数,则水平集S(f,b)={x
81、x∈D,f(x)≤b}是凸
82、集.下面的图形给出了凸函数f(x,y)=x4+3x2+y4+y2+xy的等值线(f(x,y)=
