凸优化理论与应用凸集.ppt

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