北邮庄伯金-凸优化理论与应用.pdf-资料库

9bd04191-93bd-485a-afbe-3a98da7bc320.pdf-第1页.png

第1页 / 共37页

9bd04191-93bd-485a-afbe-3a98da7bc320.pdf-第2页.png

第2页 / 共37页

9bd04191-93bd-485a-afbe-3a98da7bc320.pdf-第3页.png

第3页 / 共37页

9bd04191-93bd-485a-afbe-3a98da7bc320.pdf-第4页.png

第4页 / 共37页

9bd04191-93bd-485a-afbe-3a98da7bc320.pdf-第5页.png

第5页 / 共37页

9bd04191-93bd-485a-afbe-3a98da7bc320.pdf-第6页.png

第6页 / 共37页

9bd04191-93bd-485a-afbe-3a98da7bc320.pdf-第7页.png

第7页 / 共37页

9bd04191-93bd-485a-afbe-3a98da7bc320.pdf-第8页.png

第8页 / 共37页

2012/9/24 凸优化理论与应用庄伯金 Bjzhuang@bupt.edu.cn 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 几类经典的优化问题  线性规划问题  最小二乘问题  凸优化问题信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 凸优化问题理论上有有效的方法进行求解！课程要求  熟悉了解凸优化理论的基本原理和基本方法；  掌握实际问题转化为凸优化问题的基本方法；  掌握最优化问题的经典算法。信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 1 3 5 优化理论概述  什么是优化问题？ Objective function Constraint functions 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 本课程的主要内容  理论部分  凸集和凸函数  凸优化问题  对偶问题  应用部分  逼近与拟合  统计估计  几何问题  算法部分  非约束优化方法  等式约束优化方法  内点法信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 2 4 参考书目  Stephen Boyd and Lieven Vandenberghe, “Convex Optimization”, Cambridge University Press.  袁亚湘、孙文瑜，“最优化理论与方法”，科学出版社，1999。信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 6 1 0minimize ()subject to (), 1,...,iinfxfxbimxR()ifx为线性函数202()-, 0.fxAxbm＝()ifx为凸函数

凸优化理论与应用第一章凸集仿射集(Affine sets)  直线的表示：  线段的表示：信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 7 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 仿射集(Affine sets) 仿射集  仿射集的定义：过集合C内任意两点的直线均在集合  仿射包：包含集合C的最小的仿射集。 C内，则称集合C为仿射集。  仿射集的例：直线、平面、超平面  仿射维数：仿射包的维数。信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 9 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 2012/9/24 8 10 仿射集  内点（interior）：  相对内点（relative interior）：凸集(Convex Sets)  凸集的定义：集合C内任意两点间的线段均在集合C 内，则称集合C为凸集。信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 11 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 12 2 12(1), .yxxR.12(1), [0,1].yxx.Axbaff {|,1}iiiiCxxCint {|(,),0}CxBxrCrrelint {|(,)aff,0}CxBxrCCr1212,,[0,1],(1)xxCxxC则111,...,,[0,1]1,kkiiikiiixxCxC且则

凸集锥(Cones)  凸包的定义：包含集合C的最小的凸集。  锥的定义：  凸锥的定义：集合C既是凸集又是锥。  锥包的定义：集合C内点的所有锥组合。信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 13 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 超平面和半空间欧氏球和椭球  超平面(hyperplane) ：  欧氏球(euclidean ball):  半空间(Halfspace)：  椭球(ellipsoid): 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 15 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 范数球和范数锥多面体(Polyhedra)  范数(norm)：  多面体：  范数球(norm ball)：  范数锥(norm cone)：  单纯形(simplex)：信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 17 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 2012/9/24 14 16 18 3 11conv {|,0,1}kkiiiiiiiCxxC,0,.xCxC则有12121122,,,0,.xxCxxC则有1{|,0}kiiiiixxC{|}Txaxb{|}Txaxb{|}Txaxb22(,){|} {|()()}ccTccBxrxxxrxxxxxr12{|()()}, TccExxxPxxrP为对称正定矩阵2(,){|1}ccBxrxruu1/22{|1}, cExAuuAP0,00;||,xxxtxtxtxyxy当且仅当；R;(,){|}ccBxrxxxr{(,)|}xtxt{|,}TTjjiiPxaxbcxd10000{|0,1,,...,}kkiiiikiivvvvv线性无关

半正定锥(Positive semidefinite cone) 保持凸性的运算  n阶对称矩阵集：  集合交运算  仿射变换  n阶半正定矩阵集：  透视/投射函数(perspective function)  n阶正定矩阵集： n阶半正定矩阵集为凸锥！信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 19 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 保持凸性的运算真锥(proper cone)  线性分式函数(linear-fractional function)  真锥的定义：锥满足如下条件 K具有内点 K内不含直线信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 21 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 广义不等式广义不等式的性质  真锥下的偏序关系：广义不等式  例：  逐项不等式  矩阵不等式严格广义不等式信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 23 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 2012/9/24 20 22 24 4 {|}nnnTSXXXnR{|0}nnSXSX{|0}nnSXSX(,)/,,nPztztztRR(),,mnmfxAxbARbR()()/(),,,,0TmnmnTfxAxbcxdAbcdcxdRRRRnKR1.4.KKKK为凸集；2.为闭集；3.非中空；有端点。KKxyyxKintKxyyxK1.;2.,;3.,;4.,;5.,0;6.,lim,lim.KKKKKKKKKKKiKiiiKxxxyyxxyxyyzxzxyuvxuyvxyxyxyxxyyxy

