凸优化理论与应用-凸函数PPT课件.ppt

1、可编辑可编辑1 1凸优化理论与应用凸优化理论与应用第二章第二章 凸函数凸函数可编辑可编辑2 2凸函数的定义1.定义域定义域 为凸集；为凸集；dom f.(1) )( )(1) ( ).fxyf xf y2. ，有，有,dom ,01x yf.n凸函数的定义：函数凸函数的定义：函数 ，满足，满足:nfnRR .n凸函数的扩展定义：若凸函数的扩展定义：若 为凸函数，则可定义其扩为凸函数，则可定义其扩展函数展函数 为为f.: nfnRR .( )dom( )domf xxff xxf凸函数的凸函数的扩展函数扩展函数也是凸函也是凸函数！数！可编辑可编辑3 3凸函数的一阶微分条件n若函数若函数 的定义域

2、的定义域 为开集，且函数为开集，且函数 一阶可微，一阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对( )( )( ) ()Tf yf xf xyxfffdomfdomf,domx yf可编辑可编辑4 4凸函数的二阶微分条件fn若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 二阶可二阶可微，则函数微，则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且为凸集，且对对 ，其，其Hessian矩阵矩阵2( )0.f xffdomfdomfdomxf 可编辑可编辑5 5凸函数的例n幂函数幂函数,1 or 0.axxaaRn负对数函数负对数函数log xn

3、负熵函数负熵函数logxxn范数函数范数函数pxaxen指数函数指数函数可编辑可编辑6 6凸函数的例1( )max( ,.,)nf xxx2( , )/ ,0f x yxy y1( )log(.)nxxf xee1/1( )(),domnnniif xxfR()log(det),domnf XXfS 可编辑可编辑7 7下水平集(sublevel set)n定理：凸函数的任一下水平集均为凸集。定理：凸函数的任一下水平集均为凸集。n任一下水平集均为凸集的函数任一下水平集均为凸集的函数不一定不一定为凸函数。为凸函数。dom |( )Cxff x称为称为 的的 下水平集。下水平集。fn定义：集合定义：

4、集合可编辑可编辑8 8函数上半图(epigraph)n定理：函数定理：函数 为凸函数为凸函数当且仅当当且仅当 的上半图为凸集。的上半图为凸集。ffepi( , )|dom ,( )fx txf f xt称为函数称为函数 的上半图。的上半图。fn定义：集合定义：集合可编辑可编辑9 9Jensen不等式n 为凸函数，则有：为凸函数，则有：1 111(.)().()nnnnfxxf xf xf101,.1.in其中nJensen不等式的另外形式：不等式的另外形式：( )( ) ( ).SSfp x xdxp x f x dx可编辑可编辑1010保持函数凸性的算子n凸函数的逐点最大值凸函数的逐点最大值

5、1( )max( ),.,( )nf xf xfxn凸函数与仿射变换的复合凸函数与仿射变换的复合( )()g xf Axb1 1( )( ).( )nnf xf xfxn凸函数的非负加权和凸函数的非负加权和( )sup ( , )yf xg x yA对固定对固定 ， 为凸函数。为凸函数。( , )g x yy逐点最大值函数变换的例n向量中向量中 个最大分量之和：个最大分量之和：n对称矩阵的最大特征值对称矩阵的最大特征值可编辑可编辑1111r121( ),.rinif xx xxx121.1( )maxkrriiiinkf xx2()sup|1Tf Xy Xyy可编辑可编辑1212保持函数凸性的

