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

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

1、关于凸集和凸函数和关于凸集和凸函数和凸规划凸规划现在学习的是第1页，共50页凸集凸集-定义定义线性组合线性组合 (linear Combination)仿射组合仿射组合 (Affine Combination)凸组合凸组合 (Convex Combination)凸锥组合凸锥组合 (Convex Cone Combination)现在学习的是第2页，共50页凸集凸集-定义定义例例 二维情况下，两点二维情况下，两点x x1 1,x,x2 2的的 (a)(a)线性组合为全平面；线性组合为全平面；(b)(b)仿射组合为过这两点的直线；仿射组合为过这两点的直线；(c)(c)凸组合为连接这两点的线段；凸

2、组合为连接这两点的线段；(b)(b)凸锥组合为以原点为锥顶并通过这两点的锥凸锥组合为以原点为锥顶并通过这两点的锥.现在学习的是第3页，共50页凸集凸集-定义定义现在学习的是第4页，共50页凸集凸集-定义定义定义定义1 1设集合设集合若对于任意两点若对于任意两点及实数及实数都有：都有：则称集合则称集合为为凸集凸集常见的凸集常见的凸集：单点集单点集 x，空集空集，整个欧氏空间，整个欧氏空间 Rn，超平面超平面：半空间半空间：现在学习的是第5页，共50页例：例：证明超球证明超球为凸集为凸集证明证明：设设为超球中的任意两点，为超球中的任意两点，则有：则有：即点即点属于超球属于超球,所以超球为凸集所以超

3、球为凸集凸集凸集-举例举例现在学习的是第6页，共50页 (1)(1)任意多个凸集的交集任意多个凸集的交集为凸集为凸集 (2)(2)设设是凸集，是凸集，是一实数，是一实数，则下面的则下面的集合是凸集：集合是凸集：凸集凸集-性质性质(3)(3)现在学习的是第7页，共50页推论推论：设设是凸集，是凸集，则则也是凸集，也是凸集，其中其中是实数是实数(4)(4)S 是凸集当且仅当是凸集当且仅当S中任意有限个点的凸中任意有限个点的凸 组合仍然在组合仍然在S中中.P23,P23,定理定理2.92.9凸集凸集-性质性质现在学习的是第8页，共50页注：注：和集和并集有很大的区别，凸集的并集和集和并集有很大的区别

4、，凸集的并集未必是凸集，而凸集的和集是凸集未必是凸集，而凸集的和集是凸集例例：表示表示轴上的点轴上的点表示表示轴上的点轴上的点则则表示两个轴的所有点，表示两个轴的所有点，它不是凸集；它不是凸集；而而凸集凸集凸集凸集-性质性质现在学习的是第9页，共50页定义定义 设设 S S 中任意有限个点的所有凸中任意有限个点的所有凸组合所构成的集合称为组合所构成的集合称为S S的凸包，记为的凸包，记为H H(S S),),即即凸集凸集-凸包凸包(Convex Hull)定理定理2.1.42.1.4 H H(S S)是是Rn 中所有包含中所有包含S S 的凸集的交集的凸集的交集.H H(S S)是包含是包含S

5、 S 的最小凸集的最小凸集.现在学习的是第10页，共50页定义定义 锥、凸锥锥、凸锥凸集凸集-凸锥凸锥(Convex Cone)现在学习的是第11页，共50页凸函数凸函数凸函数凸函数(Convex Function)(Convex Function)-定义定义定义定义2.42.4设设是非空凸集，是非空凸集，若对任意的若对任意的及任意的及任意的都有：都有：则称函数则称函数为为上的凸函数上的凸函数注：注：将上述定义中的不等式反向，可以得到将上述定义中的不等式反向，可以得到凹函数凹函数的定义的定义现在学习的是第19页，共50页凸函数凸函数严格凸函数严格凸函数设设是非空凸集，是非空凸集，若对任意的若对