2012/9/24 严格广义不等式的性质最值和极值  最小元的定义：设，对，都有成立，则称为的最小元。  极小元的定义：设，对于，若，则成立，则称为的极小元。信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 25 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 26 分割超平面(separating hyperplane) 支撑超平面(supporting hyperplane)  定理：设和为两不相交凸集，则存在超平面将  定义：设集合，为边界上的点。若存在，和分离。即：满足对任意面，都有成立，则称超平为集合在点处的支撑超平面。  定理：凸集边界上任意一点均存在支撑超平面。  定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 27 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 对偶锥(dual cone)  对偶锥的定义：设为锥，则集合对偶广义不等式  广义不等式与对偶等价性质称为对偶锥。  对偶锥的性质：真锥的对偶锥仍然是真锥！  最小元的对偶特性：信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 29 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 28 30 5 1.;2.;3.,;4.,05.,.KKKKKKKKKKxyxyxxxyuvxuyvxyxyxyuxuy足够小xSySKxyxSxSySKyxxSyx,,.TTxCaxbxDaxb且CDCDC0xC0axC0TTaxax0{|}TTxaxaxC0xK*{|0,}TKyxyxK*****1..3.KKKKKKK是闭凸集；2若非中空，则有端点；若的闭包有端点，则非中空；4.是的闭凸包；**,for all 0;,for all 0,0.TTKKTTKKxyxyxyxy*0, ,.TKxSKxzzS为集合中关于偏序的最小元对所有为使最小的值

2012/9/24 对偶广义不等式  极小元的对偶特性反过来不一定成立！作业  P60 2.8  P60 2.10  P60 2.14  P62 2.16  P62 2.18  P64 2.30  P64 2.31  P64 2.33 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 31 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 32 凸优化理论与应用第二章凸函数凸函数的定义  凸函数的定义：函数，满足 1.定义域为凸集； 2. ，有  凸函数的扩展定义：若为凸函数，则可定义其扩展函数为凸函数的扩展函数也是凸函 信息与通信工程学院庄伯金 33 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 数！ 34 凸函数的一阶微分条件凸函数的二阶微分条件  若函数的定义域为开集，且函数一阶可微，  若函数的定义域则函数为凸函数当且仅当为凸集，且对微，则函数为凸函数当且仅当对，其Hessian矩阵为开集，且函数二阶可为凸集，且信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 35 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 36 6 *0, ,.TKxzzSx为使最小的值为极小元dom f.((1))()(1)().fxyfxfy,dom ,01xyf.:nfnRR.f.:{}nfnRR.()dom()domfxxffxxf()()()()Tfyfxfxyxfffdomfdomf,domxyff2()0.fxffdomfdomfdomxf

2012/9/24 凸函数的例凸函数的例  指数函数  幂函数  负对数函数  负熵函数  范数函数信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 37 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 38 下水平集(sublevel set) 函数上半图(epigraph)  定义：集合称为的下水平集。  定理：凸函数的任一下水平集均为凸集。  任一下水平集均为凸集的函数不一定为凸函数。  定义：集合称为函数的上半图。  定理：函数为凸函数当且仅当的上半图为凸集。信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 39 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn Jensen不等式  为凸函数，则有：  Jensen不等式的另外形式：保持函数凸性的算子  凸函数的非负加权和  凸函数与仿射变换的复合  凸函数的逐点最大值信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 41 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 40 42 7 ,,1 or 0.axxaaRlogxlogxxpxaxe1()max(,...,)nfxxx2()/,0fxxyy1()log(...)nxxfxee1/1()(),domnnniifxxfR()log(det),domnfXXfS{dom|()}Cxffxfffepi{(,)|dom,()}fxtxffxtf1111(...)()...()nnnnfxxfxfxf101,...1.in其中(())()().SSfpxxdxpxfxdx1()max((),...,())nfxfxfx()()gxfAxb()sup(,)yfxgxyA11()()...()nnfxfxfx

2012/9/24 保持函数凸性的算子共轭函数(conjugate function)  复合运算  最小值算子  凸函数的透视算子  定义：设函数定义为  共轭函数的例，其共轭函数，共轭函数具有凸性！信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 43 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 44 共轭函数的性质准凸函数(quasiconvex function)  Fenchel’s inequality  定义：设函数，若函数的定义域和任意下水  性质：若为凸函数，且的上半图是闭集，则有  性质：设为凸函数，且可微，对于，若则平集则称函数为准凸函数。  准凸函数的例信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 45 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 准凸函数的判定定理保持准凸性的算子  定理：函数为准凸函数，当且仅当为凸集，  非负权值函数的最大值函数且对，有  定理：若函数一阶可微，则当为凸集，且对为准凸函数，当且仅，有  复合函数  定理：若函数二阶可微，且满足对  最小值函数，有则函数准凸函数。信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 47 信息与通信工程学院庄伯金 bjzhuang@bupt.edu.cn 46 48 8 :,:()(())nghfxhgxRRRRf()inf(,)yCgxfxy(,)(/)gxttfxt:nfRR*dom()sup(()).Txffyyxfx*:nfRR()Tfxaxb()xfxe()logfxxx*()().Tfxfyyx()fx()fx**.ff()fxnzR()yfz*()()()Tfyzfzfz{|(),dom}Sxfxxf:nfnRR()fx()fx((1))max{(),()}fxyfxfydomf,dom,01xyf()fx()fxdomf,domxyf()()()()0Tfyfxfxyx()fxdom,,0nxfyyR2()0()0TTyfxyfxy()fx

资料库

北邮庄伯金-凸优化理论与应用.pdf

相关推荐

课程资源

热门标签

最新资料