西安电子科技大学：《工程优化方法》课程教学资源（PPT课件讲稿）第3讲 凸集、凸函数、凸规划

第3讲 凸集、凸函数、 凸规划 凸性(Convexity)是最优化理论必须涉及到基本概念.具有凸性 的非线性规划模型是一类特殊的重要模型，它在最优化的理 论证明及算法研究中具有非常重要的作用. 凸集(Convex Set) 凸函数(Convex Function) 凸规划(Convex Programming)

第3讲 凸集、凸函数、凸规划 • 凸集 (Convex Set) • 凸函数 (Convex Function) • 凸规划 (Convex Programming) 凸性(Convexity)是最优化理论必须涉及到基本概念.具有凸性 的非线性规划模型是一类特殊的重要模型，它在最优化的理 论证明及算法研究中具有非常重要的作用

凸集定义 线性组合linear Combination ∑x,其中儿，∈R,x,∈R”,i=1,2,…m. i=1 仿射组合(Affine Combination) 2x其申cRxER',i=12m且23，=1 i=1 凸组合(Convex Combination) 之x,其中，eR*,y,eR",i=1,2m且∑=1. i=1 凸锥组合(Convex Cone Combination) ∑，其中2eR*,x,eR”,i=1,2m

凸集---定义 , , , 1,2,... , 1. 1 1   = =   = = m i i n i i m i i xi 其 中 R x R i m 且  , , , 1,2,... . 1 x R x R i m n i i m i i i   = + =  其 中 线性组合 (linear Combination) , , , 1,2,... . 1 x R x R i m n i i m i  i i   = =  其 中 仿射组合 (Affine Combination) , , , 1,2,... 1. m i 1 i 1  = + =  x 其 中  R x  R i = m且  = n i i m i i i 凸组合 (Convex Combination) 凸锥组合 (Convex Cone Combination)

凸集-定义 例二维情况下，两点xx2的 (a)线性组合为全平面 (b)仿射组合为过这两点的直线： (c)凸组合为连接这两点的线段 (b)凸锥组合为以原点为锥顶并通过这两点的锥

凸集---定义 例 二维情况下，两点x1 , x2 的 (a)线性组合为全平面； (b)仿射组合为过这两点的直线； (c)凸组合为连接这两点的线段； (b)凸锥组合为以原点为锥顶并通过这两点的锥

凸集--定义 XI 2 X2 (c)凸组合为线段 (a)线性组合为全平面 (b)仿射組合为直线 (严格凸组合不含端点) (d)凸锥组合 A严格凸集 B凸集但不严格 C非凸集

凸集---定义

凸集-定义 定义1i 设集合DcR”,若对于任意两点 x,y∈D,及实数az(0≤a≤1)，都有： ax+1-a)y∈D, 则称集合D为凸集 常见的凸集：单点集{x},空集☑，整个欧氏空间R”, 超平面H={x∈R”l4x1+ax2++anxn=b以 半空间： H*={x∈R"lax+ax2++anxn≥b} -xER"a"x=b

凸集---定义 定义1 设集合 , n D  R 若对于任意两点 x , y D, 及实数  (0   1), 都有： x + (1−)y D, 则称集合 D 为凸集． 常见的凸集：单点集 { x }，空集 ，整个欧氏空间 Rn ， 超平面：  , H x R a1 x1 a2 x2 an xn b n =  + ++ = 半空间：     1 1 2 2 = n n n n T H x R a x a x a x b x R a x b + =  + + +   

凸集--举例 例：证明超球x≤r为凸集 证明：设x,y为超球中的任意两点p≤a≤1， 则有： llax+(1-a)y ≤alx+(1-ay‖ ≤cm+(1-a)r=r, 即点x+(1-a)y属于超球 ,所以超球为凸集

例： 证明超球 x  r 为凸集． 证明：设 x , y 为超球中的任意两点， 0    1, 则有： x + (1−)y   x + (1−) y r + (1−)r = r, 即点 x + (1−)y 属于超球, 所以超球为凸集． 凸集----举例

凸集--性质 (1) 任意多个凸集的交集为凸集 (2) 设D是凸集，B是一实数，则下面的 集合是凸集：BD={y=x,x∈D} (3)设D和D是R上的凸集，则 (a)D,+D={x+xlx,∈D,x2∈D,是凸集 (b)D-D2=1-x2Ix∈D,x2∈D2是凸集

(1) 任意多个凸集的交集为凸集． (2) 设 D 是凸集，  是一实数，则下面的 集合是凸集： D = y y = x , x D 凸集-----性质 (3)   (b)  | ,  . (a) | , ; 1 2 1 2 1 1 2 2 1 2 1 2 1 1 2 2 1 2 是凸集 是凸集 设 和 是 上的凸集，则 D D x x x D x D D D x x x D x D D D R n − = −   + = +  

凸集--性质 推论设D,i=1,2,,k是凸集，则∑B,D i= 也是凸集，其中B是实数. (4)S是凸集当且仅当S中任意有限个点的凸 组合仍然在S中

推论： = k i i Di 1 设 D i k  i , = 1,2,  , 是凸集，则 也是凸集，其中 i 是实数． (4) S 是凸集当且仅当S中任意有限个点的凸 组合仍然在S中. 凸集-----性质

凸集--性质 注：和集和并集有很大的区别，凸集的并集 未必是凸集，而凸集的和集是凸集 例：D,=《x,0yx∈表示x轴上的点. D=《和，y)y∈R表示y轴上的点 则D,UD,表示两个轴的所有点，它不是凸集 而D,+D2=R2凸集

注：和集和并集有很大的区别，凸集的并集 未必是凸集，而凸集的和集是凸集． 例： D (x ) x R T 1 = ,0  表示 x 轴上的点． D ( y) y R T 2 = 0,  表示 y 轴上的点． 则 D1  D2 表示两个轴的所有点，它不是凸集； 2 而 D1 + D2 = R 凸集． 凸集-----性质

凸集--凸包/壳(Convex Hul) 定义设S≤中任意有限个点的所有凸组合 所构成的集合称为S的凸包，记为H(S,即 ②3012-2=me H(S) i=1 定理2.1.4H(S是R"中所有包含S的凸集的交集 H(S是包含S的最小凸集

定义 设 S 中任意有限个点的所有凸组合 所构成的集合称为S的凸包，记为H(S),即 , n S  R 凸集-----凸包/壳(Convex Hull)       =    =  =  = = m i i i i m i H S i xi x S i m m N 1 1 ( )  , 0, 1,2..., ,  1, 定理2.1.4 H(S)是Rn 中所有包含S 的凸集的交集. H(S)是包含S 的最小凸集