凸优化理论与应用

信息与通信工程学院庄伯金[e-mail]1凸优化理论与应用庄伯金[e-mail]信息与通信工程学院庄伯金[e-mail]2优化理论概述什么是优化问题？0minimize()subjectto(),1,...,iinfxfxbimxRObjectivefunctionConstraintfunctions信息与通信工程学院庄伯金[e-mail]3几类经典的优化问题线性规划问题()ifx为线性函数最小二乘问题202()-,0.fxAxbm＝凸优化问题()ifx为凸函数凸优化问题理论上有有效的方法进行求解！信息与通信工程学院庄伯金[e-mail]4本课程的主要内容理论部分凸集和凸函数凸优化问题对偶问题应用部分逼近与拟合统计估计几何问题算法部分非约束优化方法等式约束优化方法内点法信息与通信工程学院庄伯金[e-mail]5熟悉了解凸优化理论的基本原理和基本方法；掌握实际问题转化为凸优化问题的基本方法；掌握最优化问题的经典算法。课程要求信息与通信工程学院庄伯金[e-mail]6参考书目StephenBoydandLievenVandenberghe,“ConvexOptimization”,CambridgeUniversityPress.袁亚湘、孙文瑜，“最优化理论与方法”，科学出版社，1999。信息与通信工程学院庄伯金[e-mail]7凸优化理论与应用第一章凸集信息与通信工程学院庄伯金[e-mail]8仿射集(Affinesets)直线的表示：12(1),.yxxR.线段的表示：12(1),[0,1].yxx.信息与通信工程学院庄伯金[e-mail]9仿射集(Affinesets)仿射集的定义：过集合C内任意两点的直线均在集合C内，则称集合C为仿射集。仿射集的例：直线、平面、超平面Axb信息与通信工程学院庄伯金[e-mail]10仿射集仿射包：包含集合C的最小的仿射集。aff{|,1}iiiiCxxC仿射维数：仿射包的维数。信息与通信工程学院庄伯金[e-mail]11仿射集内点（interior）：int{|(,),0}CxBxrCr相对内点（relativeinterior）：relint{|(,)aff,0}CxBxrCCr信息与通信工程学院庄伯金[e-mail]12凸集(ConvexSets)凸集的定义：集合C内任意两点间的线段均在集合C内，则称集合C为凸集。1212,,[0,1],(1)xxCxxC则111,...,,[0,1]1,kkiiikiiixxCxC且则信息与通信工程学院庄伯金[e-mail]13凸集凸包的定义：包含集合C的最小的凸集。11conv{|,0,1}kkiiiiiiiCxxC信息与通信工程学院庄伯金[e-mail]14锥(Cones)锥的定义：,0,.xCxC则有凸锥的定义：集合C既是凸集又是锥。12121122,,,0,.xxCxxC则有锥包的定义：集合C内点的所有锥组合。1{|,0}kiiiiixxC信息与通信工程学院庄伯金[e-mail]15超平面和半空间超平面(hyperplane)：{|}Txaxb半空间(Halfspace)：{|}Txaxb{|}Txaxb信息与通信工程学院庄伯金[e-mail]16欧氏球和椭球欧氏球(euclideanball):22(,){|}{|()()}ccTccBxrxxxrxxxxxr椭球(ellipsoid):12{|()()},TccExxxPxxrP为对称正定矩阵2(,){|1}ccBxrxruu1/22{|1},cExAuuAP信息与通信工程学院庄伯金[e-mail]17范数球和范数锥范数(norm)：0,00;||,xxxtxtxtxyxy当且仅当；R;范数球(normball)：(,){|}ccBxrxxxr范数锥(normcone)：{(,)|}xtxt信息与通信工程学院庄伯金[e-mail]18多面体(Polyhedra)多面体：{|,}TTjjiiPxaxbcxd单纯形(simplex)：10000{|0,1,,...,}kkiiiikiivvvvv线性无关信息与通信工程学院庄伯金[e-mail]19半正定锥(Positivesemidefinitecone)n阶对称矩阵集：{|}nnnTSXXXnRn阶半正定矩阵集：{|0}nnSXSXn阶正定矩阵集：{|0}nnSXSXn阶半正定矩阵集为凸锥！信息与通信工程学院庄伯金[e-mail]20保持凸性的运算集合交运算仿射变换透视/投射函数(perspectivefunction)(,)/,,nPztztztRR(),,mnmfxAxbARbR信息与通信工程学院庄伯金[e-mail]21保持凸性的运算线性分式函数(linear-fractionalfunction)()()/(),,,,0TmnmnTfxAxbcxdAbcdcxdRRRR信息与通信工程学院庄伯金[e-mail]22真锥(propercone)真锥的定义：锥满足如下条件nKR1.4.KKKK为凸集；2.为闭集；3.非中空；有端点。K具有内点K内不含直线信息与通信工程学院庄伯金[e-mail]23广义不等式真锥下的偏序关系：KKxyyxKintKxyyxK例：逐项不等式矩阵不等式广义不等式严格广义不等式信息与通信工程学院庄伯金[e-mail]24广义不等式的性质1.;2.,;3.,;4.,;5.,0;6.,lim,lim.KKKKKKKKKKKiKiiiKxxxyyxxyxyyzxzxyuvxuyvxyxyxyxxyyxy信息与通信工程学院庄伯金[e-mail]25严格广义不等式的性质1.;2.;3.,;4.,05.,.KKKKKKKKKKxyxyxxxyuvxuyvxyxyxyuxuy足够小信息与通信工程学院庄伯金[e-mail]26最值和极值最小元的定义：设，对，都有成立，则称为的最小元。xSySKxyxS极小元的定义：设，对于，若，则成立，则称为的极小元。xSySKyxxSyx信息与通信工程学院庄伯金[e-mail]27分割超平面(separatinghyperplane)定理：设和为两不相交凸集，则存在超平面将和分离。即：,,.TTxCaxbxDaxb且CDCD信息与通信工程学院庄伯金[e-mail]28支撑超平面(supportinghyperplane)定义：设集合，为边界上的点。若存在，满足对任意，都有成立，则称超平面为集合在点处的支撑超平面。C0xC0axC0TTaxax0{|}TTxaxaxC0x定理：凸集边界上任意一点均存在支撑超平面。定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。信息与通信工程学院庄伯金[e-mail]29对偶锥(dualcone)对偶锥的定义：设为锥，则集合称为对偶锥。K*{|0,}TKyxyxK对偶锥的性质：*****1..3.KKKKKKK是闭凸集；2若非中空，则有端点；若的闭包有端点，则非中空；4.是的闭凸包；真锥的对偶锥仍然是真锥！信息与通信工程学院庄伯金[e-mail]30对偶广义不等式广义不等式与对偶等价性质**,forall0;,forall0,0.TTKKTTKKxyxyxyxy最小元的对偶特性：*0,,.TKxSKxzzS为集合中关于偏序的最小元对所有为使最小的值信息与通信工程学院庄伯金[e-mail]31对偶广义不等式极小元的对偶特性*0,,.TKxzzSx为使最小的值为极小元反过来不一定成立！信息与通信工程学院庄伯金[e-mail]32作业P602.8P602.10P602.14P622.16P622.18P642.30P642.31P642.33信息与通信工程学院庄伯金[e-mail]33凸优化理论与应用第二章凸函数信息与通信工程学院庄伯金[e-mail]34凸函数的定义1.定义域为凸集；domf.((1))()(1)().fxyfxfy2.，有,dom,01xyf.凸函数的定义：函数，满足:nfnRR.凸函数的扩展定义：若为凸函数，则可定义其扩展函数为f.:{}nfnRR.()dom()domfxxffxxf凸函数的扩展函数也是凸函数！信息与通信工程学院庄伯金[e-mail]35凸函数的一阶微分条件若函数的定义域为开集，且函数一阶可微，则函数为凸函数当且仅当为凸集，且对()()()()Tfyfxfxyxfffdomfdomf,domxyf信息与通信工程学院庄伯金[e-mail]36凸函数的二阶微分条件f若函数的定义域为开集，且函数二阶可微，则函数为凸函数当且仅当为凸集，且对，其Hessian矩阵2()0.fxffdomfdomfdomxf信息与通信工程学院庄伯金[e-mail]37凸函数的例幂函数,,1or0.axxaaR负对数函数logx负熵函数logxx范数函数pxaxe指数函数信息与通信工程学院庄伯金[e-mail]38凸函数的例1()max(,...,)nfxxx2()/,0fxxyy1()log(...)nxxfxee1/1()(),domnnniifxxfR()log(det),domnfXXfS信息与通信工程学院庄伯金[e-mail]39下水平集(sublevelset)定理：凸函数的任一下水平集均为凸集。任一下水平集均为凸集的函数不一定为凸函数。{dom|()}Cxffx称为的下水平集。f定义：集合信息与通信工程学院庄伯金[e-mail]40函数上半图(epigraph)定理：函数为凸函数当且仅当的上半图为凸集。ffepi{(,)|dom,()}fxtxffxt称为函数的上半图。f定义：集合信息与通信工程学院庄伯金[e-mail]41Jensen不等式为凸函数，则有：1111(...)()...()nnnnfxxfxfxf101,...1.in其中Jensen不等式的另外形式