第讲凸集、凸函数、凸规划

第3讲凸集、凸函数、凸规划•凸集(ConvexSet)•凸函数(ConvexFunction)•凸规划(ConvexProgramming)凸性(Convexity)是最优化理论必须涉及到基本概念.具有凸性的非线性规划模型是一类特殊的重要模型，它在最优化的理论证明及算法研究中具有非常重要的作用.凸集---定义.1,,...2,1,,,11miiniimiiimiRxRx且其中.,...2,1,,,1miRxRxniimiii其中线性组合(linearCombination).,...2,1,,,1miRxRxniimiii其中仿射组合(AffineCombination).1,...2,1,,,m1ii1且其中miRxRxniimiii凸组合(ConvexCombination)凸锥组合(ConvexConeCombination)凸集---定义例二维情况下，两点x1,x2的(a)线性组合为全平面；(b)仿射组合为过这两点的直线；(c)凸组合为连接这两点的线段；(b)凸锥组合为以原点为锥顶并通过这两点的锥.凸集---定义凸集---定义定义1设集合,nRD若对于任意两点,,Dyx及实数,10都有：,1Dyx则称集合D为凸集．常见的凸集：单点集{x}，空集，整个欧氏空间Rn，超平面：,2211bxaxaxaRxHnnn半空间：1122=nnnnTHxRaxaxaxbxRaxb例：证明超球rx为凸集．证明：设为超球中的任意两点，yx,,10则有：yx1yx1,1rrr即点yx1属于超球,所以超球为凸集．凸集----举例(1)任意多个凸集的交集为凸集．(2)设D是凸集，是一实数，则下面的集合是凸集：DxxyyD,凸集-----性质(3).,|)b(;,|)a(221121212211212121是凸集是凸集上的凸集，则是和设DxDxxxDDDxDxxxDDRDDn推论：kiiiD1设kiDi,,2,1,是凸集，则也是凸集，其中i是实数．(4)S是凸集当且仅当S中任意有限个点的凸组合仍然在S中.凸集-----性质注：和集和并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集．例：RxxDT0,1表示x轴上的点．RyyDT,02表示y轴上的点．则21DD表示两个轴的所有点，它不是凸集；221RDD而凸集．凸集-----性质定义设S中任意有限个点的所有凸组合所构成的集合称为S的凸包，记为H(S),即,nRS凸集-----凸包(ConvexHull)miiiimiiiNmmiSxxSH11,1,...,2,1,0,)(定理2.1.4H(S)是Rn中所有包含S的凸集的交集.H(S)是包含S的最小凸集.定义锥、凸锥.SS.xS,Sxx,0Sx,000为凸锥则称又是凸集，如果为顶点的锥以是则称有及，如果对一切设SxRSn凸集-----凸锥(ConvexCone)凸函数凸函数(ConvexFunction)----定义2.4设,:RSxf是非空凸集，nRD若对任意的,,Dyx及任意的1,0都有：yfxfyxf11则称函数xf为D上的凸函数．注：将上述定义中的不等式反向，可以得到凹函数的定义．凸函数严格凸函数设,:RSxf是非空凸集，nRD若对任意的,(),xyDxy及任意的0,1都有：11fxyfxfy则称函数xf为D上的严格凸函数．注：将上述定义中的不等式反向，可以得到严格凹函数的定义．凸函数对一元函数,xf在几何上211xfxf10表示连接2211,,,xfxxfx的线段．所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方．几何性质211xxf表示在点211xx处的函数值．f(X)Xf(X1)f(X2)X1X2f(X)Xf(X1)f(X2)X1X2αx1+(1-α)x2f(αx1+(1-α)x2)f(X)Xf(X1)f(X2)X1X2αx1+(1-α)x2f(αx1+(1-α)x2)f(X)Xαf(x1)+(1-α)f(x2)f(X1)f(X2)X1X2αx1+(1-α)x2f(αx1+(1-α)x2)f(X)Xf(X1)f(X2)X1X2任意两点的函数值的连线上的点都在曲线的上方αx1+(1-α)x2f(αx1+(1-α)x2)αf(x1)+(1-α)f(x2)例4.2.1(a)凸函数(b)凹函数该定义的一个应用——证明不等式例：证明11,pqxyxypq11,0,,0,1.pqxypq其中()lnftt凹pqxxxypqYoung不等式11111pqnnnpqkkkkkkkxyxy推广：Hölder不等式P412.37证法：在Young不等式中令1:nppikkxxx1:nqqikkyyy例：设,12xxf试证明xf在,上是严格凸函数．证明:设,,Ryx且1,0,yx都有：yfxfyxf1122211111yxyx012yx因此,xf在,上是严格凸函数．凸函数例：试证线性函数是nnTxcxcxcxcxf2211nR上的凸函数．证明:设,1,0,,Ryx则yxcyxfT11yfxfycxcTT11故,xcT是凸函数．类似可以证明Tcx也是凹函数.凸函数凸函数定理1设xf是凸集nRD上的凸函数充要条件121ii11,,...,,0(1,2,...,),1,fxf(x).kkiiikkiiiixxxDik则性质詹生(Jensen)不等式0ix不等式应用:设，证明:1112(1),ppppnnxxxxxpnn1112(1),ppppnnxxxxxpnnP412.36凸函数定理2.)(max(x)),...,2,1(0),(xf(x),,...,,ki11i21上的凸函数都是和则上的凸函数是凸集SxfkiSfffiikiik性质正线性组合凸函数定理3设xf是凸集nRS上的凸函数，R则对任意，水平集,fS是凸集．水平集(LevelSet).:,},)(|{,RSfRSxfSxfSn其中称为函数f在集合S上关于数的水平集.注：定理3的逆命题不成立.下面的图形给出了凸函数xyy24243,yxxyxf的等值线的图形，可以看出水平集是凸集.凸函数凸函数定理1:设xf是定义在凸集nRD上，,,Dyx令,1,0,1tyttxft则:(1)xf是定义在凸集是凸集D上的凸函数的充要条件是对任意的,,Dyx一元函数t为1,0上的凸函数.(2)设,,,yxDyx若t在1,0上为严格凸函数，则xf在D上为严格凸函数．凸函数凸函数的判别定理该定理的几何意义是：凸函数上任意两点之间的部分是一段向下凸的弧．凸函数定理4设在凸集nRD上xf可微，则：xf在D上为凸函数的充要条件是对任意的,,Dyx都有：.xyxfxfyfT严格凸函数(充要条件)??凸函数凸函数的判别定理---一阶条件注：定理4提供了一个判别可微函数是否为凸函数的依据.()Tfyfxfxyxxy凸函数定理4-----几何解释一个可微函数是凸函数当且仅当函数图形上任一点处的切线位于曲线的下方.凸函数定理4-----几何解释一个可微函数是凸函数当且仅当函数图形上任一点处的切平面位于曲面的下方.定理5:设在开凸集nRD内xf二阶可微,则xf是D内的凸函数的充要条件为:对任意,Dxxf的Hesse矩阵xG半正定,22221222222122122122122nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxfxG其中：凸函数凸函数的判别定理---二阶条件定理2.3.6:设在开凸集nRD内xf二阶可微,若在D内xG正定,则xf在D内是严格凸函数．注:反之不成立．例：4xxff(x)是严格凸的，但在点0x处xG不是正定的凸函数凸函数的判别定理---二阶条件例：.)2(.)1(,21)(:为正定矩阵条件是上的严格凸函数的充要是为半正定矩阵是上的凸函数的充要条件是阶对称矩阵，则是其中为二次函数，即设QRfQRfnQcxbQxxxfRRfnnTTn凸函数凸函数的判别定理---二阶条件凸规划凸规划(ConvexProgramming)设nRD为凸集，xf为D上的凸函数，则称规划问题xfDxmin为凸规划问题．例：xf若为nR上的凸函数，xfnRxmin则为无约束凸规划问题．例：0Xbs.t.AXminCX线性规划凸规划凸规划例：,,...,1,0)(,...,1,0)(..min(3),,...,1,0)(..min(2),,...,1,0)(..min(1),),...,2,1(h),...,2,1(ljxhmixgtsf(x)mixgtsf(x)ljxhtsf(x)RljSmigSfRSjiijnjin是凸规划：则下面三个规划问题都上的线性函数是上的凹函数，是上的凸函数，是为开凸集，设凸规划定理2.4(1)凸规划问题的任一局部极小点是全局极小点，且全体极小点的集合为凸集．(2)若xf是凸集nRD上的严格凸函数，且凸规划问题xfDxmin局部极小点x*存在，则x*是唯一的全局极小点．凸规划的基本性质定理凸规划的任一局部最优解都是它的整体最优解。证明：设x*是凸规划的一个局部解，则存在δ0,使(*)()(*)1fxfxxXNx，（）如果x*不是整体最优解，则又因为f是凸函数，所以((1)*))(1)(*)(*)(1)(*)(*)2fxxfxfxfxfxfx(（）xX，使(*)()fxfx，取α0充分小，有1(1)**(*),(1)*(*)()fxxfxxXNxxx（），与（2）矛盾例如下非线性规划是否为凸规划：22121112221212min()44()20()10,0fXxxxgXxxgXxxxx2221212222212()()20,02fXffxxxfXffxxx解的正定，凸函数221121212122112212222221212222222212()().00,002000ggxxxgXggxxxggxxxgXggxxx)(,)(21XgXg所以，该问题为凸规划。半正定，凸函数半正定，凸函数如图所示，该问题最优解（最小点）在x*点取得。8.3)()34