1、信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1 1凸优化理论与应用凸优化理论与应用庄 伯 金B信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2 2优化理论概述n什么是优化问题？什么是优化问题？0minimize ()subject to (),1,.,iinfxf xbimxR RObjective functionConstraint functions信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3 3几类经典的优化问题n线性规划问题线性规划问题()if x 为线性函数n最小二乘问题最小二乘问题202()-,0.fxAx bm n凸优化问题凸优化问题()if x 为凸函
2、数凸优化问题理论上有凸优化问题理论上有有效的方法进行求解！有效的方法进行求解！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4 4本课程的主要内容n理论部分理论部分n凸集和凸函数凸集和凸函数n凸优化问题凸优化问题n对偶问题对偶问题n应用部分应用部分n逼近与拟合逼近与拟合n统计估计统计估计n几何问题几何问题n算法部分算法部分n非约束优化方法非约束优化方法n等式约束优化方法等式约束优化方法n内点法内点法信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5 5n熟悉了解凸优化理论的基本原理和基本方法；熟悉了解凸优化理论的基本原理和基本方法；n掌握实际问题转化为凸优化问题的基本方法；掌握实际问
3、题转化为凸优化问题的基本方法；n掌握最优化问题的经典算法。掌握最优化问题的经典算法。课程要求信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6 6参考书目nStephen Boyd and Lieven Vandenberghe,“Convex Optimization”,Cambridge University Press.n袁亚湘、孙文瑜，袁亚湘、孙文瑜，“最优化理论与方法最优化理论与方法”，科学出版，科学出版社，社，1999。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7 7凸优化理论与应用凸优化理论与应用第一章第一章凸集凸集信息与通信工程学院信息与通信工程学院 庄伯金庄伯金
4、 8 8仿射集(Affine sets)n直线的表示：直线的表示：12(1),.yxxR.n线段的表示：线段的表示：12(1),0,1.yxx.信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9 9仿射集(Affine sets)n仿射集的定义：过集合仿射集的定义：过集合C内任意两点的直线均在集合内任意两点的直线均在集合C内，则称集合内，则称集合C为仿射集。为仿射集。n仿射集的例：直线、平面、超平面仿射集的例：直线、平面、超平面Axb信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1010仿射集n仿射包：包含集合仿射包：包含集合C的最小的仿射集。的最小的仿射集。aff|,1iiiiCx
5、xCn仿射维数：仿射包的维数。仿射维数：仿射包的维数。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1111仿射集n内点（内点（interior）：）：int|(,),0Cx B x rC rn相对内点（相对内点（relative interior）：）：relint|(,)aff,0Cx B x rCC r信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1212凸集(Convex Sets)n凸集的定义：集合凸集的定义：集合C内任意两点间的线段均在集合内任意两点间的线段均在集合C内，则称集合内，则称集合C为凸集。为凸集。1212,0,1,(1)x xCxxC则111,.,0,11,
6、kkiiikiiixxCxC且 则信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1313凸集n凸包的定义：包含集合凸包的定义：包含集合C的最小的凸集。的最小的凸集。11conv|,0,1kkiiiiiiiCxxC信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1414锥(Cones)n锥的定义：锥的定义：,0,.xCxC 则有n凸锥的定义：集合凸锥的定义：集合C既是凸集又是锥。既是凸集又是锥。12121 122,0,.x xCxxC 则有n锥包的定义：集合锥包的定义：集合C内点的所有锥组合。内点的所有锥组合。1|,0kiiiiixxC信息与通信工程学院信息与通信工程学院 庄伯金庄伯金
7、 1515超平面和半空间n超平面超平面(hyperplane)：|Tx a xbn半空间半空间(Halfspace)：|Tx a xb|Tx a xb信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1616欧氏球和椭球n欧氏球欧氏球(euclidean ball):22(,)|()()ccTccB x rxxxrxxxxxrn椭球椭球(ellipsoid):12|()(),TccExxxPxxrP为对称正定矩阵2(,)|1ccB x rxruu1/22|1,cExAuuAP信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1717范数球和范数锥n范数范数(norm)：0,00;|,xxx
8、txtx txyxy当且仅当；R;n范数球范数球(norm ball)：(,)|ccB x rxxxrn范数锥范数锥(norm cone)：(,)|x txt信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1818多面体(Polyhedra)n多面体：多面体：|,TTjjiiPx a xb c xdn单纯形单纯形(simplex)：10000|0,1,.,kki iiikiivvvvv线性无关信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 1919半正定锥(Positive semidefinite cone)nn阶对称矩阵集：阶对称矩阵集：|nn nTSXXXnRnn阶半正定矩阵集：
9、阶半正定矩阵集：|0nnSXSXnn阶正定矩阵集：阶正定矩阵集：|0nnSXSXn阶半正定矩阵集阶半正定矩阵集为凸锥！为凸锥！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2020保持凸性的运算n集合交运算集合交运算n仿射变换仿射变换n透视透视/投射函数投射函数(perspective function)(,)/,nP z tz t ztRR(),m nmf xAxb ARbR信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2121保持凸性的运算n线性分式函数线性分式函数(linear-fractional function)()()/(),0Tm nmnTf xAxbc xdAbc
10、dc xdRRRR信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2222真锥(proper cone)n真锥的定义：锥真锥的定义：锥 满足如下条件满足如下条件nKR1.4.KKKK为凸集；2.为闭集；3.非中空；有端点。K具有内点具有内点K内不含直线内不含直线信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2323广义不等式n真锥真锥 下的下的偏序关系偏序关系：KKxyyxK intKxyyxK n例：例：n逐项不等式逐项不等式n矩阵不等式矩阵不等式广义不等式广义不等式严格广义不等式严格广义不等式信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2424广义不等式的性质1.;2.,
11、;3.,;4.,;5.,0;6.,lim,lim.KKKKKKKKKKKiKiiiKxxxy yxxyxy yzxzxy uvxuyvxyxyxyxxyyxy信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2525严格广义不等式的性质1.;2.;3.,;4.,05.,.KKKKKKKKKKxyxyxxxy uvxuyvxyxyxy uxuy足够小信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2626最值和极值n最小元的定义：设最小元的定义：设 ，对，对 ，都有，都有 成立，则称成立，则称 为为 的最小元。的最小元。xSyS KxyxSn极小元的定义：设极小元的定义：设 ，对于，对于
12、，若，若 ，则，则 成立，则称成立，则称 为为 的极小元。的极小元。xSySKyxxSyx信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2727分割超平面(separating hyperplane)n定理：设定理：设 和和 为两不相交凸集，则存在超平面将为两不相交凸集，则存在超平面将 和和 分离。即：分离。即：,.TTxC a xbxD a xb 且CDCD信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2828支撑超平面(supporting hyperplane)n定义：设集合定义：设集合 ，为为 边界上的点。若存在边界上的点。若存在 ，满足对任意满足对任意 ，都有，都有 成立
13、，则称超平成立，则称超平面面 为集合为集合 在点在点 处的支撑超平面。处的支撑超平面。C0 xC0a xC0TTa xa x0|TTx a xa xC0 xn定理：凸集边界上任意一点均存在支撑超平面。定理：凸集边界上任意一点均存在支撑超平面。n定理：若一个闭的非中空集合，在边界上的任意一点定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。存在支撑超平面，则该集合为凸集。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 2929对偶锥(dual cone)n对偶锥的定义：设对偶锥的定义：设 为锥，则集合为锥，则集合 称为对偶锥。称为对偶锥。K*|0,TKy x yx
14、K n对偶锥的性质：对偶锥的性质：*1.3.KKKKKKK是闭凸集；2若 非中空，则有端点；若 的闭包有端点，则非中空；4.是 的闭凸包；真锥的对偶锥仍真锥的对偶锥仍然是真锥！然是真锥！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3030对偶广义不等式n广义不等式与对偶等价性质广义不等式与对偶等价性质*,for all 0;,for all 0,0.TTKKTTKKxyxyxyxyn最小元的对偶特性：最小元的对偶特性：*0,.TKxSKxz zS为集合 中关于 偏序的最小元对所有为使最小的值信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3131对偶广义不等式n极小元的对偶特性极小
15、元的对偶特性*0,.TKxz zSx为使最小的值为极小元反过来不一定成反过来不一定成立！立！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3232作业nP60 2.8nP60 2.10nP60 2.14nP62 2.16nP62 2.18nP64 2.30nP64 2.31nP64 2.33信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3333凸优化理论与应用凸优化理论与应用第二章第二章 凸函数凸函数信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3434凸函数的定义1.定义域定义域 为凸集；为凸集；dom f.(1)()(1)().fxyf xf y2.，有，有,dom,01
16、x yf.n凸函数的定义：函数凸函数的定义：函数 ，满足，满足:nfnRR.n凸函数的扩展定义：若凸函数的扩展定义：若 为凸函数，则可定义其扩为凸函数，则可定义其扩展函数展函数 为为f.:nfnRR.()dom()domf xxff xxf凸函数的凸函数的扩展函数扩展函数也是凸函也是凸函数！数！信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3535凸函数的一阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 一阶可微，一阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对()()()()Tf yf xf xyxfffdomfdomf,do
17、mx yf信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3636凸函数的二阶微分条件fn若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 二阶可二阶可微，则函数微，则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且为凸集，且对对 ，其，其Hessian矩阵矩阵2()0.f xffdomfdomfdomxf 信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3737凸函数的例n幂函数幂函数,1 or 0.axxaaRn负对数函数负对数函数log xn负熵函数负熵函数logxxn范数函数范数函数pxaxen指数函数指数函数信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3
18、838凸函数的例1()max(,.,)nf xxx2()/,0f xxy y1()log(.)nxxf xee1/1()(),domnnniif xxfR()log(det),domnf XXfS信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 3939下水平集(sublevel set)n定理：凸函数的任一下水平集均为凸集。定理：凸函数的任一下水平集均为凸集。n任一下水平集均为凸集的函数任一下水平集均为凸集的函数不一定不一定为凸函数。为凸函数。dom|()Cxff x称为称为 的的 下水平集。下水平集。fn定义：集合定义：集合信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4040函数
19、上半图(epigraph)n定理：函数定理：函数 为凸函数为凸函数当且仅当当且仅当 的上半图为凸集。的上半图为凸集。ffepi(,)|dom,()fx txf f xt称为函数称为函数 的上半图。的上半图。fn定义：集合定义：集合信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4141Jensen不等式n 为凸函数，则有：为凸函数，则有：1 111(.)().()nnnnfxxf xf xf101,.1.in其中nJensen不等式的另外形式：不等式的另外形式：()()().SSfp x xdxp x f x dx信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4242保持函数凸性的算
20、子n凸函数的逐点最大值凸函数的逐点最大值1()max(),.,()nf xf xfxn凸函数与仿射变换的复合凸函数与仿射变换的复合()()g xf Axb()sup(,)yf xg x yA1 1()().()nnf xf xfxn凸函数的非负加权和凸函数的非负加权和信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4343保持函数凸性的算子n复合运算复合运算:,:()()nghf xh g xRRRRfn最小值算子最小值算子()inf(,)y Cg xf x yn凸函数的透视算子凸函数的透视算子(,)(/)g x ttf x t信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4444共
21、轭函数(conjugate function)n定义：设函数定义：设函数 ，其共轭函数，其共轭函数 ，定义为定义为:nfRR*dom()sup().Txffyy xf x*:nfRRn共轭函数的例共轭函数的例共轭函数共轭函数具有凸性！具有凸性！()Tf xa xb()xf xe()logf xxx信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4545共轭函数的性质nFenchels inequality*()().Tf xfyy xn性质：若性质：若 为凸函数，且为凸函数，且 的上半图是闭集，则有的上半图是闭集，则有()f x()f x*.ffn性质：设性质：设 为凸函数，且可微，对于为
22、凸函数，且可微，对于 ，若，若()f xnzR()yf z 则则*()()()Tfyzf zf z信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4646准凸函数(quasiconvex function)n准凸函数的例准凸函数的例n定义：设函数定义：设函数 ，若函数的定义域和任意下，若函数的定义域和任意下水平集水平集|(),dom Sx f xxf:nfnRR则称函数则称函数 为准凸函数。为准凸函数。()f x信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4747准凸函数的判定定理n定理：函数定理：函数 为准凸函数，当且仅当为准凸函数，当且仅当 为凸集，为凸集，且对且对 ，有，有(
23、)f x(1)max(),()fxyf xf ydomf,dom,01x yfn定理：若函数定理：若函数 一阶可微，则一阶可微，则 为准凸函数，当且仅为准凸函数，当且仅当当 为凸集，且对为凸集，且对 ，有，有()f x()f xdomf,domx yf()()()()0Tf yf xf xyx ，有，有n定理：若函数定理：若函数 二阶可微，且满足对二阶可微，且满足对()f xdom,0nxf yy R2()0()0TTyf xyf x y则函数则函数 准凸函数。准凸函数。()f x信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4848n最小值函数最小值函数n非负权值函数的最大值函数非负权
24、值函数的最大值函数保持准凸性的算子n复合函数复合函数信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 4949准凸函数的凸函数族表示n若若 为准凸函数，根据为准凸函数，根据 的任意的任意 下水平集，我们下水平集，我们可以构造一个凸函数族可以构造一个凸函数族 ，使得，使得()f x()f xt()tx()()0tf xtx n性质：若性质：若 为准凸函数为准凸函数 的凸函数族表示，对每一的凸函数族表示，对每一个个 ，若，若 ，则有，则有()().stxx()f x()txdomxfst信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5050对数凸函数 为凸集为凸集为凸函数。为凸函数。n定义
25、：函数定义：函数 称为对数凸函数，若函数称为对数凸函数，若函数 满足：满足：2.()0f x()f x()f x3.log()f x1.domfn定理：函数定理：函数 的定义域为凸集，且的定义域为凸集，且 ，则，则 为为对数凸函数，当且仅当对对数凸函数，当且仅当对()f x()0f x()f x,dom,01x yf 有有1(1)()()fxyf xf yn对数凸函数的例对数凸函数的例信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5151对数凸函数和凹函数的性质n性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。闭。n定理：函数定
26、理：函数 二阶可微，则二阶可微，则 为对数凸函数当且仅为对数凸函数当且仅当当2()()()()Tf xf xf xf x()f x()f xn性质：对数凸性对函数加运算保持封闭。但对数凹性对函数性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。加运算不封闭。n推论：函数推论：函数 对每一个对每一个 在在 上对数凸，则函上对数凸，则函数数 也是对数凸函数。也是对数凸函数。(,)f x yyCx()(,)Cg xf x y dy信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5252对数凸函数和凹函数的性质n定理：函数定理：函数 为对数凹函数，则函为对数凹函数，则函数数 是对数
27、凹函数。是对数凹函数。(,):nmf x yRRR()(,)g xf x y dy信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5353广义不等式下的凸性n广义单调性的定义：设广义单调性的定义：设 为真锥，函数为真锥，函数 称为称为 单调增，若函数单调增，若函数 满足：满足：nK R:nfRRK()f x()()Kxyf xf yn广义凸函数的定义：设广义凸函数的定义：设 为真锥，函数为真锥，函数 称为称为 凸，若函数凸，若函数 满足对满足对mK R:nmfRRK()f x,dom,01x yf(1)()(1)().Kfxyf xf y 均有均有n定理定理(对偶等价对偶等价)：函数函数
28、为为 凸函数，当且仅当对所凸函数，当且仅当对所有有 ，为凸函数。为凸函数。()f xK*0Kw()Tw f x信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5454作业(1)nP116 3.16nP116 3.21信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5555作业(2)nP121 3.41nP122 3.49 (1)(2)信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5656凸优化理论与应用凸优化理论与应用第三章第三章 凸优化凸优化信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5757优化问题的基本形式n优化问题的基本描述：优化问题的基本描述：0minimize
29、 (),subject to ()0,1,.,()0,1,.,niifxxf ximh xjpR R优化变量优化变量nxR()0if x 不等式约束不等式约束等式约束等式约束()0ih x.0mp无约束优化无约束优化信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5858优化问题的基本形式最优化值最优化值*0inf()|()0,1,.,()0,1,.,iipfxf xim h xip*0()pfx最优化解最优化解 优化问题的域优化问题的域01domdompmiiiiDfh 可行点可行点(解解)(feasible)满足约束条件满足约束条件xD 可行域可行域(可解集可解集)所有可行点的集合所有
30、可行点的集合信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 5959局部最优问题n局部最优问题局部最优问题02minimize (),subject to ()0,1,.,()0,1,.,0niifxxf ximh xjpxzR RR R信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6060优化问题的等价形式(1)n定理：若定理：若000minimize ()(),subject to ()()0,1,.,()()0,1,.,niiiiifxfxxf xf ximh xh xipR R0,0,.,0,1,.,iiimip 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价信
31、息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6161优化问题的等价形式(2)n定理：设定理：设 为一一对应，且为一一对应，且00minimize ()(),subject to ()()0,1,.,()()0,1,.,niiiifzfzzf zfzimh zhzipR R:nnRR 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价(dom)D信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6262优化问题的等价形式(3)n定理：设定理：设 为严格单调增函数；为严格单调增函数；满满足足 当且仅当当且仅当 ；满足满足 当当且仅当且仅当 。则原优化问题与以下优化问题等价。则原优
32、化问题与以下优化问题等价000minimize ()(),subject to ()()0,1,.,()()0,i1,.,niiiiiifzfzzf zf zimh zh zpR R0:RR1,.,m()0iu0u 1,.,p()0iu0u 信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6363优化问题的等价形式(4)n定理：原优化问题与以下优化问题等价定理：原优化问题与以下优化问题等价0minimize (),subject to ()0,1,.,0 ()0,1,.,niiiifxxf xsimsh xjpR Rn 称为松弛变量称为松弛变量s信息与通信工程学院信息与通信工程学院 庄伯金
33、庄伯金 6464优化问题的等价形式(5)n定理：设定理：设 满足等式满足等式 成立，当且仅当成立，当且仅当 。则原优化问题与以下优化。则原优化问题与以下优化问题等价问题等价0minimize (),subject to ()0,1,.,nifzxfzimR R:knRR()0,1,.,ih xjp()xz信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6565可分离变量优化问题n性质：性质：,inf(,)inf()x yxf x yf x其中其中()inf(,)yf xf x y可以分离变量可以分离变量n定理：优化问题定理：优化问题0121122minimize (,),subject t
34、o ()0,1,.,()0,1,.,niifx xxf ximf ximR R12,x x信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6666优化问题的上半图形式0minimize subject to ()0,()0,1,.,()0,1,.,iitfxtf ximh xjp 信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6767凸优化问题的基本形式n凸优化问题的基本描述：凸优化问题的基本描述：0minimize (),subject to ()0,1,.,()0,1,.,niifxxf ximh xjpR R 为仿射函数为仿射函数()ih x 为凸函数为凸函数()if x 若若
35、 为准凸函数，则优化问题称为准凸优化问题。为准凸函数，则优化问题称为准凸优化问题。0()fx 性质：凸优化问题的可行域是凸集。性质：凸优化问题的可行域是凸集。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6868凸优化问题的例n例：例：2201221122112minimize ()subject to ()/(1)0 ()()0fxxxf xxxh xxx等价于凸优化问题等价于凸优化问题2201211112minimize ()subject to ()0 ()0fxxxf xxh xxx信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 6969凸优化问题的局部最优解n定理：凸优化问
36、题的局部最优解均是全局最优解。定理：凸优化问题的局部最优解均是全局最优解。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7070凸优化问题最优解的微分条件n定理：设定理：设 为凸优化问题的可行域，为凸优化问题的可行域，可微。则可微。则 为最优解当且仅当为最优解当且仅当 成立。成立。0()fx0()()0,TfxyxyXXxn定理：非约束凸优化问题中，若定理：非约束凸优化问题中，若 可微。则可微。则 为最为最优解当且仅当优解当且仅当 成立。成立。0()fxx0()0fx信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7171凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，
37、且存在向量，且存在向量 满足满足 n定理：设凸优化问题仅有等式约束定理：设凸优化问题仅有等式约束x0()0TfxA v0minimize (),subject to nfxxAxbR RxXv信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7272凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且，且 n定理：设凸优化问题定理：设凸优化问题x0()0Tfxx0minimize (),subject to 0nfxxxR RxX信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7373凸优化问题的等价形式0minimize (),subject to ()0,1,.,niTf
38、xxf ximA xbR R等价于等价于 n定理：设凸优化问题定理：设凸优化问题000minimize (),subject to ()0,1,.,nifFzxxf FzximR R其中其中 0 TA xbxFzx信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7474凸优化问题的等价形式0minimize (),subject to ,1,.,nTiifxxa xbimR R等价于等价于 n定理：设凸优化问题定理：设凸优化问题0minimize (),subject to ,1,.,0,1,.,nTiiiifxxa xsbimsimR R信息与通信工程学院信息与通信工程学院 庄伯金庄伯金
39、 7575准凸优化问题 为准凸函数，为准凸函数，为凸函数。为凸函数。1(),.,()mf xfxn准凸优化问题的基本描述准凸优化问题的基本描述0()fx0minimize (),subject to ()0,1,.,()0,1,.,niifxxf ximh xjpR Rn注：准凸优化问题的局部最优解不一定是全局最优解。注：准凸优化问题的局部最优解不一定是全局最优解。信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7676准凸优化问题的上半图形式n设设 为准凸函数为准凸函数 的凸函数族表示，即的凸函数族表示，即0()fx()tx0()()0tfxtx 则准凸优化问题的可行解问题为则准凸优化问
40、题的可行解问题为find subject to ()0,()0,1,.,tixxf ximAxbn设设 为准凸优化问题的最优解，若上述问题可解，为准凸优化问题的最优解，若上述问题可解，则则 。否则。否则 。*p*pt*pt信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7777准凸优化问题二分法求解n给定一个足够小的给定一个足够小的 和足够大的和足够大的 ，使得区间，使得区间 能包含最优解能包含最优解 。给定。给定ul*p,l u0nLOOP：n令令n求解可行解问题；求解可行解问题；n若可解，则令若可解，则令 ，否则令，否则令n若若 ，则结束，否则，则结束，否则goto LOOP。()/2
41、tluutltul信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7878线性规划(linear program,LP)nLP问题的一般描述问题的一般描述minimize subject to Tc xdGxhAxb,m np nGARR信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 7979LP问题的几种类型n标准标准LP问题问题minimize subject to 0Tc xAxbxn不等式形式不等式形式LP问题问题minimize subject to Tc xdAxb信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8080标准LP问题的转换minimize subject
42、 to 0,0,0TTc xc xbGxGxshAxAxbxxs信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8181LP问题的例nChebyshev center of a polyhedronnPiecewise-linear minimizationnLinear-fractional programming信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8282Chebyshev center of a polyhedron|nPxRAxbn多面体nChebyshev center：到多面体边界距离最大的内点（最深的点）2(,)|ccB x rxuurn问题描述maximiz
43、e subject to (,)crB x rPnLP形式2minimize 1/subject to ,1,.,Ticiira xr ab im信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8383Piecewise-linear minimizationn问题描述1,.,minimize ()max()Tiiimf xa xbn上半图形式1,.,minimize subject to max()Tiiimta xbtnLP形式minimize subject to ,1,.,Tiita xbt im信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8484Linear-fracti
44、onal programmingn问题描述00minimize (),dom|0subject to TTTc xdfxfx e xfe xfGxhAxbnLP形式minimize subject to 0 0 1 0TTc ydzGyhzAybze yfzz1TTxye xfze xf信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8585二次规划(quadratic program,QP)minimize (1/2)subject to ,TTnm np nx Pxq xrGxhAxbPSGRARnQP问题的基本描述问题的基本描述信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 86
45、86二次约束二次规划000minimize (1/2)subject to (1/2)0 ,TTTTiiinp nix P xq xrx Pxq xrAxbPSARnquadratically constrained quadratic program(QCQP)信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8787QP问题的例nLeast-squares and regressionnDistance between polyhedra信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8888Least-squares and regressionn问题描述22minimize Ax
46、b222TTTTAxbx A Axb Axb b信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 8989Distance between polyhedran问题描述12121122dist(,)inf|,P PxxxP xP111|Px A xb222|Px A xbnQP形式21221122minimize subject to ,xxAxb A xb信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9090Second-order cone program,SOCPnSOCP问题的基本描述2minimize subject to TTiiif xAxbc xdFxgn二次锥约束条件
47、2TAxbc xd信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9191SOCP问题的例Robust linear programmingn问题描述minimize subject to TTiic xa xb其中 不是完全确定的常数。,iic a bn例：为确定的常数，为变量，其范围满足,ic bia2|1iiiiaaPuuSOCP形式2minimize subject to TTTiiic xa xP xb信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9292几何规划(Geometric programming)n单项式与多项式11()naanf xcxx111()knkKaa
48、knkf xc xxn几何规划的基本描述0minimize ()subject to ()1,1,.,()1,1,.,iiniifxf ximh xipfhDR为多项式，为单项式,信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9393几何规划的凸形式转换n令logiiyxn几何规划的凸形式000011minimize ()log()subject to ()log()0,1,.,()0,1,.,TkkTiikikKay bkKa y bikTiiifyef yeimh yg yhip信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9494广义不等式约束n广义不等式约束的优化问题0mi
49、nimize ()subject to ()0,1,.,iiKfxf ximAxbnSOCP的描述12minimize subject to (,)0,1,.,(,)|iiTTiiiiKkic xAxb c xdimFxgKy tRyt信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9595凸优化理论与应用凸优化理论与应用第四章第四章 对偶问题对偶问题信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9696优化问题的拉格朗日函数n设优化问题：设优化问题：0minimize (),subject to ()0,1,.,()0,1,.,niifxxf ximh xjpR Rn拉格朗日拉格朗
50、日(Lagrangian)函数：函数：011(,)()()()pmiiiiiiL xfxf xh x n对固定的对固定的 ，拉格朗日函数，拉格朗日函数 为关于为关于 和和 的的仿仿射函数射函数。(,)L x x信息与通信工程学院信息与通信工程学院 庄伯金庄伯金 9797拉格朗日对偶函数n拉格朗日对偶函数拉格朗日对偶函数(lagrange dual function)：011(,)inf(,)inf()()()pmiiiix Dx DiigL xfxf xh x 若拉格朗日函数没有下界，则令若拉格朗日函数没有下界，则令(,)g n拉格朗日对偶函数为拉格朗日对偶函数为凹函数凹函数。n对对 和和 ，
