01凸优化理论与应用_凸集

信息与通信工程学院庄伯金[e-mail]1凸优化理论与应用第一章凸集信息与通信工程学院庄伯金[e-mail]2仿射集(Affinesets)直线的表示：12(1),.yxxR.线段的表示：12(1),[0,1].yxx.仿射集的定义：过集合C内任意两点的直线均在集合C内，则称集合C为仿射集。仿射集的例：直线、平面、超平面Axb信息与通信工程学院庄伯金[e-mail]3仿射集仿射包：包含集合C的最小的仿射集。aff{|,1}iiiiCxxC仿射维数：仿射包的维数。相对内点（relativeinterior）：relint{|(,)aff,0}CxBxrCCr相对内点信息与通信工程学院庄伯金[e-mail]4信息与通信工程学院庄伯金[e-mail]5凸集(ConvexSets)凸集的定义：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。1212,,[0,1],(1)xxCxxC则111,...,,[0,1]1,kkiiikiiixxCxC且则凸集信息与通信工程学院庄伯金[e-mail]6仿射集与凸集的联系信息与通信工程学院庄伯金[e-mail]71212,,[0,1],(1)xxCxxC则所以仿射集一定是凸集凸集信息与通信工程学院庄伯金[e-mail]8信息与通信工程学院庄伯金[e-mail]9信息与通信工程学院庄伯金[e-mail]10凸集凸包的定义：包含集合C的最小的凸集。11conv{|,0,1}kkiiiiiiiCxxC凸集信息与通信工程学院庄伯金[e-mail]11信息与通信工程学院庄伯金[e-mail]12锥(Cones)锥的定义（nonnegativehomogeneous）,0,.xCxC则有凸锥的定义：集合C既是凸集又是锥。12121122,,,0,.xxCxxC则有锥包的定义：集合C内点的所有锥组合。1{|,0}kiiiiixxC锥信息与通信工程学院庄伯金[e-mail]13锥包信息与通信工程学院庄伯金[e-mail]14信息与通信工程学院庄伯金[e-mail]15超平面和半空间超平面(hyperplane)：{|}Txaxb半空间(Halfspace)：{|}Txaxb{|}Txaxb超平面信息与通信工程学院庄伯金[e-mail]16半空间信息与通信工程学院庄伯金[e-mail]17信息与通信工程学院庄伯金[e-mail]18欧氏球和椭球欧氏球(euclideanball):22(,){|}{|()()}ccTccBxrxxxrxxxxxr椭球(ellipsoid):12{|()()},TccExxxPxxrP为对称正定矩阵椭圆球信息与通信工程学院庄伯金[e-mail]19信息与通信工程学院庄伯金[e-mail]20范数球和范数锥范数(norm)：0,00;||,xxxtxtxtxyxy当且仅当；R;范数球(normball)：(,){|}ccBxrxxxr范数锥(normcone)：{(,)|}xtxt信息与通信工程学院庄伯金[e-mail]21多面体(Polyhedra)多面体：{|,}TTjjiiPxaxbcxd单纯形(simplex)：10000{|0,1,,...,}kkiiiikiivvvvv线性无关信息与通信工程学院庄伯金[e-mail]22信息与通信工程学院庄伯金[e-mail]23半正定锥(Positivesemidefinitecone)n阶对称矩阵集：{|}nnnTSXXXnRn阶半正定矩阵集：{|0}nnSXSXn阶正定矩阵集：{|0}nnSXSXn阶半正定矩阵集为凸锥！信息与通信工程学院庄伯金[e-mail]24保持凸性的运算集合交运算仿射变换透视函数(perspectivefunction)(,)/,,nPztztztRR线性分式函数(linear-fractionalfunction)()()/(),,,,0TmnmnTfxAxbcxdAbcdcxdRRRR信息与通信工程学院庄伯金[e-mail]25真锥(propercone)真锥的定义：锥满足如下条件nKR1.4.KKKK为凸集；2.为闭集；3.非中空；有端点。K具有内点K内不含直线信息与通信工程学院庄伯金[e-mail]26广义不等式真锥下的偏序关系：KKxyyxKintKxyyxK例：逐项不等式矩阵不等式广义不等式严格广义不等式信息与通信工程学院庄伯金[e-mail]27广义不等式的性质1.;2.,;3.,;4.,;5.,0;6.,lim,lim.KKKKKKKKKKKiKiiiKxxxyyxxyxyyzxzxyuvxuyvxyxyxyxxyyxy信息与通信工程学院庄伯金[e-mail]28严格广义不等式的性质1.;2.;3.,;4.,05.,.KKKKKKKKKKxyxyxxxyuvxuyvxyxyxyuxuy足够小信息与通信工程学院庄伯金[e-mail]29最值和极值最小元的定义：设，对，都有成立，则称为的最小元。xSySKxyxS极小元的定义：设，对于，若，则成立，则称为的极小元。xSySKyxxSyx信息与通信工程学院庄伯金[e-mail]30分割超平面(separatinghyperplane)定理：设和为两不相交凸集，则存在超平面将和分离。即：,,.TTxCaxbxDaxb且CDCD信息与通信工程学院庄伯金[e-mail]31支撑超平面(supportinghyperplane)定义：设集合，为边界上的点。若存在，满足对任意，都有成立，则称超平面为集合在点处的支撑超平面。C0xC0axC0TTaxax0{|}TTxaxaxC0x定理：凸集边界上任意一点均存在支撑超平面。定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。信息与通信工程学院庄伯金[e-mail]32对偶锥(dualcone)对偶锥的定义：设为锥，则集合称为对偶锥。K*{|0,}TKyxyxK对偶锥的性质：*****1..3.KKKKKKK是闭凸集；2若非中空，则有端点；若的闭包有端点，则非中空；4.是的闭凸包；真锥的对偶锥仍然是真锥！信息与通信工程学院庄伯金[e-mail]33对偶广义不等式广义不等式与对偶等价性质**,forall0;,forall0,0.TTKKTTKKxyxyxyxy最小元的对偶特性：*0,,.TKxSKxzzS为集合中关于偏序的最小元对所有为使最小的值信息与通信工程学院庄伯金[e-mail]34对偶广义不等式极小元的对偶特性*0,,.TKxzzSx为使最小的值为极小元反过来不一定成立！信息与通信工程学院庄伯金[e-mail]35作业(1)P602.8P602.10P602.14信息与通信工程学院庄伯金[e-mail]36作业(2)P622.16P622.18P642.30信息与通信工程学院庄伯金[e-mail]37作业(3)P642.31P642.33