《最优化方法》课程教学资源（PPT课件）凸集与凸函数（1/2）（刘二永）

理论部分 凸集和凸函数

理论部分 凸集和凸函数

凸集 定义1设集合DcR,若对于任意两点 x,y∈D,及实数a(0≤a≤1),都有 O c)y∈D 则称集合D为凸集 注:常见的凸集:空集,整个欧氏空间R 超平面H={∈Ra4x1+a2x2+…+anxn=b} 半空间7=(∈R"x+a2x2+…+axn≥b

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

例1:证明超球≤r为凸集 证明设x,y为超球中的任意两点0≤c≤1 则有:|ax+(1-a) ≤l|x+(1-a)训 a+(1-a)=r 即点ax+(1-a)v属于超球 所以超球为凸集

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

凸集的性质 1)有限个(可以改成无限)凸集的交集 为凸集 (2)设D是凸集,B是一实数,则下面的 集合是凸集:mD={y=x,x∈D} (3)设D,D2是凸集,则D1,D2的和集 D+D2={y=x+z,x∈D,z∈D2是凸集

凸集的性质 （１） 有限个（可以改成无限）凸集的交集 为凸集． （２）设 D 是凸集，  是一实数，则下面的 集合是凸集： D = y y = x, xD （３）设 1 2 D ,D 是凸集，则 1 2 D ,D 的和集 D1 + D2 = y y = x + z, xD1 ,zD2  是凸集

注:和集和并集有很大的区别,凸集的并集 未必是凸集,而凸集的和集是凸集 例:D=1x:0y|x∈R}表示x轴上的点 D2={0,ypy∈R}表示y轴上的点 则D∪D2表示两个轴的所有点它不是凸集; 而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 凸集．

推论设D,=1,2,…,k是凸集,则∑BD 也是凸集,其中B是实数 定义2:设x,∈R",i=1,2,…,k,实数41≥0 ∑λ=1,则x=∑λx,称为x,=1,2,…,k, 的凸组合 注:集中任意有限个点的凸组合仍然在该 凸集中

推论： = k i i Di 1 设 D i k  i , =1,2,  , 是凸集，则 也是凸集，其中 i 是实数． 定义2:设 x R ,i 1,2, , k , n i  =  实数  0, i = = k i i 1  1, 则 = = k i i i x x 1  , 称为 x ,i 1,2, , k , i =  的凸组合． 注：凸集中任意有限个点的凸组合仍然在该 凸集中．

极点 定义1设D为凸集x∈D,若D中不存在 两个相异的点y,z及某一实数a∈(0,1) 使得x=ay+(1-a)z,则称x为D的极点 例D={∈R"|≤aa>0),则川=a 上的点均为极点

极点 定义1 设 D 为凸集， xD, 若 D 中不存在 两个相异的点 y ,z 及某一实数  (0,1) 使得 x =y +(1−)z, 则称 x 为 D 的极点． 例： D = x R x  a(a  0), n 则 x = a 上的点均为极点．

证:设|=a,若存在y,z∈D及a∈(0,1) 使得x=+(1-a)z,则 =〈a+ (1-a)z,ay+(1-a)z) a2|y1+(1-a)|+2c(1-a)y州z 不等式要取等号,必须|y=z=a, 且y,z)=y,容易证明y=z=x 恨据定义可知x为极点

证：设 x = a, 若存在 y,z  D 及  (0,1), 使得 x =y +(1−)z, 则： a = x = y + (1−)z,y + (1−)z 2 2  y + (1−) z + 2(1−) y z 2 2 2 2 2  a 不等式要取等号，必须 y = z = a, 且 y,z = y z , 容易证明 y = z = x, 根据定义可知 x 为极点．

凸函数 定义4设函数f(x)定义在凸集DcR上, 若对任意的x,y∈D,及任意的a∈[0,1 都有:f(ax+(1-a))≤of(x)+(1-a)f(y) 则称函数f(x)为凸集D上的凸函数 定义5严格凸函数 注:将上述定义中的不等式反向,可以得到 凹函数的定义

凸函数 定义4 设函数 f (x) 定义在凸集 n D  R 上， 若对任意的 x, yD, 及任意的  0,1 都有： f (x +(1−)y)f (x)+(1−)f (y) 则称函数 f (x) 为凸集 D 上的凸函数． 定义5 严格凸函数 注：将上述定义中的不等式反向，可以得到 凹函数的定义．

例1:设f(x)=(x-1),试证明f(x)在(-∞,+∞ 上是严格凸函数 证明设x,y∈R,且x≠y,a∈(0,1)都有 f(ax+(1-a)y)-(a(x)+(1-a)f(y) (ax+(1-a)-1)2-a(x-1)2-(1-aXy-1) a(1-a)x-y)2<0 因此f(x)在(-∞,+∞)上是严格凸函数

例1：设 ( ) ( 1) , 2 f x = x − 试证明 f (x) 在 (−,+) 上是严格凸函数． 证明: 设 x, y R, 且 x  y, (0,1) 都有： f (x +(1−)y)−(f (x)+(1−)f (y)) ( ( ) ) ( ) ( )( ) 2 2 2 = x + 1− y −1 − x −1 − 1− y −1 (1 )( ) 0 2 = − − x − y  因此 f (x) 在 (−,+) 上是严格凸函数．