线性规划-凸集凸函数(课堂PPT).ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,线性规划,凸集和凸函数,1,凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。,定义,1,设 ，若对,D,中任意两点 与 ，连接,与 的线段仍属于,D,；换言之，对 ，,D,，,0,1,恒有,+(1-),D,则称,D,为,凸集,。,+(1-),称为 和 的,凸组合,。,n,R,D,),1,(,x,),2,(,x,),1,(,x,),2,(,x,),1,(,x,),2,(,x,a,),1,(,x,a,),2,(,x,a,),1,(,x,a,a,),2,(,x,),1,(,x,),2,(,x,2,例,3,(i),超平面 为凸集。,b,=,=,x,P,x,T,H,定义为,(ii),半空间 为凸集。,b,=,-,x,P,x,T,H,定义为,(iii),射线 为凸集，其中,d,为给定的非零向量，为定点。,0,),0,(,+,=,=,l,l,d,x,x,x,L,),0,(,x,(iv),超球 是凸集。,(v),欧式空间 是凸集，规定空集 是凸集,4,凸集的性质,有限个凸集的交集仍然是凸集。,设 是凸集，则 是凸集。,设 是凸集，则 是凸集。,凸集的和集仍然是凸集。,设 是凸集，则,是凸集。,推论：设 是凸集，则 也是凸集，,其中 。,5,定义,3,极点（顶点）,：,设,D,是凸集,若,D,中的点,x,不能成为,D,中任何线段上的内点，则称,x,为凸集,D,的极点。,设,D,为凸集，,XD,若,X,不能用,X,(1),D,X,(2),D,两点的,一个凸组合表示为,X=X,(1),+(1-)X,(2),其中,01,，,则称,X,为,D,的一个极点。,定义,2.,凸组合,：设,X,(1),，,X,(2),，,，,X,(k),是,n,维欧式空间中的,k,个点，若存在,1,2,k,满足,0,i,1,(,i=1,2,k),使,X=,1,X,(1),+,2,X,(2),+,k,X,(k),，,则称,X,为,X,(1),，,X,(2),，,，,X,(k),的凸组合。,6,多边形的,顶点,是,凸集的,极点（顶点）,。,圆周上的点都是,凸集的,极点（顶点）,。,7,定义,4,设,D,为,R,中非空凸集，若对 ，,D,，,(0,1),恒有,n,),1,(,x,),2,(,x,a,f,+(1-)+(1-),f,(*),),1,(,x,a,),2,(,x,a,),(,),1,(,x,f,a,a,),(,),2,(,x,则称 为,D,上的凸函数；进一步，若 时，,(*),式仅,成立。,),(,x,f,x,f(x),16,定理,3,（二阶条件）：,设,D,是,R,中非空开凸集,是定义在,D,上的二次可微函数,则 是,凸函数,的充要条件为对,x,D,0,即,Hesse,矩阵,半正定,。,n,),(,x,f,),(,x,f,),(,2,x,f,),(,2,x,f,若,x,D,0,，即,Hesse,矩阵,正定,，则 为,严格凸函数,。,),(,2,x,f,),(,x,f,例：,证明函数,是 上的凸函数。,17,若规划,=,=,=,l,j,h,m,i,g,t,s,f,j,i,2,1,0,),(,2,1,0,),(,.,.,),(,min,x,x,x,中,和,-,为凸函数,是线性函数,则上述问题为求凸规划。,),(,x,f,),(,x,i,g,),(,x,i,h,定义,6:,凸规划,设,D,为凸集,是定义在,D,上的凸函数，则称规划问题 为凸规划。,18,凸规划是非线性规划中的一种重要特殊情形，它具有很好的性质。,定理,4,：（,1),凸规划的任意局部极小点就是整体极小点，且极小点集合是凸集。,(2),如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点还是唯一的。,19,