北邮最优化课件2凸分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最优化理论,TP SHUAI,*,TP SHUAI,1,最优化理论与算法,帅天平,北京邮电大学数学系,2,，凸分析与凸函数,2026/5/27 周三,TP SHUAI,2,2.,凸集与凸函数,2.1,凸集与锥,2026/5/27 周三,TP SHUAI,3,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,4,2.,凸集与凸函数,x,0,x,x-x,0,p,x,0,x,x-x,0,p,2026/5/27 周三,TP SHUAI,5,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI6,运用定义不难验证如下命题,：,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,7,2.,凸集与凸函数,多面体,(,polyhedral set,),是有限闭半空间的交,.,(,可表为,Ax,b,).,x,4,x,3,x,2,x,1,x,5,x,y,2026/5/27 周三,TP SHUAI,8,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,9,多面集,x|,Ax,0,也是凸锥，称为,多面锥,。,2.,凸集与凸函数,由定义可知,锥关于正的数乘运算封闭,凸锥关于加法,和正的数乘封闭,一般的,对于凸集,S,集合,K,(,S,)=,x|,0,x,S,是包含,S,的最小凸锥,.,锥,C,称为,尖锥,若,0,S.,尖锥称为,突出,的,若它不包含一维子空间,.,约定,:,非空集合,S,生成的凸锥,是指可以表示成,S,中有限个元素的非负线性组合,(,称为凸锥组合,),的所有点所构成的集合,记为,coneS,.,若,S,凸,则,coneS,=,K,(,S,),0,2026/5/27 周三,TP SHUAI,10,2.,凸集与凸函数,Df,2,.5,非空凸集中的点,x,称为,极点,若,x,=,x,1,+(1-,),x,2,(0,1),x,1,x,2,S,则,x,=,x,1,=,x,2,.,换言之,x,不能表示成,S,中两个不同点的凸组合,.,x,4,x,3,x,2,x,1,x,5,x,y,S,x,由上可知,任何有界凸集中任一点都可表成极点的凸组合,.,2026/5/27 周三,TP SHUAI,11,2.,凸集与凸函数,Def 2.6,.,设非空凸集,S,R,n,R,n,中向量,d,0,称为,S,的,一个,回收方向,(,方向,),若对每一,x,S,R(x.d)=,x,+,d|,0,S,.S,的所有方向构成的尖锥称为,S,的,回收锥,记为,0+S,方向,d,1,和,d,2,称为,S,的两个,不同的方向,若对任意,0,都有,d,1,d,2,；,方向,d,称为,S,的,极方向,extreme direction,若,d,=,d,1,+(1-,),d,2,(0,1),d,1,d,2,是,S,的两个方向,则有,d,=,d,1,=,d,2,.,换言之,d,不能表成它的两个不同方向的凸锥组合,x,0,x,0,d,d,d,2026/5/27 周三,TP SHUAI,12,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,13,2.,凸集与凸函数,表示定理,Th2.4,若多面体,P,=,x,Rn,|,Ax,b,r(,A,)=,n,则,:,(1)P,的极点集是非空的有限集合,记为,x,k,k,K,则,j,(2),记,P,的极方向集为,d,j,J,(,约定,P,不存在极方向时,J=),(3),指标集,J,是空集当且仅当,P,是有界集合,即多胞形,2026/5/27 周三,TP SHUAI,14,2.,凸集与凸函数,表示定理直观描述,:,设,X,为非空多面体,.,则存在有限个极点,x,1,x,k,k,0,.,进一步,存在有限个极方向,d,1,d,l,l,0,当且仅当,X,无界,.,进而,x,X,的充要条件是,x,可以表为,x,1,x,k,的凸组合和,d,1,d,l,的非负线性组合,(,凸锥组合,).,x,y,x,1,x,2,x,3,d,1,d,2,0,推论,2.1,若多面体,S=x|Ax=b,x,0,非空,则,S,必有极点,.,2026/5/27 周三,TP SHUAI,15,2.2,凸集分离定理,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,16,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,17,证明：令,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,18,所以为柯西列，必有极限,且由,S,为闭集知。此极限点必在,S,中。,2.,凸集与凸函数,下证明唯一性,2026/5/27 周三,TP SHUAI,19,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,20,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,21,2.,凸集与凸函数,x,p,X,(i),(,x,-)(,y,-,),0,对任意,x,X,.,(ii),令,p,=y,-,，p p,.,T,x,x,x,y,x,证明提纲,2026/5/27 周三,TP SHUAI,22,由此可得,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,23,2.,凸集与凸函数,Th2.7,表明，,S,为闭凸集，,y,S,，则,y,与,S,可分离。若,令,clS,表示非空集合,S,的闭包，则当,y,clS,时，定理结论也真。实际上我们有下述定理,2026/5/27 周三,TP SHUAI,24,证明,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,25,推论,2.2,：设,S,为,R,n,中的非空集合，,y,S,则存在非零向量,p,，使对,xclS,p,T,(x-y)0,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,26,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,27,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,28,作为凸集分离定理的应用，下面介绍两个择一定理：,Farkas,定理,和,Gordan,定理,，它们在最优化理论中是很有用的。,2.,凸集与凸函数,2.3,择一定理,2026/5/27 周三,TP SHUAI,29,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,30,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,31,2.,凸集与凸函数2026/5/27 周三,TP SHUAI,32,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,33,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,34,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,35,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,36,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,37,2.,凸集与凸函数,2.4,凸函数,Df,2.10,设,S,R,n,是非空凸集,函数,f,:S,R,若对任意,x,1,x,2,S,和每一,(0,1),都有,f,(,x,1,+(1-),x,2,),fx,1,)+(,1-,),f(,x,2,),则称,f,是,S,上的,凸函数,.,若上面的不等式对于,x,y,严格成立,则称,f,是,S,上的,严格凸函数,.,若,-f,是,S,上的凸函数,则称,f,是,S,上的,凹函数,.,若,-f,是,S,上的严格凸函数,则称,f,是,S,上的,严格凹函数,.,2.4.1,基本性质,2026/5/27 周三,TP SHUAI,38,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,39,Th2.13,设,f,是一凸函数，则对任意的,x,R,n,和,d,(,0,),R,n,，,f,在,x,处沿方向,d,的方向导数存在。,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,40,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,41,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,42,命题,2.3,设,f,是定义在凸集,S,上的凸函数，则,(1),所有凸函数,f,的集合关于凸锥组合运算是封闭的,即,(a),实数,0,，则,f,也,是定义在,S,上的凸函数,(b),设,f,1,和,f,2,是定义在凸集,S,上的凸函数，,则,f,1,+,f,2,也,是定义在,S,上的凸函数,2.,凸集与凸函数,(2),函数,f,在开集,intS,内是连续的,.,(3),函数,f,的水平集,L(,f,)=,xx,S,f,(,x,),R,和上镜图,epi(,f,)=(,x,y,)|,xS,y,R,y,f(x),都是凸集,2026/5/27 周三,TP SHUAI,43,2.,凸集与凸函数,设,S,为,Rn,中的非空凸集,则,f,(,x,),是凸的当且仅当上镜图,epi,f,=(,x,y,)|,x,S,y,R,y,f,(,x,),是凸集,对上镜图事实上我们有如下定理,2026/5/27 周三,TP SHUAI,44,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,45,定理,2.14,设,S,R,n,为一非空凸集，,f,是定义在,S,上的凸函数，则,f,在,S,上的局部极小点是整体极小点，且极小点的集合为凸集。,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,46,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,47,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,48,2.,凸集与凸函数,2.5.2,凸函数的判别,Th2.16,.,设,S,是,R,n,中的非空开凸集,f,(,x,):S,R,是可微的函数 则,f,(,x,),是凸函数当且仅当对任意的,x,*,S,我们有,f,(,x,),f,(,x,*)+,f,(,x,*)(,x,-,x,*),任意,x,S,.,类似的,f,(,x,),严格凸当且仅当对每一,x,*,S,f,(x,),f,(,x,*)+,f,(,x,*)(,x,-,x,*),任意,x,S,.,2.4.2,凸函数的判别,2026/5/27 周三,TP SHUAI,49,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,50,2.,凸集与凸函数,Th 2.16*,.,设,S,是,R,n,上的非空开凸集,f,(,x,),为,S,到,R,上的可微函数,.,则,f,(,x,),是凸函数当且仅当任意的,x,1,x,2,S,有,(,f,(,x,2,)-,f,(,x,1,)(,x,2,-,x,1,),0.,类似的,f,严格凸当且仅当对任意相异的,x,1,x,2,S,(,f,(,x,2,)-,f,(,x,1,)(,x,2,-,x,1,),0.,2026/5/27 周三,TP SHUAI,51,2.,凸集与凸函数,2026/5/27 周三,TP SHUAI,52,2.,凸集与凸函数,Def 2.11,.,设,S,是,R,n,上的非空开集,f,(,x,),f,(,x,):S,R,的函数 则,f,(,x,),在点,x,*,int(,S,),称为二次可微的,若存在向量,f,(,x,*),和,n,n,(,Hessian,),矩阵,H,(,x,*),及函数,:,R,n,R,使得对所有的,x,S,f,(,x,),=,f,(,x,*)+,f,(,x,*)(,x,-,x,*)+0.5(,x,-,x,*),H,(,x,*)(,x,-,x,*)+|,x,-,x,*|,(,x,-,x,*),其中,lim,(,x,-,x,*)=0.,2,x,*,x,*,x,x,*,Th 2.17,设,S,是,R,n,a,上的非空开凸集,f,(,x,),为,S,到,R,上的二次可微函数,.,则,(1),f,(,x,),是凸函数当且仅当,S,上每一点的,Hessian,矩阵是半正定的,.,(2),f,(,x,),是严格凸函数当且仅当,S,上每一点的,Hessian,矩阵是正定的,.,2026/5/27 周三,TP SHUAI,53,凸规划,2.,凸集与凸函数,2026/5/27 周三,