凸集和凸函数和凸规划-课件

1、. 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)例例 二维情况下，两点二维情况下，两点x x1 1, x, x2 2的的 (a)(a)线

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

3、 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是是凸凸集集是是凸凸集集上上的的凸凸集集，则则是是和和设设DxDxxxDDDxDxx

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

5、集；221RDD 而而凸集凸集定义定义 设设 S S 中任意有限个点的所有凸中任意有限个点的所有凸组合所构成的集合称为组合所构成的集合称为S S的凸包，记为的凸包，记为H H( (S S),),即即,nRS 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定义定义 分离分离 (Separation) .SS axpRxHaxpRxHS ,axpRxHS ,Ra0p,Rp,21TnTn2Tn1n21和和分分离离则则称称超超平平面面使使及及是是非非空空集集合合，如如果果存存在在设设 nRSS性质性质 定理定理2.1.52.1.5 .0Sxyxinfy-x , y ,Sx )1(S,Ryn 即即有有为为最最小小的的距距离离使使得得它它与与则则存存在在唯唯一一的的是是非非空空闭闭凸凸集集，设设nRS (2)Sx 是点是点y到集合到集合S的最短距离点的的最短距离点的充要条件为：充要条件

7、为： .0SxyxxxT 注：注：闭凸集外一点与闭凸集的极小距离闭凸集外一点与闭凸集的极小距离，即投影定理投影定理。定理定理2.1.5 2.1.5 直观解释直观解释 我们不妨把一个闭凸集想象为一个三维的充满了气体的气我们不妨把一个闭凸集想象为一个三维的充满了气体的气球（不一定球（不一定为为标准球形，但必须是凸的），那么，在标准球形，但必须是凸的），那么，在气气球外一球外一点，到点，到气气球各点（包括内部）的距离是不一样的，但直觉告诉球各点（包括内部）的距离是不一样的，但直觉告诉我们，肯定在我们，肯定在气气球上有一点，它到该点的距离是所有距离中最球上有一点，它到该点的距离是所有距离中最小的。这是

8、凸集的特有性质。如果不是凸集，就不会这样了，小的。这是凸集的特有性质。如果不是凸集，就不会这样了，比如一个平面上对称心形的图形（它不是凸的）外一点，至少比如一个平面上对称心形的图形（它不是凸的）外一点，至少可以找到可以找到2 2点，使其到外面那一点的距离最小。点，使其到外面那一点的距离最小。凸集分离定理凸集分离定理 定理定理2.1.62.1.6 .Syaxp|RxHS,xy,paxp ,R a0,Rp S,RyTnTTn和和分离分离即存在超平面即存在超平面使得使得及及则存在唯一的则存在唯一的是非空闭凸集，是非空闭凸集，设设 pRSnnylS点与闭凸集的分离定理点与闭凸集的分离定理凸集分离定理应

9、用凸集分离定理应用-Farkas-Farkas引理引理 定理定理2.1.72.1.7(2.1.5) . 0y,by A(2.1.4) ; 0 xb, 0 Ax,Rb,TTn 有且仅有一组有解：有且仅有一组有解：则下列两个关系式组则下列两个关系式组设设nmRAFarkasFarkas引理在我们即将学习的最优性条件中是重要的基础引理在我们即将学习的最优性条件中是重要的基础. .FarkasFarkas引理引理 几何解释几何解释 设设A的第的第i个行向量为个行向量为ai,i=1,2,m,则则(2.1.4)式有解式有解当且仅当凸锥当且仅当凸锥x|Ax0与半空间与半空间x|bTx0的交不空的交不空.即即

10、(2.1.4)式有解当且仅当存在向量式有解当且仅当存在向量x,它与各它与各ai的夹角钝的夹角钝角或直角，而与角或直角，而与b的夹角为锐角的夹角为锐角. (2.1.5)式有解当且仅当式有解当且仅当b在由在由 a1, a2, , am所生成的所生成的凸锥内凸锥内.a a2 2a a1 1a am mb ba a1 1a a2 2a am mb b凸集分离定理应用凸集分离定理应用-Gordan -Gordan 定理定理 定理定理2.1.82.1.8(2.1.6) . 0y0,y, 0y A(2.1.5) ; 0 Ax,T 且且仅仅有有一一组组有有解解：则则下下列列两两个个关关系系式式组组有有设设nm

11、RA利用利用FarkasFarkas引理可推导下述的引理可推导下述的GordanGordan定理和择一性定理定理和择一性定理. .凸集分离定理应用凸集分离定理应用-择一性定理择一性定理 定理定理2.1.92.1.9(2.1.9) 0.yBu A ,Rv0u,Ru(2.1.8) 0Bx0,x A,TTpm 满满足足和和无无解解当当且且仅仅当当存存在在则则关关系系式式组组设设mpnmRBRA凸函数凸函数 -设设 :,fxDR是非空凸集，是非空凸集，nRD 若对任意的若对任意的,Dyx 及任意的及任意的 1,0 都有：都有： yfxfyxf 11则称函数则称函数 xf为为D上的凸函数上的凸函数注：注

12、：将上述定义中的不等式反向，可以得到将上述定义中的不等式反向，可以得到凹函数凹函数的定义的定义严格凸函数严格凸函数设设 :,fxDR是非空凸集，是非空凸集，nRD 若对任意的若对任意的,(),x yD xy及任意的及任意的0,1都有：都有： 11fxyfxfy则称函数则称函数 xf为为D上的严格凸函数上的严格凸函数注：注：将上述定义中的不等式反向，可以将上述定义中的不等式反向，可以得到得到严格凹函数严格凹函数的定义的定义l 对一元函数对一元函数 ,xf在几何上在几何上 211xfxf 10 表示连接表示连接 2211,xfxxfx的线段的线段所以所以一元凸函数表示连接函数图形上任意两点一元凸函

13、数表示连接函数图形上任意两点的线段总是位于曲线弧的上方的线段总是位于曲线弧的上方 211xxf 表示在点表示在点 211xx 处的处的函数值函数值例例4.2.1(a) 凸函数凸函数 (b)凹函数凹函数该定义的一个应用该定义的一个应用证明不等式证明不等式例：证明例：证明11,pqxyx ypq11,0, ,0,1.pqx yp q 其中( )lnf tt 凹pqxyxypqYoung不等式不等式11111pqnnnpqkkkkkkkx yxy 推广：推广：Hlder不等式不等式P41 2.37证法：在证法：在YoungYoung不等式中令不等式中令1:nppkkkxxx 1:nqqkkkyyy

14、例：例：设设 ,12 xxf试证明试证明 xf在在 ,上是严格凸函数上是严格凸函数证明证明: :设设,Ryx 且且 1,0, yx都有：都有： yfxfyxf 11 22211111 yxyx 012 yx 因此因此, , xf在在 ,上是严格凸函数上是严格凸函数例：例：试证线性函数是试证线性函数是 nnTxcxcxcxcxf 2211nR上的凸函数上的凸函数证明证明: :设设 ,1,0, Ryx则则 yxcyxfT 11 yfxfycxcTT 11故故, ,xcT是凸函数是凸函数类似可以证明类似可以证明Tc x也是凹函数也是凹函数.定理定理1 1 设设 xf是凸集是凸集nRD 上的凸函数上的

15、凸函数充要条件充要条件121ii11,.,0(1, 2,.,),1, fxf(x ).kkiiikkiiiixxxDik则0ix 1112(1),ppppnnxxxxxpnn 1112(1),ppppnnxxxxxpnn P41 2.36定理定理2 2.)(max(x) ),.,2 , 1(0),(xf(x) ,.,ki11i21上上的的凸凸函函数数都都是是和和则则上上的的凸凸函函数数是是凸凸集集SxfkiSfffiikiik 正线性组合正线性组合定理定理3 3设设 xf是凸集是凸集nRS 上的凸函数，上的凸函数，R 则对任意则对任意，水平集水平集 ,fS是凸集是凸集 .:,)(|,RSfRS

16、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上为上为严格严格

17、凸函数凸函数， 则则 xf在在D上为严格凸函数上为严格凸函数该定理的该定理的几何意义几何意义是：凸函数上任意两点之是：凸函数上任意两点之间的部分是一段向下凸的弧间的部分是一段向下凸的弧定理定理4 4设在凸集设在凸集nRD 上上 xf可微可微， 则：则： xf在D上为凸函数的充要条件是对任意的上为凸函数的充要条件是对任意的,Dyx 都有：都有： .xyxfxfyfT 严格凸函数严格凸函数( (充要条件充要条件)?)? ()Tfyf xf xyxxy 定理定理5:5:设在开凸集设在开凸集nRD 内内 xf二阶可微二阶可微, ,则则 xf是D内的凸函数的充要条件为内的凸函数的充要条件为: :对任意对

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

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

20、规划划例：例： ,.,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)凸规划问题的任一局部极小点是全局凸规划问题的任一局部极小点是全局极小点，且全体极小点的集合为凸集极小点，且全体极小点的集合为凸集(2)(2)若若 xf是凸集是凸集nRD 上的严格凸函数，上的严格凸函数，且凸规划问题且凸规划问题 xfDx min局部极小点局部极小点x x* *存在，存在，则则x x* *是唯一的全局极小点是唯一的全局极小点凸规划的基本性质凸规划的基本性质定理定理 凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。证明：设证明：设x*是凸规划的一个局部解，则存在是凸规划的一个局部解，则存在0,使使( *)