凸集和凸函数和凸规划.ppt

《凸集和凸函数和凸规划.ppt》由会员分享，可在线阅读，更多相关《凸集和凸函数和凸规划.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、现在学习的是第1页，共50页. 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页，共50页例例 二维情况下，两点二维情况下

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

3、氏空间 Rn，超平面超平面： ,2211bxaxaxaRxHnnn 半空间半空间：1122 =nnnnTHxRa xa xa xbxRa xb现在学习的是第5页，共50页例：例： 证明超球证明超球rx 为凸集为凸集证明证明： 设设为超球中的任意两点，为超球中的任意两点，yx ,10 则有：则有： yx 1 yx 1 , 1rrr 即点即点 yx 1属于超球属于超球, ,所以超球为凸集所以超球为凸集现在学习的是第6页，共50页 (1) (1) 任意多个凸集的交集任意多个凸集的交集为凸集为凸集 (2)(2)设设D是凸集，是凸集，是一实数，是一实数，则下面的则下面的集合是凸集：集合是凸集： Dxxy

4、yD , (3)(3) .,|)b(;,|)a(221121212211212121是是凸凸集集是是凸凸集集上上的的凸凸集集，则则是是和和设设DxDxxxDDDxDxxxDDRDDn 现在学习的是第7页，共50页推论推论： kiiiD1 设设kiDi,2,1, 是凸集，是凸集， 则则也是凸集，也是凸集， 其中其中i是实数是实数 (4)(4) S 是凸集当且仅当是凸集当且仅当S中任意有限个点的凸中任意有限个点的凸 组合仍然在组合仍然在S中中. .P23,P23,定理定理2.92.9现在学习的是第8页，共50页注：注：和集和并集有很大的区别，凸集的并集和集和并集有很大的区别，凸集的并集未必是凸集，

5、而凸集的和集是凸集未必是凸集，而凸集的和集是凸集例例： RxxDT 0 ,1表示表示x轴上的点轴上的点 RyyDT ,02表示表示y轴上的点轴上的点则则21DD 表示两个轴的所有点，表示两个轴的所有点， 它不是凸集；它不是凸集；221RDD 而而凸集凸集现在学习的是第9页，共50页定义定义 设设 S S 中任意有限个点的所有凸中任意有限个点的所有凸组合所构成的集合称为组合所构成的集合称为S S的凸包，记为的凸包，记为H H( (S S),),即即,nRS miiiimiiiNmmiSxxSH11, 1,.,2 , 1, 0,)( 定理定理2.1.42.1.4 H H( (S S) )是是Rn

6、中所有包含中所有包含S S 的凸集的交集的凸集的交集. .H H( (S S) )是包含是包含S S 的最小凸集的最小凸集. .现在学习的是第10页，共50页定义定义 锥、凸锥锥、凸锥.SS .xS ,Sxx,0Sx,000为为凸凸锥锥则则称称又又是是凸凸集集，如如果果为为顶顶点点的的锥锥以以是是则则称称有有及及，如如果果对对一一切切设设 SxRSn现在学习的是第11页，共50页定义定义 分离分离 (Separation) .SS axpRxHaxpRxHS ,axpRxHS ,Ra0p,Rp,21TnTn2Tn1n21和和分分离离则则称称超超平平面面使使及及是是非非空空集集合合，如如果果存存

7、在在设设 nRSS现在学习的是第12页，共50页性质性质 定理定理2.1.52.1.5 .0Sxyxinfy-x , y ,Sx )1(S,Ryn 即即有有为为最最小小的的距距离离使使得得它它与与则则存存在在唯唯一一的的是是非非空空闭闭凸凸集集，设设nRS (2)Sx 是点是点y到集合到集合S的最短距离点的的最短距离点的充要条件为：充要条件为： .0SxyxxxT 注：注：闭凸集外一点与闭凸集的极小距离闭凸集外一点与闭凸集的极小距离，即投影定理投影定理。现在学习的是第13页，共50页定理定理2.1.5 2.1.5 直观解释直观解释 我们不妨把一个闭凸集想象为一个三维的充满了气体的气我们不妨把一

8、个闭凸集想象为一个三维的充满了气体的气球（不一定球（不一定为为标准球形，但必须是凸的），那么，在标准球形，但必须是凸的），那么，在气气球外一球外一点，到点，到气气球各点（包括内部）的距离是不一样的，但直觉告诉球各点（包括内部）的距离是不一样的，但直觉告诉我们，肯定在我们，肯定在气气球上有一点，它到该点的距离是所有距离中最球上有一点，它到该点的距离是所有距离中最小的。这是凸集的特有性质。如果不是凸集，就不会这样了，小的。这是凸集的特有性质。如果不是凸集，就不会这样了，比如一个平面上对称心形的图形（它不是凸的）外一点，至少比如一个平面上对称心形的图形（它不是凸的）外一点，至少可以找到可以找到2 2

9、点，使其到外面那一点的距离最小。点，使其到外面那一点的距离最小。现在学习的是第14页，共50页凸集分离定理凸集分离定理 定理定理2.1.62.1.6 .Syaxp|RxHS,xy,paxp ,R a0,Rp S,RyTnTTn和和分离分离即存在超平面即存在超平面使得使得及及则存在唯一的则存在唯一的是非空闭凸集，是非空闭凸集，设设 pRSnnylS点与闭凸集的分离定理点与闭凸集的分离定理现在学习的是第15页，共50页凸集分离定理应用凸集分离定理应用-Farkas-Farkas引理引理 定理定理2.1.72.1.7(2.1.5) . 0y,by A(2.1.4) ; 0 xb, 0 Ax,Rb,T

10、Tn 有且仅有一组有解：有且仅有一组有解：则下列两个关系式组则下列两个关系式组设设nmRAFarkasFarkas引理在我们即将学习的最优性条件中是重要的基础引理在我们即将学习的最优性条件中是重要的基础. .现在学习的是第16页，共50页FarkasFarkas引理引理 几何解释几何解释 设设A的第的第i个行向量为个行向量为ai,i=1,2,m,则则(2.1.4)式有解当且式有解当且仅当凸锥仅当凸锥x|Ax0与半空间与半空间x|bTx0的交不空的交不空.即即(2.1.4)式式有解当且仅当存在向量有解当且仅当存在向量x,它与各它与各ai的夹角钝角或直角，而与的夹角钝角或直角，而与b的夹角为锐角的

11、夹角为锐角. (2.1.5)式有解当且仅当式有解当且仅当b在由在由 a1, a2, , am所生成的凸锥所生成的凸锥内内.a a2 2a a1 1a am mb ba a1 1a a2 2a am mb b现在学习的是第17页，共50页凸集分离定理应用凸集分离定理应用-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现在学习的是第18页，共50页凸函数凸函数 -设设 :,fxDR是非空凸集，是非空凸集，nRD 若对任意的若对任意的,Dyx 及任意的及任意的 1,0 都有：都有： yfxfyxf 11则称函数则称函数 xf为为D上的凸函数上的凸函数注：注：将上述定义中的不等式反向，可以得到将上述定义中的不等式反向，可以得到凹函数凹

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

14、上任意两点的线段总是位于曲线弧的上方的线段总是位于曲线弧的上方 211xxf 表示在点表示在点 211xx 处的处的函数值函数值l 现在学习的是第21页，共50页现在学习的是第22页，共50页现在学习的是第23页，共50页现在学习的是第24页，共50页例例4.2.1现在学习的是第25页，共50页(a) 凸函数凸函数 (b)凹函数凹函数该定义的一个应用该定义的一个应用证明不等式证明不等式例：证明例：证明11,pqxyx ypq11,0, ,0,1.pqx yp q 其中( )lnf tt 凹pqxyxypqYoung不等式不等式11111pqnnnpqkkkkkkkx yxy 推广：推广：Hld

15、er不等式不等式P41 2.37证法：在证法：在YoungYoung不等式中令不等式中令1:nppkkkxxx 1:nqqkkkyyy 现在学习的是第26页，共50页例：例：设设 ,12 xxf试证明试证明 xf在在 ,上是严格凸函数上是严格凸函数证明证明: :设设,Ryx 且且 1,0, yx都有：都有： yfxfyxf 11 22211111 yxyx 012 yx 因此因此, , xf在在 ,上是严格凸函数上是严格凸函数现在学习的是第27页，共50页例：例：试证线性函数是试证线性函数是 nnTxcxcxcxcxf 2211nR上的凸函数上的凸函数证明证明: :设设 ,1,0, Ryx则则

16、 yxcyxfT 11 yfxfycxcTT 11故故, ,xcT是凸函数是凸函数类似可以证明类似可以证明Tc x也是凹函数也是凹函数.现在学习的是第28页，共50页定理定理1 1 设设 xf是凸集是凸集nRD 上的凸函数上的凸函数充要条件充要条件121ii11,.,0(1,2,.,),1, fxf(x ).kkiiikkiiiixxxDik则0ix 1112(1),ppppnnxxxxxpnn 1112(1),ppppnnxxxxxpnn P41 2.36现在学习的是第29页，共50页定理定理2 2.)(max(x) ),.,2 , 1(0),(xf(x) ,.,ki11i21上上的的凸凸函

17、函数数都都是是和和则则上上的的凸凸函函数数是是凸凸集集SxfkiSfffiikiik 正线性组合正线性组合现在学习的是第30页，共50页定理定理3 3设设 xf是凸集是凸集nRS 上的凸函数，上的凸函数，R 则对任意则对任意，水平集水平集 ,fS是凸集是凸集 .:,)(|,RSfRSxfSxfSn 其其中中 注：注：定理定理3 3 的逆命题不成立的逆命题不成立. .现在学习的是第31页，共50页下面的图形给出了凸函数下面的图形给出了凸函数xyy 2 4243,yxxyxf 的等值线的图形，可以看出水平集是凸集的等值线的图形，可以看出水平集是凸集. .现在学习的是第32页，共50页现在学习的是第

18、33页，共50页定理定理1:1:设设 xf是定义在凸集nRD 上，上，,Dyx 令令 ,1,0,1 tyttxft 则则: :(1)(1) xf是定义在凸集是定义在凸集是凸集是凸集D上的上的凸函数凸函数的充要条件是对的充要条件是对任意的任意的,Dyx一元函数一元函数 t为为1,0上的凸函数上的凸函数. .(2)(2)设设,yxDyx 若若 t 在在 1,0上为上为严格严格凸函数凸函数， 则则 xf在在D上为严格凸函数上为严格凸函数现在学习的是第34页，共50页该定理的该定理的几何意义几何意义是：凸函数上任意两点之是：凸函数上任意两点之间的部分是一段向下凸的弧间的部分是一段向下凸的弧现在学习的是

19、第35页，共50页定理定理4 4设在凸集设在凸集nRD 上上 xf可微可微， 则：则： xf在D上为凸函数的充要条件是对任意的上为凸函数的充要条件是对任意的,Dyx 都有：都有： .xyxfxfyfT 严格凸函数严格凸函数( (充要条件充要条件)?)? ()Tfyf xf xyxxy 现在学习的是第36页，共50页现在学习的是第37页，共50页现在学习的是第38页，共50页定理定理5:5:设在开凸集设在开凸集nRD 内内 xf二阶可微二阶可微, ,则则 xf是D内的凸函数的充要条件为内的凸函数的充要条件为: :对任意对任意,Dx xf的的HesseHesse矩阵矩阵 xG半正定半正定, , 2

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

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

22、规规划划凸规凸规划划现在学习的是第42页，共50页例：例： ,.,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是是凸凸规规划划：则则下下面面三三个个规规划划问问题题都都上上的的线线性性函函数数是是上上的的凹凹函函数数，是是上上的的凸凸函函数数，是是为为开开凸凸集集，设设现在学习的是第43页，共50页定理定理2.42.4(1)(1)凸规划问题的任一局部极小点是全局凸规划

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

24、果x*不是整体最优解，则不是整体最优解，则又因为又因为f是凸函数，所以是凸函数，所以(1) *)(1) ( *)( *)(1) ( *)( *)2fxxf xf xf xf xf x( (（）xX ，使使( *)( )f xf x，取取0充分小，有充分小，有1(1) *( *),(1) *( *)()fxxfxxXNxxx（），与与（2）2）矛矛盾盾现在学习的是第45页，共50页22121112221212min()44()20()10,0f Xxxxg XxxgXxxx x 2221212222212()() 2 0 ,0 2 f Xffx xxf Xffxxx 解解的的正定，正定，凸函数凸

25、函数现在学习的是第46页，共50页221121212122112212222221212222222212()(). 0 0 , 0 0 2 0 0 0 ggx xxg Xggxxxggx xxgXggxxx )( , )(21XgXg所以，该问题为凸规划。半正定，半正定，凸函数凸函数半正定，半正定，凸函数凸函数现在学习的是第47页，共50页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 现在学习的是第48页，共50页2221231231 31 21222112321233123min( ,)222.( )0( )216( )0f x x xxxxx xx xxxstg xxxxg xxxxg xxxx现在学习的是第49页，共50页感谢大家观看感谢大家观看9/1/2022现在学习的是第50页，共50页