01凸优化理论与应用-凸集PPT.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,凸优化理论与应用,第一章,凸集,2,仿射集(,Affine sets),直线的表示：,线段的表示：,仿射集的定义：过集合,C,内任意两点的直线均在集合,C,内，则称集合,C,为仿射集。,仿射集的例：直线、平面、超平面,3,仿射集,仿射包：包含集合,C,的最小的仿射集。,仿射维数：仿射包的维数。,相对内点（,relative interior,）：,相对内点,4,5,凸集(,Convex Sets),凸集的定义：集合,C,内任意两点间的线段均在集合,C,内，则称集合,C,为凸集。,凸集,6,仿射集与凸集的联系,7,所以仿射集一定是凸集,凸集,8,9,10,凸集,凸包的定义：包含集合,C,的最小的凸集。,凸集,11,12,锥(,Cones),锥的定义,（,nonnegative homogeneous,）,凸锥的定义：集合,C,既是凸集又是锥。,锥包的定义：集合,C,内点的所有锥组合。,锥,13,锥包,14,15,超平面和半空间,超平面(,hyperplane),：,半空间(,Halfspace)：,超平面,16,半空间,17,18,欧氏球和椭球,欧氏球(,euclidean ball):,椭球(,ellipsoid):,椭圆球,19,20,范数球和范数锥,范数,(norm),：,范数球,(norm ball),：,范数锥,(norm cone),：,21,多面体,(Polyhedra),多面体：,单纯形,(simplex),：,22,23,半正定锥,(Positive semidefinite cone),n,阶对称矩阵集：,n,阶半正定矩阵集：,n,阶正定矩阵集：,n,阶半正定矩阵集为凸锥！,24,保持凸性的运算,集合交运算,仿射变换,透视函数,(,perspective function,),线性分式函数,(,linear-fractional function,),25,真锥(,proper cone),真锥的定义：锥 满足如下条件,K,具有内点,K,内不含直线,26,广义不等式,真锥 下的,偏序关系,：,例：,逐项不等式,矩阵不等式,广义不等式,严格广义不等式,27,广义不等式的性质,28,严格广义不等式的性质,29,最值和极值,最小元的定义：设 ，对 ，都有,成立，则称 为 的最小元。,极小元的定义：设 ，对于 ，若,，则 成立，则称 为 的极小元。,30,分割超平面(,separating hyperplane),定理：设 和 为两不相交凸集，则存在超平面将 和 分离。即：,31,支撑超平面(,supporting hyperplane),定义：设集合 ，为 边界上的点。若存在 ，满足对任意 ，都有 成立，则称超平面 为集合 在点 处的支撑超平面。,定理：凸集边界上任意一点均存在支撑超平面。,定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。,32,对偶锥(,dual cone),对偶锥的定义：设 为锥，则集合,称为对偶锥。,对偶锥的性质：,真锥的对偶锥仍然是真锥！,33,对偶广义不等式,广义不等式与对偶等价性质,最小元的对偶特性：,34,对偶广义不等式,极小元的对偶特性,反过来不一定成立！,35,作业(1),P60 2.8,P60 2.10,P60 2.14,36,作业(2),P62,2.16,P62 2.18,P64 2.30,37,作业(3),P64 2.31,P64 2.33,