第3讲凸集凸函数凸规划整理课件.ppt

1、第第3 3讲讲 凸集、凸函数、凸规划凸集、凸函数、凸规划凸集凸集-定义定义.1,.2,1,11 miiniimiiimiRxRx 且且其中其中.,.2,1,1miRxRxniimiii 其其中中线性组合线性组合 (linear Combination).,.2,1,1miRxRxniimiii 其其中中仿射组合仿射组合 (Affine Combination).1,.2,1,m1ii1 且且其其中中miRxRxniimiii凸组合凸组合 (Convex Combination)凸锥组合凸锥组合 (Convex Cone Combination)凸集凸集-定义定义例例 二维情况下，两点二维情况下

2、，两点x1 1,x2 2 的的 (a)(a)线性组合为全平面；线性组合为全平面；(b)(b)仿射组合为过这两点的直线；仿射组合为过这两点的直线；(c)(c)凸组合为连接这两点的线段；凸组合为连接这两点的线段；(b)(b)凸锥组合为以原点为锥顶并通过这两点的锥凸锥组合为以原点为锥顶并通过这两点的锥.凸集凸集-定义定义凸集凸集-定义定义定义定义1 1设集合设集合,nRD 若对于任意两点若对于任意两点,Dyx 及实数及实数 ,10 都有：都有：,1Dyx 则称集合则称集合D为为凸集凸集常见的凸集常见的凸集：单点集单点集 x，空集空集，整个欧氏空间，整个欧氏空间 Rn，超平面超平面：,2211bxax

