最优化线性规划.pptx

文档介绍：第二章线性规划
2
§ 凸集与凸函数
3
凸 集
设集合D Rn,若对于任意点x,y∈ D,
及实数a,0≤a≤1,都有
ax+(1-a)y ∈ D,
则称集合D为凸集.
常见的凸集:单点集{x}, 空集, 整个欧式空间Rn,
超平面 H={x∈ Rn|a1x1+a2x2+…anxn=b}，
半空间 H+={x∈Rn|a1x1+a2x2+…anxn≥b}，实
心圆，实心球，实心长方体等都是凸集。
4
凸 集
从直观上看，没有凹入部分，或没有空洞
的是凸集。
几何解释为：集合D中任两点连线上的每
一点仍在D中，则D为凸集。
5
凸集的例
超球||x||≤r为凸集
证明 设x,y为超球中任意两点, 0≤a≤1,则有
||ax+(1-a)y||≤a||x||+(1-a)||y||
≤a r+(1-a) r = r,
即点ax+(1-a)y属于超球,所以超球为凸集.
6
凸集的性质
(i)有限个(可以改成无限)凸集的交集为凸集.
即:若Dj(j ∈ J)是凸集,则它们的交集
D={x|x ∈ Dj,j ∈ J }
是凸集.
(ii)设D是凸集,b是一实数,则下面集合是凸集
b D={y | y =b x, x ∈ D}.
7
凸集的性质
(iii)设D1,D2是凸集,则D1与D2的和集
D1+D2={y|y=x+z,x ∈ D1,z ∈ D2}是凸集.
注:和集与并集有很大的区别,凸集的并集未必是凸集, 而凸集的和集是凸集.
例:D1={(x,0)T|x ∈ R}表示 x 轴上的点, D2={(0,y)T|y ∈R},表示 y 轴上的点.
则D1∪D2表示两个轴的所有点,它不是凸集;
D1+D2=R2是凸集
8
推论 凸集的线性组合是凸集.
设xi∈ Rn,i=1,…,k,实数li≥0,
则 称为x1,x2, …,xk的凸组合.
容易证明:凸集中任意有限个点的凸组合仍然在该凸集中.
两点的凸组合
三点的凸组合
多点的凸组合
9
极 点
设D为凸集, x∈,z及某一实数a∈(0,1)使得x=ay+(1-a)z则称x为D的极点.
凸集
极点
凸集
极点
10
极 点
例 D={x ∈Rn| ||x||≤a}(a>0),则||x||=a上的点均为极点
证明:设||x||=a,若存在y,z ∈D及a∈(0,1),使得x=ay+(1-a)
a2=||x||2≤a2||y||2+(1-a)2||z||2+2a (1-a)||y||||z||≤a2
不等式取等号,必须||y||=||z||=a, 容易证明y=z=x,根据定义可知,x为极点.