凸集凸函数凸规划整理PPT学习教案

1、会计学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)第1页/共51页例例 二维情况下，两点二

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

3、平面： ,2211bxaxaxaRxHnnn 半空间半空间：1122 =nnnnTHxRa xa xa xbxRa xb第4页/共51页例：例： 证明超证明超球球rx 为凸集为凸集证明证明：设设为超球中的任意两点为超球中的任意两点，yx,10 则有：则有： yx 1 yx 1 , 1rrr 即即点点 yx 1属于超球属于超球, ,所以超球为凸集所以超球为凸集第5页/共51页 (1) (1) 任意多个凸集的交集任意多个凸集的交集为凸集为凸集 (2)(2)设设D是凸集，是凸集，是一实数是一实数，则下面的则下面的集合是凸集集合是凸集： DxxyyD , (3)(3) .,|)b(;,|)a(2211

4、21212211212121是凸集是凸集是凸集是凸集上的凸集，则上的凸集，则是是和和设设DxDxxxDDDxDxxxDDRDDn 第6页/共51页推论推论： kiiiD1 设设kiDi,2, 1, 是凸集是凸集，则则也是凸集也是凸集，其其中中i是实数是实数 (4)(4) S 是凸集当且仅当是凸集当且仅当S中任意有限个点的凸中任意有限个点的凸 组合仍然在组合仍然在S中中. .第7页/共51页注：注：和集和集和和并集并集有很大的区别，凸集的并有很大的区别，凸集的并集集未必是凸集，而凸集的和集是凸集未必是凸集，而凸集的和集是凸集例例： RxxDT 0,1表表示示x轴上的点轴上的点 RyyDT ,02

5、表表示示y轴上的点轴上的点则则21DD 表示两个轴的所有点表示两个轴的所有点，它不是凸集它不是凸集；221RDD 而而凸集凸集第8页/共51页定义定义 设设 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 的最小凸集的最小凸集. .第9页/共5

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

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

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

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

10、.第15页/共51页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 2a a1 1a am mb ba a1 1a a2 2a am mb b第16页/共

11、51页凸集分离定理应用凸集分离定理应用-Gordan -Gordan 定理定理 定理定理2.1.82.1.8(2.1.6) . 0y0,y, 0y A(2.1.5) ; 0 Ax,T 且仅有一组有解：且仅有一组有解：则下列两个关系式组有则下列两个关系式组有设设nmRA利用利用FarkasFarkas引理可推导下述的引理可推导下述的GordanGordan定理和择一性定理定理和择一性定理. .凸集分离定理应用凸集分离定理应用-择一性定理择一性定理 定理定理2.1.92.1.9(2.1.9) 0.yBu A ,Rv0u,Ru(2.1.8) 0Bx0,x A,TTpm 满足满足和和无解当且仅当存在无

12、解当且仅当存在则关系式组则关系式组设设mpnmRBRA第17页/共51页凸函数凸函数 -设设 ,:RSxf是非空凸集，是非空凸集，nRD 若对任意的若对任意的,Dyx 及任意及任意的的 1,0 都有都有： yfxfyxf 11则称函则称函数数 xf为为D上的凸函数上的凸函数注：注：将上述定义中的不等式反向，可以得到将上述定义中的不等式反向，可以得到凹函数凹函数的定义的定义第18页/共51页严格凸函数严格凸函数设设 ,:RSxf是非空凸集，是非空凸集，nRD 若对任意的若对任意的,(),x yD xy及任意的及任意的0,1都有都有： 11fxyf xfy则称函则称函数数 xf为为D上的上的严格凸

13、函数严格凸函数注：注：将上述定义中的不等式反向，可以将上述定义中的不等式反向，可以得到得到严格凹函数严格凹函数的定义的定义第19页/共51页l 对一元函数对一元函数 ,xf在几何上在几何上 211xfxf 10 表示连接表示连接 2211,xfxxfx的线段的线段所以所以一元凸函数表示连接函数图形上任意两点一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方的线段总是位于曲线弧的上方 211xxf 表示在点表示在点 211xx 处的处的函数值函数值l 第20页/共51页第21页/共51页第22页/共51页第23页/共51页第24页/共51页例例4.2.1第25页/共51页(a) (a

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

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

16、x xxDik则0ix 1112(1),ppppnnxxxxxpnn1112(1),ppppnnxxxxxpnnP41 2.36第29页/共51页定理定理2 2.)(max(x) ),.,2 , 1(0),(xf(x) ,.,ki11i21上的凸函数上的凸函数都是都是和和则则上的凸函数上的凸函数是凸集是凸集SxfkiSfffiikiik 正线性组合正线性组合第30页/共51页定理定理3 3设设 xf是凸集是凸集nRS 上的凸函数上的凸函数，R 则对任则对任意意，水平集水平集 ,fS是凸集是凸集 .:,)(|,RSfRSxfSxfSn 其中其中 注：注：定理定理3 3 的逆命题不成立的逆命题不成

17、立. .第31页/共51页下面的图形给出了凸函下面的图形给出了凸函数数xyy 2 4243,yxxyxf 的等值线的图形，可以看出水平集是凸集的等值线的图形，可以看出水平集是凸集. .第32页/共51页第33页/共51页定理定理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上为严格凸函数上为严格凸函数第34页/共51页该定理的该定理的几何意义几何意义是：凸函数上任意两点之是：凸函数上任意两点之间的部分是一段向下凸的弧间的部分是一段向下凸的弧第35页/共51页定理定理4 4设在凸集设在凸集nRD 上上 xf可微可微，则：则： xf在D上为凸函数的充要条件是对任意上为凸函数的充要条件是对任意的的,Dyx 都有：都有： .xyxfxfyfT 严格凸函数严格凸函数( (充要条件充要条件)?)? ()Tfyf xf xyxxy 第36页/共51页第37页/共51页第38页/共51页定理定理5:5:设在开凸设在开凸集集nRD 内内 xf二阶可微二阶可微,

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

20、51页例：例：.)2(.)1(,21)( :为正定矩阵为正定矩阵条件是条件是上的严格凸函数的充要上的严格凸函数的充要是是为半正定矩阵为半正定矩阵是是上的凸函数的充要条件上的凸函数的充要条件是是阶对称矩阵，则阶对称矩阵，则是是其中其中为二次函数，即为二次函数，即设设QRfQRfnQcxbQxxxfRRfnnTTn 第41页/共51页凸规划凸规划(Convex Programming)(Convex Programming)设设nRD 为凸集为凸集， xf为为D上的凸函数上的凸函数，则称规划问则称规划问题题 xfDx min为凸规划问题为凸规划问题例例： xf若若为为nR上的凸函数，上的凸函数，

21、xfnRxmin则则为无约束凸规划问题为无约束凸规划问题例：例：0 X bs.t.AX min CX线性规划线性规划凸凸规规划划第42页/共51页例：例： ,.,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是凸规划：是凸规划：则下面三个规划问题都则下面三个规划问题都上的线性函数上的线性函数是是上的凹函数，上的凹函数，是是上的凸函数，上的凸函数，是是为开凸集，为开凸集，

22、设设第43页/共51页定理定理2.42.4(1)(1)凸规划问题的任一局部极小点是全局凸规划问题的任一局部极小点是全局极小点，且全体极小点的集合为凸集极小点，且全体极小点的集合为凸集(2(2) )若若 xf是凸是凸集集nRD 上的严格凸函数，上的严格凸函数，且凸规划问题且凸规划问题 xfDx min局部极小点局部极小点x x* *存在，存在，则则x x* *是唯一的全局极小点是唯一的全局极小点凸规划的基本性质凸规划的基本性质第44页/共51页定理定理 凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。证明：设证明：设x* *是凸规划的一个局部解，则存在是凸规划的一个局部解，则存在0,使使( *)( )( *)