6、算子n复合运算复合运算:, :( )( ( )nghf xh g xRRRRfn凸函数的透视算子凸函数的透视算子( , )(/ )g x ttf x tn最小值算子最小值算子( )inf( , )y Cg xf x y( , )f x y 为凸函数。为凸函数。可编辑可编辑1313共轭函数(conjugate function)n定义：设函数定义：设函数 ，其共轭函数，其共轭函数 ，定义为定义为:nfRR*dom( )sup ( ).Txffyy xf x*:nfRRn共轭函数的例共轭函数的例共轭函数共轭函数具有凸性！具有凸性！( )Tf xa xb( )xf xe( )logf xxx可编辑可

7、编辑1414共轭函数的性质nFenchels inequality*( )( ).Tf xfyy xn性质：若性质：若 为凸函数，且为凸函数，且 的上半图是闭集，则有的上半图是闭集，则有( )f x( )f x*.ffn性质：设性质：设 为凸函数，且可微，对于为凸函数，且可微，对于 ，若，若( )f xnzR( )yf z 则则*( )( )( )Tfyzf zf z可编辑可编辑1515准凸函数(quasiconvex function)n准凸函数的例准凸函数的例n定义：设函数定义：设函数 ，若函数的定义域和任意下，若函数的定义域和任意下水平集水平集 |( ),dom Sx f xxf:nfn

8、RR为凸集，则称函数为凸集，则称函数 为准凸函数。为准凸函数。( )f x( )log ,0f xx x( )( )inf |f xceil xz zZzx( )max |0,nif xi xxR可编辑可编辑1616准凸函数的判定定理n定理：函数定理：函数 为准凸函数，当且仅当为准凸函数，当且仅当 为凸集，为凸集，且对且对 ，有，有( )f x(1) )max ( ),( )fxyf xf ydomf,dom ,01x yf准凸函数的判定定理可编辑可编辑1717n定理：若函数定理：若函数 一阶可微，则一阶可微，则 为准凸函数，当且仅为准凸函数，当且仅当当 为凸集，且对为凸集，且对 ，有，有 (

9、 )f x( )f xdomf,domx yf( )( )( )()0Tf yf xf xyx 准凸函数的判定定理可编辑可编辑1818 ，有，有n定理：若函数定理：若函数 二阶可微，且满足对二阶可微，且满足对( )f xdom ,0nxf yy R2( )0( )0TTyf xyf x y则函数则函数 准凸函数。准凸函数。( )f x可编辑可编辑1919n最小值函数最小值函数n非负权值函数的最大值函数非负权值函数的最大值函数保持准凸性的算子n复合函数复合函数1 1max,.,mmffffh ginf( , )y Cgf x y 是关于是关于 和和 的准凸函数，且的准凸函数，且 为凸集。为凸集。

10、( , )f x yxyC可编辑可编辑2020准凸函数的凸函数族表示n若若 为准凸函数，根据为准凸函数，根据 的任意的任意 下水平集，我们下水平集，我们可以构造一个凸函数族可以构造一个凸函数族 ，使得，使得( )f x( )f xt( )tx( )( )0tf xtx n性质：若性质：若 为准凸函数为准凸函数 的凸函数族表示，对每一的凸函数族表示，对每一个个 ，若，若 ，则有，则有( )( ).stxx( )f x( )txdomxfstn例：例：0( )( ).tf xtxotherwise可编辑可编辑2121对数凸函数 为凸集为凸集为凸函数。为凸函数。n定义：函数定义：函数 称为对数凸函数

11、，若函数称为对数凸函数，若函数 满足：满足：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对数凸函数的例对数凸函数的例可编辑可编辑2222对数凸函数和凹函数的性质n性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。闭。n定理：函数定理：函数 二阶可微，则二阶可微，则 为对数

12、凸函数当且仅为对数凸函数当且仅当当2( )( )( )( )Tf xf xf xf x( )f x( )f xn性质：对数凸性对函数加运算保持封闭。但对数凹性对函数性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。加运算不封闭。n推论：函数推论：函数 对每一个对每一个 在在 上对数凸，则函上对数凸，则函数数 也是对数凸函数。也是对数凸函数。( , )f x yyCx( )( , )Cg xf x y dy可编辑可编辑2323对数凸函数和凹函数的性质n定理：函数定理：函数 为对数凹函数，则函为对数凹函数，则函数数 是对数凹函数。是对数凹函数。( , ):nmf x yRRR( )

13、( , )g xf x y dy可编辑可编辑2424广义不等式下的凸性n广义单调性的定义：设广义单调性的定义：设 为真锥，函数为真锥，函数 称为称为 单调增，若函数单调增，若函数 满足：满足：nK R:nfRRK ( )f x( )( )Kxyf xf yn广义凸函数的定义：设广义凸函数的定义：设 为真锥，函数为真锥，函数 称为称为 凸，若函数凸，若函数 满足对满足对mK R:nmfRRK ( )f x,dom ,01x yf(1) )( )(1) ( ).Kfxyf xf y 均有均有n定理定理(对偶等价对偶等价)：函数函数 为为 凸函数，当且仅当对所凸函数，当且仅当对所有有 ， 为凸函数。为凸函数。( )f xK *0Kw( )Tw f x可编辑可编辑2525作业nP116 3.16nP116 3.21nP121 3.41nP122 3.49 (1)(2)