北邮最优化课件2凸分析

2020/5/5,最优化理论TPSHUAI,TPSHUAI,1,最优化理论与算法,帅天平北京邮电大学数学系2，凸分析与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,2,2.凸集与凸函数,2.1凸集与锥,2020/5/5,最优化理论TPSHUAI,TPSHUAI,3,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,4,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,5,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,6,运用定义不难验证如下命题：,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,7,2.凸集与凸函数,多面体(polyhedralset)是有限闭半空间的交.(可表为Axb).,2020/5/5,最优化理论TPSHUAI,TPSHUAI,8,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,9,多面集x|Ax0也是凸锥，称为多面锥。,2.凸集与凸函数,由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合,K(S)=x|0,xS,是包含S的最小凸锥.,锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间.,约定:非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合(称为凸锥组合)的所有点所构成的集合,记为coneS.若S凸,则,coneS=K(S)0,2020/5/5,最优化理论TPSHUAI,TPSHUAI,10,2.凸集与凸函数,Df2.5非空凸集中的点x称为极点,若x=x1+(1-)x2,(0,1),x1,x2S,则x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.,由上可知,任何有界凸集中任一点都可表成极点的凸组合.,2020/5/5,最优化理论TPSHUAI,TPSHUAI,11,2.凸集与凸函数,Def2.6.设非空凸集SRn,Rn中向量d0称为S的一个回收方向(方向),若对每一xS,R(x.d)=x+d|0S.S的所有方向构成的尖锥称为S的回收锥,记为0+S,方向d1和d2称为S的两个不同的方向,若对任意0,都有d1d2；方向d称为S的极方向extremedirection,若d=d1+(1-)d2,(0,1),d1,d2是S的两个方向,则有d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合,2020/5/5,最优化理论TPSHUAI,TPSHUAI,12,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,13,2.凸集与凸函数,表示定理,Th2.4若多面体P=xRn|Axb,r(A)=n则:,则,(3)指标集J是空集当且仅当P是有界集合,即多胞形.,2020/5/5,最优化理论TPSHUAI,TPSHUAI,14,2.凸集与凸函数,表示定理直观描述:设X为非空多面体.则存在有限个极点x1,xk,k0.进一步,存在有限个极方向d1,dl,l0当且仅当X无界.进而,xX的充要条件是x可以表为x1,xk的凸组合和d1,dl的非负线性组合(凸锥组合).,推论2.1若多面体S=x|Ax=b,x0非空,则S必有极点.,2020/5/5,最优化理论TPSHUAI,TPSHUAI,15,2.2凸集分离定理,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,16,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,17,证明：令,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,18,所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。,2.凸集与凸函数,下证明唯一性,2020/5/5,最优化理论TPSHUAI,TPSHUAI,19,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,20,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,21,2.凸集与凸函数,证明提纲,2020/5/5,最优化理论TPSHUAI,TPSHUAI,22,由此可得,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,23,2.凸集与凸函数,Th2.7表明，S为闭凸集，yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理,2020/5/5,最优化理论TPSHUAI,TPSHUAI,24,证明,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,25,推论2.2：设S为Rn中的非空集合，yS,则存在非零向量p，使对xclS,pT(x-y)0,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,26,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,27,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,28,作为凸集分离定理的应用，下面介绍两个择一定理：Farkas定理和Gordan定理，它们在最优化理论中是很有用的。,2.凸集与凸函数,2.3择一定理,2020/5/5,最优化理论TPSHUAI,TPSHUAI,29,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,30,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,31,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,32,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,33,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,34,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,35,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,36,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,37,2.凸集与凸函数,2.4凸函数,Df2.10设SRn是非空凸集,函数f:SR,若对任意x1,x2S,和每一(0,1)都有f(x1+(1-)x2)f(x1)+(1-)f(x2)则称f是S上的凸函数.若上面的不等式对于xy严格成立,则称f是S上的严格凸函数.若-f是S上的凸函数,则称f是S上的凹函数.若-f是S上的严格凸函数,则称f是S上的严格凹函数.,2.4.1基本性质,2020/5/5,最优化理论TPSHUAI,TPSHUAI,38,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,39,Th2.13设f是一凸函数，则对任意的xRn和d(0)Rn，f在x处沿方向d的方向导数存在。,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,40,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,41,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,42,命题2.3设f是定义在凸集S上的凸函数，则(1)所有凸函数f的集合关于凸锥组合运算是封闭的,即(a)实数0，则f也是定义在S上的凸函数(b)设f1和f2是定义在凸集S上的凸函数，则f1+f2也是定义在S上的凸函数,2.凸集与凸函数,(2)函数f在开集intS内是连续的.(3)函数f的水平集L(f,)=x|xS,f(x),R和上镜图epi(f)=(x,y)|xS,yR,yf(x)都是凸集,2020/5/5,最优化理论TPSHUAI,TPSHUAI,43,2.凸集与凸函数,设S为Rn中的非空凸集,则f(x)是凸的当且仅当上镜图epif=(x,y)|xS,yR,yf(x)是凸集,对上镜图事实上我们有如下定理,2020/5/5,最优化理论TPSHUAI,TPSHUAI,44,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,45,定理2.14设SRn为一非空凸集，f是定义在S上的凸函数，则f在S上的局部极小点是整体极小点，且极小点的集合为凸集。,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,46,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,47,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,48,2.凸集与凸函数,2.5.2凸函数的判别,Th2.16.设S是Rn中的非空开凸集,f(x):SR是可微的函数则f(x)是凸函数当且仅当对任意的x*S,我们有f(x)f(x*)+f(x*)(x-x*),任意xS.类似的,f(x)严格凸当且仅当对每一x*S,f(x)f(x*)+f(x*)(x-x*),任意xS.,2.4.2凸函数的判别,2020/5/5,最优化理论TPSHUAI,TPSHUAI,49,2.凸集与凸函数,2020/5/5,最优化理论TPSHUAI,TPSHUAI,50,2.凸集与凸函数,Th2.16*.设S是Rn上的非空开凸集,f(x)为S到R上的可微函数.则f(x)是凸函数当且仅当任意的x1,x2S,有(f(x2)-f(x1)(x2-x1)0.类似的,f严格凸当且仅当对任意相异的x1,x2S,(f(x2)-f(x1)(x2-x1)0.,2020/5/5,最优化理论TPSHUAI,TPSHUAI,51,