3、axaRxHnnn 半空间半空间：1122 =nnnnTHxRa xa xa xbxRa xb例：例：证明超球证明超球rx 为凸集为凸集证明证明：设设为超球中的任意两点，为超球中的任意两点，yx,10 则有：则有：yx 1 yx 1 ,1rrr 即点即点 yx 1属于超球属于超球,所以超球为凸集所以超球为凸集凸集凸集-举例举例 (1)(1)任意多个凸集的交集任意多个凸集的交集为凸集为凸集 (2)(2)设设D是凸集，是凸集，是一实数，是一实数，则下面的则下面的集合是凸集：集合是凸集：DxxyyD ,凸集凸集-性质性质(3)(3).,|)b(;,|)a(221121212211212121是凸集是

4、凸集是凸集是凸集上的凸集，则上的凸集，则是是和和设设DxDxxxDDDxDxxxDDRDDn 推论推论：kiiiD1 设设kiDi,2,1,是凸集，是凸集，则则也是凸集，也是凸集，其中其中i是实数是实数(4)(4)S 是凸集当且仅当是凸集当且仅当S中任意有限个点的凸中任意有限个点的凸 组合仍然在组合仍然在S中中.凸集凸集-性质性质注：注：和集和集和和并集并集有很大的区别，凸集的并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集未必是凸集，而凸集的和集是凸集例例：RxxDT 0,1表示表示x轴上的点轴上的点 RyyDT ,02表示表示y轴上的点轴上的点则则21DD 表示两个轴的所有点，表

5、示两个轴的所有点，它不是凸集；它不是凸集；221RDD 而而凸集凸集凸集凸集-性质性质定义定义 设设 S S 中任意有限个点的所有凸中任意有限个点的所有凸组合所构成的集合称为组合所构成的集合称为S S的凸包，记为的凸包，记为H H(S S),),即即,nRS 凸集凸集-凸包凸包(Convex Hull)miiiimiiiNmmiSxxSH11,1,.,2,1,0,)(定理定理2.1.42.1.4 H H(S S)是是Rn 中所有包含中所有包含S S 的凸集的交集的凸集的交集.H H(S S)是包含是包含S S 的最小凸集的最小凸集.定义定义 锥、凸锥锥、凸锥.SS.xS,Sxx,0Sx,000

6、为为凸凸锥锥则则称称又又是是凸凸集集，如如果果为为顶顶点点的的锥锥以以是是则则称称有有及及，如如果果对对一一切切设设 SxRSn凸集凸集-凸锥凸锥(Convex Cone)定义定义 分离分离 (Separation).SS axpRxHaxpRxHS ,axpRxHS ,Ra0p,Rp,21TnTn2Tn1n21和和分分离离则则称称超超平平面面使使及及是是非非空空集集合合，如如果果存存在在设设 nRSS凸集凸集-凸集分离定理凸集分离定理性质性质 定理定理2.1.52.1.5 .0Sxyxinfy-x ,y,Sx )1(S,Ryn 即即有有为为最最小小的的距距离离使使得得它它与与则则存存在在唯唯

7、一一的的是是非非空空闭闭凸凸集集，设设nRS凸集凸集-凸集分离定理凸集分离定理 (2)Sx 是点是点y到集合到集合S的最短距离点的的最短距离点的充要条件为：充要条件为：.0SxyxxxT 注：注：闭凸集外一点与闭凸集的极小距离闭凸集外一点与闭凸集的极小距离，即投影定理投影定理。定理定理2.1.5 2.1.5 直观解释直观解释 我们不妨把一个闭凸集想象为一个三维的充满了气体的气我们不妨把一个闭凸集想象为一个三维的充满了气体的气球（不一定球（不一定为为标准球形，但必须是凸的），那么，在标准球形，但必须是凸的），那么，在气气球外一球外一点，到点，到气气球各点（包括内部）的距离是不一样的，但直觉告诉球

8、各点（包括内部）的距离是不一样的，但直觉告诉我们，肯定在我们，肯定在气气球上有一点，它到该点的距离是所有距离中最球上有一点，它到该点的距离是所有距离中最小的。这是凸集的特有性质。如果不是凸集，就不会这样了，小的。这是凸集的特有性质。如果不是凸集，就不会这样了，比如一个平面上对称心形的图形（它不是凸的）外一点，至少比如一个平面上对称心形的图形（它不是凸的）外一点，至少可以找到可以找到2 2点，使其到外面那一点的距离最小。点，使其到外面那一点的距离最小。凸集凸集-凸集分离定理凸集分离定理凸集分离定理凸集分离定理 定理定理2.1.62.1.6 .Syaxp|RxHS,xy,paxp ,R a0,Rp

9、 S,RyTnTTn和和分离分离即存在超平面即存在超平面使得使得及及则存在唯一的则存在唯一的是非空闭凸集，是非空闭凸集，设设 pRSnn凸集凸集-凸集分离定理凸集分离定理ylS点与闭凸集的分离定理点与闭凸集的分离定理凸集分离定理应用凸集分离定理应用-Farkas-Farkas引理引理 定理定理2.1.72.1.7(2.1.5).0y,by A(2.1.4);0 xb,0 Ax,Rb,TTn 有且仅有一组有解：有且仅有一组有解：则下列两个关系式组则下列两个关系式组设设nmRA凸集凸集-凸集分离定理应用凸集分离定理应用FarkasFarkas引理在我们即将学习的最优性条件中是重要的基础引理在我们即

10、将学习的最优性条件中是重要的基础.FarkasFarkas引理引理 几何解释几何解释 设设A的第的第i个行向量为个行向量为ai,i=1,2,m,则则(2.1.4)式有解式有解当且仅当凸锥当且仅当凸锥x|Ax0与半空间与半空间x|bTx0的交不空的交不空.即即(2.1.4)式有解当且仅当存在向量式有解当且仅当存在向量x,它与各它与各ai的夹角钝的夹角钝角或直角，而与角或直角，而与b的夹角为锐角的夹角为锐角.(2.1.5)式有解当且仅当式有解当且仅当b在由在由 a1,a2,am所生成的所生成的凸锥内凸锥内.a a2 2(2.1.4)有解，有解，(2.1.5)无解无解a a1 1a am mb b凸

11、集凸集-凸集分离定理应用凸集分离定理应用a a1 1a a2 2a am mb b(2.1.4)无解，无解，(2.1.5)有解有解凸集分离定理应用凸集分离定理应用-Gordan-Gordan 定理定理 定理定理2.1.82.1.8(2.1.6).0y0,y,0y A(2.1.5);0 Ax,T 且且仅仅有有一一组组有有解解：则则下下列列两两个个关关系系式式组组有有设设nmRA凸集凸集-凸集分离定理应用凸集分离定理应用利用利用FarkasFarkas引理可推导下述的引理可推导下述的GordanGordan定理和择一性定理定理和择一性定理.凸集分离定理应用凸集分离定理应用-择一性定理择一性定理 定

12、理定理2.1.92.1.9(2.1.9)0.yBu A ,Rv0u,Ru(2.1.8)0Bx0,x A,TTpm 满满足足和和无无解解当当且且仅仅当当存存在在则则关关系系式式组组设设mpnmRBRA凸函数凸函数凸函数凸函数-设设 ,:RSxf是非空凸集，是非空凸集，nRD 若对任意的若对任意的,Dyx 及任意的及任意的 1,0 都有：都有：yfxfyxf 11则称函数则称函数 xf为为D上的凸函数上的凸函数注：注：将上述定义中的不等式反向，可以得到将上述定义中的不等式反向，可以得到凹函数凹函数的定义的定义凸函数凸函数严格凸函数严格凸函数设设 ,:RSxf是非空凸集，是非空凸集，nRD 若对任意

13、的若对任意的,(),x yD xy及任意的及任意的0,1都有：都有：11fxyfxfy则称函数则称函数 xf为为D上的上的严格凸函数严格凸函数注：注：将上述定义中的不等式反向，可以将上述定义中的不等式反向，可以得到得到严格凹函数严格凹函数的定义的定义凸函数凸函数l 对一元函数对一元函数 ,xf在几何上在几何上 211xfxf 10 表示连接表示连接 2211,xfxxfx的线段的线段所以所以一元凸函数表示连接函数图形上任意两点一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方的线段总是位于曲线弧的上方几何性质几何性质 211xxf 表示在点表示在点 211xx 处的处的函数值函数值

14、l 例例4.2.1(a)(a)凸函数凸函数 (b)(b)凹函数凹函数该定义的一个应用该定义的一个应用证明不等式证明不等式例：证明例：证明11,pqxyx ypq11,0,0,1.pqx yp q其中()lnf tt 凹pqxxxypqYoung不等式不等式11111pqnnnpqkkkkkkkx yxy 推广：推广：Hlder不等式不等式P41 2.37证法：在证法：在YoungYoung不等式中令不等式中令1:nppikkxxx 1:nqqikkyyy 例：例：设设 ,12 xxf试证明试证明 xf在在 ,上是严格凸函数上是严格凸函数证明证明:设设,Ryx 且且 1,0,yx都有：都有：yf

15、xfyxf 11 22211111 yxyx 012 yx 因此因此,xf在在 ,上是严格凸函数上是严格凸函数凸函数凸函数例：例：试证线性函数是试证线性函数是 nnTxcxcxcxcxf 2211nR上的凸函数上的凸函数证明证明:设设 ,1,0,Ryx则则 yxcyxfT 11 yfxfycxcTT 11故故,xcT是凸函数是凸函数类似可以证明类似可以证明Tc x也是凹函数也是凹函数.凸函数凸函数凸函数凸函数定理定理1 1 设设 xf是凸集是凸集nRD 上的凸函数上的凸函数充要条件充要条件121ii11,.,0(1,2,.,),1,fxf(x).kkiiikkiiiixxxDik则性质性质詹生

16、詹生(Jensen)不等式不等式0ix 不等式应用不等式应用:设设，证明，证明:1112(1),ppppnnxxxxxpnn1112(1),ppppnnxxxxxpnnP41 2.36凸函数凸函数定理定理2 2.)(max(x),.,2,1(0),(xf(x),.,ki11i21上上的的凸凸函函数数都都是是和和则则上上的的凸凸函函数数是是凸凸集集SxfkiSfffiikiik 性质性质正线性组合正线性组合凸函数凸函数定理定理3 3设设 xf是凸集是凸集nRS 上的凸函数，上的凸函数，R 则对任意则对任意，水平集水平集 ,fS是凸集是凸集水平集水平集(Level Set).:,)(|,RSfRS

17、xfSxfSn 其其中中 注：注：定理定理3 3 的逆命题不成立的逆命题不成立.下面的图形给出了凸函数下面的图形给出了凸函数xyy 2 4243,yxxyxf 的等值线的图形，可以看出水平集是凸集的等值线的图形，可以看出水平集是凸集.凸函数凸函数凸函数凸函数定理定理1:1:设设 xf是定义在凸集nRD 上，上，,Dyx 令令 ,1,0,1 tyttxft 则则:(1)(1)xf是定义在凸集是定义在凸集是凸集是凸集D上的上的凸函数凸函数的充要条件是对的充要条件是对任意的任意的,Dyx一元函数一元函数 t为为1,0上的凸函数上的凸函数.(2)(2)设设,yxDyx 若若 t 在在 1,0上为上为严

18、格严格凸函数凸函数，则则 xf在在D上为严格凸函数上为严格凸函数凸函数的判别定理凸函数的判别定理该定理的该定理的几何意义几何意义是：凸函数上任意两点之是：凸函数上任意两点之间的部分是一段向下凸的弧间的部分是一段向下凸的弧定理定理4 4设在凸集设在凸集nRD 上上 xf可微可微，则：则：xf在D上为凸函数的充要条件是对任意的上为凸函数的充要条件是对任意的,Dyx 都有：都有：.xyxfxfyfT 严格凸函数严格凸函数(充要条件充要条件)?)?凸函数的判别定理凸函数的判别定理-一阶条件一阶条件注：注：定理定理4 4提供了一个判别可微函数是否为凸提供了一个判别可微函数是否为凸 函数的依据函数的依据.

19、()Tfyf xf xyxxy 定理定理4-几何几何解释解释一个可微函数一个可微函数是凸函数当且是凸函数当且仅当函数图形仅当函数图形上任一点处的上任一点处的切线位于曲切线位于曲线的下方线的下方.定理定理4-几何几何解释解释一个可微函数一个可微函数是凸函数当且是凸函数当且仅当函数图形仅当函数图形上任一点处的上任一点处的切平面位于曲切平面位于曲面的下方面的下方.定理定理5:5:设在开凸集设在开凸集nRD 内内 xf二阶可微二阶可微,则则 xf是D内的凸函数的充要条件为内的凸函数的充要条件为:对任意对任意,Dx xf的的HesseHesse矩阵矩阵 xG半正定半正定,2222122222212212

20、2122122nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxfxG其中：其中：凸函数的判别定理凸函数的判别定理-二阶条件二阶条件定理定理2.3.6:2.3.6:设在开凸集设在开凸集nRD 内内 xf二阶可微二阶可微,若在若在D内内 xG正定正定,则则 xf在在D内内是严格凸函数是严格凸函数注注:反之不成立反之不成立例例：4xxf f(x)是严格凸的，是严格凸的，但在点但在点0 x处 xG不是正定的不是正定的凸函数的判别定理凸函数的判别定理-二阶条件二阶条件例：例：.)2(.)1(,21)(:为为正正定定矩矩阵阵条条件件是是上上的的严严格格凸凸函函数数的的充充要要是是为为半半正正定

21、定矩矩阵阵是是上上的的凸凸函函数数的的充充要要条条件件是是阶阶对对称称矩矩阵阵，则则是是其其中中为为二二次次函函数数，即即设设QRfQRfnQcxbQxxxfRRfnnTTn 凸函数的判别定理凸函数的判别定理-二阶条件二阶条件凸规划凸规划凸规划凸规划(Convex Programming)(Convex Programming)设设nRD 为凸集为凸集，xf为为D上的凸函数上的凸函数，则称规划问题则称规划问题 xfDx min为凸规划问题为凸规划问题例：例：xf若若为为nR上的凸函数，上的凸函数，xfnRx min则则为无约束凸规划问题为无约束凸规划问题例：例：0 X bs.t.AX min

22、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.42.4(1)(1)凸规划问题的任一局部极小点是全局凸规划问题的任一局部极小点是全局极小点，且全体极小点的集

23、合为凸集极小点，且全体极小点的集合为凸集(2)(2)若若 xf是凸集是凸集nRD 上的严格凸函数，上的严格凸函数，且凸规划问题且凸规划问题 xfDx min局部极小点局部极小点x x*存在，存在，则则x x*是唯一的全局极小点是唯一的全局极小点凸规划的基本性质凸规划的基本性质定理定理 凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。证明：设证明：设x*是凸规划的一个局部解，则存在是凸规划的一个局部解，则存在0,使使(*)()(*)1f xf xxXNx，（）如果如果x*不是整体最优解，则不是整体最优解，则又因为又因为f是凸函数，所以是凸函数，所以(1)*)(

24、1)(*)(*)(1)(*)(*)2fxxf xf xf xf xf x(（）xX，使使(*)()f xf x，取取0充分小，有充分小，有1(1)*(*),(1)*(*)()fxxfxxXNxxx（），与与（2）2）矛矛盾盾例 如下非线性规划是否为凸规划：22121112221212min()44()20()10,0f Xxxxg XxxgXxxx x 2221212222212()()2 0 ,0 2 f Xffx xxf Xffxxx 解解的的正定，正定，凸函数凸函数221121212122112212222221212222222212()().0 0 ,0 0 2 0 0 0 ggx

25、xxg Xggxxxggx xxgXggxxx )(,)(21XgXg所以，该问题为凸规划。半正定，半正定，凸函数凸函数半正定，半正定，凸函数凸函数 8.3)()34.1 58.0()(*2*1*XfxxXTT1x2xo11224*(0.58,1.34)x0)(1Xg0)(2Xg2(*)3.8f X222212112112221212min()44(2)()20()10,0f Xxxxxxg XxxgXxxx x 2221231231 31 21222112321233123min(,)222.()0()216()0f x x xxxxx xx xxxstg xxxxg xxxxg xxxx作业作业nP38 2.1,2.2,2.4,2.9-14,2.19,2.20(后),2.32,2.36