6、任意的及任意的及任意的都有：都有：则称函数则称函数为为上的严格凸函数上的严格凸函数注：注：将上述定义中的不等式反向，可以得将上述定义中的不等式反向，可以得到到严格凹函数严格凹函数的定义的定义现在学习的是第20页，共50页凸函数凸函数l 对一元函数对一元函数在几何上在几何上表示连接表示连接的线段的线段所以所以一元凸函数表示连接函数图形上任意两点一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方的线段总是位于曲线弧的上方几何性质几何性质表示在点表示在点处的处的函数值函数值l 现在学习的是第21页，共50页f(X)f(X)X Xf(Xf(X1 1)f(Xf(X2 2)X X1 1X X2

7、 2现在学习的是第22页，共50页f(X)f(X)X Xf f(X(X1 1)f f(X(X2 2)X X1 1X X2 2 x x1 1+(1-+(1-)x)x2 2f f(x x1 1+(1-+(1-)x)x2 2)现在学习的是第23页，共50页f(X)f(X)X X f(xf(x1 1)+(1-+(1-)f(x)f(x2 2)f(Xf(X1 1)f(Xf(X2 2)X X1 1X X2 2 x x1 1+(1-+(1-)x)x2 2f f(x x1 1+(1-+(1-)x)x2 2)现在学习的是第24页，共50页f(X)f(X)X Xf(Xf(X1 1)f(Xf(X2 2)X X1 1X

8、 X2 2任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方 x x1 1+(1-+(1-)x)x2 2f f(x x1 1+(1-+(1-)x)x2 2)f(xf(x1 1)+(1-+(1-)f(x)f(x2 2)例例4.2.1现在学习的是第25页，共50页(a)凸函数凸函数 (b)凹函数凹函数该定义的一个应用该定义的一个应用证明不等式证明不等式例：证明例：证明Young不等式不等式推广：推广：Hlder不等式不等式P41 2.37证法：在证法：在YoungYoung不等式中

9、令不等式中令现在学习的是第26页，共50页例：例：设设试证明试证明在在上是严格凸函数上是严格凸函数证明证明:设设且且都有：都有：因此因此,在在上是严格凸函数上是严格凸函数凸函数凸函数现在学习的是第27页，共50页例：例：试证线性函数是试证线性函数是上的凸函数上的凸函数证明证明:设设则则故故,是凸函数是凸函数类似可以证明类似可以证明也是凹函数也是凹函数.凸函数凸函数现在学习的是第28页，共50页凸函数凸函数定理定理1 1 设设是凸集是凸集上的凸函数上的凸函数充要条件充要条件性质性质詹生詹生(Jensen)不等式不等式不等式应用不等式应用:设设，证明，证明:P41 2.36现在学习的是第29页，共

10、50页凸函数凸函数定理定理2 2性质性质正线性组合正线性组合现在学习的是第30页，共50页凸函数凸函数定理定理3 3设设是凸集是凸集上的凸函数，上的凸函数，则对任意则对任意，水平集水平集是凸集是凸集水平集水平集(Level Set)称为函数称为函数f f在集合在集合S S上关于数上关于数 的水平集的水平集.注：注：定理定理3 3 的逆命题不成立的逆命题不成立.现在学习的是第31页，共50页下面的图形给出了凸函数下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集的等值线的图形，可以看出水平集是凸集.凸函数凸函数现在学习的是第32页，共50页凸函数凸函数现在学习的是第33页，共50页定理定

11、理1:1:设设是定义在凸集上，上，令令则则:(1(1)是定义在凸集是定义在凸集是凸集是凸集上的上的凸函数凸函数的充要条件是对的充要条件是对任意的任意的一元函数一元函数为为上的凸函数上的凸函数.(2(2)设设若若在在上为上为严格严格凸函数凸函数，则则在在上为严格凸函数上为严格凸函数凸函数凸函数凸函数的判别定理凸函数的判别定理现在学习的是第34页，共50页该定理的该定理的几何意义几何意义是：凸函数上任意两点之是：凸函数上任意两点之间的部分是一段向下凸的弧间的部分是一段向下凸的弧凸函数凸函数现在学习的是第35页，共50页定理定理4 4设在凸集设在凸集上上可微可微，则：则：在上为凸函数的充要条件是对任

12、意的上为凸函数的充要条件是对任意的都有：都有：严格凸函数严格凸函数(充要条件充要条件)?)?凸函数凸函数凸函数的判别定理凸函数的判别定理-一阶条件一阶条件注：注：定理定理定理定理4 4 4 4提供了一个判别可微函数是否为凸提供了一个判别可微函数是否为凸提供了一个判别可微函数是否为凸提供了一个判别可微函数是否为凸 函数的依据函数的依据函数的依据函数的依据.现在学习的是第36页，共50页凸函数凸函数定理定理定理定理4-4-几何几何几何几何解释解释解释解释一个可微函数一个可微函数一个可微函数一个可微函数是凸函数当且是凸函数当且是凸函数当且是凸函数当且仅当函数图形仅当函数图形仅当函数图形仅当函数图形上

13、任一点处的上任一点处的上任一点处的上任一点处的切平面位于曲切平面位于曲切平面位于曲切平面位于曲面的下方面的下方面的下方面的下方.现在学习的是第37页，共50页凸函数凸函数定理定理定理定理4-4-几何几何几何几何解释解释解释解释一个可微函数一个可微函数一个可微函数一个可微函数是凸函数当且是凸函数当且是凸函数当且是凸函数当且仅当函数图形仅当函数图形仅当函数图形仅当函数图形上任一点处的上任一点处的上任一点处的上任一点处的切平面位于曲切平面位于曲切平面位于曲切平面位于曲面的下方面的下方面的下方面的下方.现在学习的是第38页，共50页定理定理5:5:设在开凸集设在开凸集内内二阶可微二阶可微,则则是内的凸

14、函数的充要条件为内的凸函数的充要条件为:对任意对任意的的HesseHesse矩阵矩阵半正定半正定,其中：其中：凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件现在学习的是第39页，共50页定理定理2.3.6:2.3.6:设在开凸集设在开凸集内内二阶可微二阶可微,若在若在内内正定正定,则则在在内内是严格凸函数是严格凸函数注注:反之不成立反之不成立例例：f(x)是严格凸的，是严格凸的，但在点但在点处不是正定的不是正定的凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件现在学习的是第40页，共50页例：例：凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件现在学

15、习的是第41页，共50页凸规划凸规划凸规划凸规划(Convex Programming)(Convex Programming)设设为凸集为凸集，为为上的凸函数上的凸函数，则称规划问题则称规划问题为凸规划问题为凸规划问题例：例：为为上的凸函数，上的凸函数，为无约束凸规划问题为无约束凸规划问题例：例：凸凸规规划划现在学习的是第42页，共50页凸规划凸规划例：例：现在学习的是第43页，共50页凸规划凸规划定理定理2.42.4(1)(1)凸规划问题的任一局部极小点是全局凸规划问题的任一局部极小点是全局极小点，且全体极小点的集合为凸集极小点，且全体极小点的集合为凸集(2(2)若若是凸集是凸集上的严格凸

16、函数，上的严格凸函数，且凸规划问题且凸规划问题局部极小点局部极小点x x*存在，存在，则则x x*是唯一的全局极小点是唯一的全局极小点凸规划的基本性质凸规划的基本性质现在学习的是第44页，共50页定理定理 凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。证明：设证明：设x*是凸规划的一个局部解，则存在是凸规划的一个局部解，则存在0,使使如果如果x*不是整体最优解，则不是整体最优解，则又因为又因为f是凸函数，所以是凸函数，所以取取0充分小，有充分小，有现在学习的是第45页，共50页例例 如下非线性规划是否为凸规划：如下非线性规划是否为凸规划：正定，正定，凸函数凸函数现在学习的是第46页，共50页所以，该问题为凸规划。半正定，半正定，凸函数凸函数半正定，半正定，凸函数凸函数现在学习的是第47页，共50页 如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在x x*点取得。点取得。点取得。点取得。现在学习的是第48页，共50页例例 验证下列（验证下列（MP）是凸规划）是凸规划现在学习的是第49页，共50页感谢大家观看26.09.2022现在学习的是第50页，共50页