凸优化理论与应用凸函数课件.pptx

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

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

3、(,.,)nf xxx2()/,0f xxy y1()log(.)nxxf xee1/1()(),domnnniif xxfR()log(det),domnf XXfS6 6下水平集(sublevel set)n定理：凸函数的任一下水平集均为凸集。定理：凸函数的任一下水平集均为凸集。n任一下水平集均为凸集的函数任一下水平集均为凸集的函数不一定不一定为凸函数。为凸函数。dom|()Cxff x称为称为 的的 下水平集。下水平集。fn定义：集合定义：集合7 7函数上半图(epigraph)n定理：函数定理：函数 为凸函数为凸函数当且仅当当且仅当 的上半图为凸集。的上半图为凸集。ffepi(,)|d

4、om,()fx txf f xt称为函数称为函数 的上半图。的上半图。fn定义：集合定义：集合8 8Jensen不等式n 为凸函数，则有：为凸函数，则有：1 111(.)().()nnnnfxxf xf xf101,.1.in其中nJensen不等式的另外形式：不等式的另外形式：()()().SSfp x xdxp x f x dx9 9保持函数凸性的算子n凸函数的逐点最大值凸函数的逐点最大值1()max(),.,()nf xf xfxn凸函数与仿射变换的复合凸函数与仿射变换的复合()()g xf Axb()sup(,)yf xg x yA1 1()().()nnf xf xfxn凸函数的非负

5、加权和凸函数的非负加权和1010保持函数凸性的算子n复合运算复合运算:,:()()nghf xh g xRRRRfn最小值算子最小值算子()inf(,)y Cg xf x yn凸函数的透视算子凸函数的透视算子(,)(/)g x ttf x t1111共轭函数(conjugate function)n定义：设函数定义：设函数 ，其共轭函数，其共轭函数 ，定义为定义为:nfRR*dom()sup().Txffyy xf x*:nfRRn共轭函数的例共轭函数的例共轭函数共轭函数具有凸性！具有凸性！()Tf xa xb()xf xe()logf xxx1212共轭函数的性质nFenchels ineq

6、uality*()().Tf xfyy xn性质：若性质：若 为凸函数，且为凸函数，且 的上半图是闭集，则有的上半图是闭集，则有()f x()f x*.ffn性质：设性质：设 为凸函数，且可微，对于为凸函数，且可微，对于 ，若，若()f xnzR()yf z 则则*()()()Tfyzf zf z1313准凸函数(quasiconvex function)n准凸函数的例准凸函数的例n定义：设函数定义：设函数 ，若函数的定义域和任意下，若函数的定义域和任意下水平集水平集|(),dom Sx f xxf:nfnRR则称函数则称函数 为准凸函数。为准凸函数。()f x1414准凸函数的判定定理n定理

7、：函数定理：函数 为准凸函数，当且仅当为准凸函数，当且仅当 为凸集，为凸集，且对且对 ，有，有()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 x1515n最小值函

8、数最小值函数n非负权值函数的最大值函数非负权值函数的最大值函数保持准凸性的算子n复合函数复合函数1616准凸函数的凸函数族表示n若若 为准凸函数，根据为准凸函数，根据 的任意的任意 下水平集，我们下水平集，我们可以构造一个凸函数族可以构造一个凸函数族 ，使得，使得()f x()f xt()tx()()0tf xtx n性质：若性质：若 为准凸函数为准凸函数 的凸函数族表示，对每一的凸函数族表示，对每一个个 ，若，若 ，则有，则有()().stxx()f x()txdomxfst1717对数凸函数 为凸集为凸集为凸函数。为凸函数。n定义：函数定义：函数 称为对数凸函数，若函数称为对数凸函数，若函

9、数 满足：满足：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对数凸函数的例对数凸函数的例1818对数凸函数和凹函数的性质n性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。闭。n定理：函数定理：函数 二阶可微，则二阶可微，则 为对数凸函数当且仅为对数凸函数当且仅当当2()()()()Tf xf xf

10、xf x()f x()f xn性质：对数凸性对函数加运算保持封闭。但对数凹性对函数性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。加运算不封闭。n推论：函数推论：函数 对每一个对每一个 在在 上对数凸，则函上对数凸，则函数数 也是对数凸函数。也是对数凸函数。(,)f x yyCx()(,)Cg xf x y dy1919对数凸函数和凹函数的性质n定理：函数定理：函数 为对数凹函数，则函为对数凹函数，则函数数 是对数凹函数。是对数凹函数。(,):nmf x yRRR()(,)g xf x y dy2020广义不等式下的凸性n广义单调性的定义：设广义单调性的定义：设 为真锥，函数

11、为真锥，函数 称为称为 单调增，若函数单调增，若函数 满足：满足：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 x2121作业(1)nP116 3.16nP116 3.212222作业(2)nP121 3.41nP122 3.49 (1)(2)2323