《凸集和凸函数和凸规划课件》由会员分享，可在线阅读，更多相关《凸集和凸函数和凸规划课件（51页珍藏版）》请在金锄头文库上搜索。
1、第3讲凸集、凸函数、凸规划凸集 (Convex Set) 凸函数 (Convex Function) 凸规划 (Convex Programming)凸性凸性凸性凸性( (Convexity) )是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念. .具有凸具有凸具有凸具有凸性的非线性规划模型是一类特殊的重要模型，它在最优化性的非线性规划模型是一类特殊的重要模型，它在最优化性的非线性规划模型是一类特殊的重要模型，它在最优化性的非线性规划模型是一类特殊的重要模型，它在最优化的理论证明及算法研究中具有非常重要的作用的理论证明及算
2、法研究中具有非常重要的作用的理论证明及算法研究中具有非常重要的作用的理论证明及算法研究中具有非常重要的作用. .1凸集和凸函数和凸规划凸集-定义线性性组合合 (linear Combination)仿射仿射组合合(Affine Combination)凸凸组合合 (Convex Combination)凸凸锥组合合 (Convex Cone Combination)2凸集和凸函数和凸规划凸集-定义例例二二维情况下，两点情况下，两点x1, x2的的(a)线性性组合合为全平面；全平面；(b)仿射仿射组合合为过这两点的直两点的直线；(c)凸凸组合合为连接接这两点的两点的线段；段；(b)凸凸锥组合合为
3、以原点以原点为锥顶并通并通过这两点的两点的锥.3凸集和凸函数和凸规划凸集-定义4凸集和凸函数和凸规划凸集-定义定定义1设集合集合若若对于任意两点于任意两点及及实数数都有：都有：则称集合称集合为凸集凸集常见的凸集常见的凸集：单点集单点集 x ，空集空集 ，整个欧氏空间，整个欧氏空间 Rn，超平面超平面：半空半空间：5凸集和凸函数和凸规划例：例： 证明超球明超球为凸集凸集证明明： 设为超球中的任意两点，超球中的任意两点，则有：有：即点即点属于超球属于超球,所以超球所以超球为凸集凸集凸集-举例6凸集和凸函数和凸规划 (1)任意多个凸集的交集任意多个凸集的交集为凸集凸集 (2)设是凸集，是凸集， 是一
4、是一实数，数，则下面的下面的集合是凸集：集合是凸集：凸集凸集-性性质(3)7凸集和凸函数和凸规划推推论： 设是凸集，是凸集， 则也是凸集，也是凸集， 其中其中是是实数数 (4) S 是凸集当且是凸集当且仅当当S中任意有限个点的凸中任意有限个点的凸 组合仍然在合仍然在S中中.P23,定理定理2.9凸集凸集-性性质8凸集和凸函数和凸规划注：注：和集和并集有很大的区和集和并集有很大的区别，凸集的并集，凸集的并集未必是凸集，而凸集的和集是凸集未必是凸集，而凸集的和集是凸集例例：表示表示轴上的点上的点表示表示轴上的点上的点则表示两个表示两个轴的所有点，的所有点， 它不是凸集；它不是凸集；而而凸集凸集凸集
5、凸集-性性质9凸集和凸函数和凸规划定定义 设S 中任意有限个点的所有凸中任意有限个点的所有凸组合所构成的集合称合所构成的集合称为S的凸包，的凸包，记为H(S),即即凸集凸集-凸包凸包(ConvexHull)定理定理2.1.4 H(S)是是Rn 中所有包含中所有包含S 的凸集的交集的凸集的交集.H(S)是包含是包含S 的最小凸集的最小凸集.10凸集和凸函数和凸规划定定义 锥、凸、凸锥凸集凸集-凸凸锥(Convex Cone)11凸集和凸函数和凸规划凸函数凸函数凸函数(ConvexFunction)(ConvexFunction)-定义定义定义定义2.42.4设是非空凸集，是非空凸集，若若对任意的
6、任意的及任意的及任意的都有：都有：则称函数称函数为上的凸函数上的凸函数注：注：将上述定将上述定义中的不等式反向，可以得到中的不等式反向，可以得到凹函数凹函数的定的定义19凸集和凸函数和凸规划凸函数严格凸函数格凸函数设是非空凸集，是非空凸集，若若对任意的任意的及任意的及任意的都有：都有：则称函数称函数为上的上的严格凸函数格凸函数注：注：将上述定将上述定义中的不等式反向，可以中的不等式反向，可以得到得到严格凹函数格凹函数的定的定义20凸集和凸函数和凸规划凸函数l 对一元函数一元函数在几何上在几何上表示表示连接接的的线段段所以所以一元凸函数表示一元凸函数表示连接函数接函数图形上任意两点形上任意两点的
7、的线段段总是位于曲是位于曲线弧的上方弧的上方几何性几何性质表示在点表示在点处的的函数函数值l 21凸集和凸函数和凸规划f(X)f(X)X Xf(Xf(X1 1) )f(Xf(X2 2) ) X X1 1X X2 222凸集和凸函数和凸规划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凸集和凸函数和凸规划f(X)f(X)X X f( xf( x1 1 ) ) +(1- +(1- ) f( x) f( x2 2) )f(Xf(X1
8、 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凸集和凸函数和凸规划f(X)f(X)X Xf(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 ) ) f( xf( x1 1 )
9、 ) +(1- +(1- ) f( x) f( x2 2) )例例4.2.125凸集和凸函数和凸规划(a) 凸函数凸函数 (b)凹函数凹函数该定定义的一个的一个应用用证明不等式明不等式例：例：证明明Young不等式不等式推广：推广：Hlder不等式不等式P41 2.37证法：在法：在Young不等式中令不等式中令26凸集和凸函数和凸规划例：例：设试证明明在在上是上是严格凸函数格凸函数证明明: 设且且都有：都有：因此因此,在在上是上是严格凸函数格凸函数凸函数27凸集和凸函数和凸规划例：例：试证线性函数是性函数是上的凸函数上的凸函数证明明:设则故故,是凸函数是凸函数类似可以似可以证明明也是凹函数也
10、是凹函数.凸函数28凸集和凸函数和凸规划凸函数定理定理1 设是凸集是凸集上的凸函数上的凸函数充要条件充要条件性性质詹生詹生(Jensen)不等式不等式不等式不等式应用用:设，证明明:P41 2.3629凸集和凸函数和凸规划凸函数定理定理2性性质正正线性性组合合30凸集和凸函数和凸规划凸函数定理定理3设是凸集是凸集上的凸函数，上的凸函数，则对任意任意，水平集水平集是凸集是凸集水平集水平集(LevelSet)称称为函数函数f在集合在集合S上关于数上关于数的水平集的水平集.注：注：定理定理3 的逆命的逆命题不成立不成立.31凸集和凸函数和凸规划下面的下面的图形形给出了凸函数出了凸函数的等的等值线的的
11、图形，可以看出水平集是凸集形，可以看出水平集是凸集.凸函数32凸集和凸函数和凸规划凸函数33凸集和凸函数和凸规划定理定理1:设是定义在凸集上，上，令令则:(1)是定是定义在凸集在凸集是凸集是凸集上的上的凸函数凸函数的充要条件是的充要条件是对任意的任意的一元函数一元函数为上的凸函数上的凸函数.(2)设若若在在上上为严格格凸函数凸函数， 则在在上上为严格凸函数格凸函数凸函数凸函数凸函数的判凸函数的判别定理定理34凸集和凸函数和凸规划该定理的定理的几何意几何意义是：凸函数上任意两点之是：凸函数上任意两点之间的部分是一段向下凸的弧的部分是一段向下凸的弧凸函数凸函数35凸集和凸函数和凸规划定理定理4设在
12、凸集在凸集上上可微可微， 则：在上上为凸函数的充要条件是凸函数的充要条件是对任意的任意的都有：都有：严格凸函数格凸函数(充要条件充要条件)?凸函数凸函数凸函数的判凸函数的判别定理定理-一一阶条件条件注：注：定理定理定理定理4 4提供了一个判提供了一个判提供了一个判提供了一个判别别可微函数是否可微函数是否可微函数是否可微函数是否为为凸凸凸凸函数的依据函数的依据函数的依据函数的依据. .36凸集和凸函数和凸规划凸函数凸函数定理定理定理定理4-4-几何几何几何几何解释解释解释解释一个可微函数一个可微函数一个可微函数一个可微函数是凸函数当且是凸函数当且是凸函数当且是凸函数当且仅仅当函数当函数当函数当函
13、数图图形形形形上任一点上任一点上任一点上任一点处处的的的的切平面位于曲切平面位于曲切平面位于曲切平面位于曲面的下方面的下方面的下方面的下方. .37凸集和凸函数和凸规划凸函数凸函数定理定理定理定理4-4-几何几何几何几何解释解释解释解释一个可微函数一个可微函数一个可微函数一个可微函数是凸函数当且是凸函数当且是凸函数当且是凸函数当且仅仅当函数当函数当函数当函数图图形形形形上任一点上任一点上任一点上任一点处处的的的的切平面位于曲切平面位于曲切平面位于曲切平面位于曲面的下方面的下方面的下方面的下方. .38凸集和凸函数和凸规划定理定理5:设在开凸集在开凸集内内二二阶可微可微,则是内的凸函数的充要条件
14、内的凸函数的充要条件为: 对任意任意的的Hesse矩矩阵半正定半正定,其中：其中：凸函数凸函数凸函数的判凸函数的判别定理定理-二二阶条件条件39凸集和凸函数和凸规划定理定理2.3.6:设在开凸集在开凸集内内二二阶可微可微,若在若在内内正定正定, 则在在内内是是严格凸函数格凸函数注注: 反之不成立反之不成立例例：f(x)是是严格凸的，格凸的，但在点但在点处不是正定的不是正定的凸函数凸函数凸函数的判凸函数的判别定理定理-二二阶条件条件40凸集和凸函数和凸规划例：例：凸函数凸函数凸函数的判凸函数的判别定理定理-二二阶条件条件41凸集和凸函数和凸规划凸规划凸凸规划划(Convex Programmin
15、g)设为凸集凸集，为上的凸函数上的凸函数，则称称规划划问题为凸凸规划划问题例：例：为上的凸函数，上的凸函数，为无无约束凸束凸规划划问题例：例：凸凸规划划42凸集和凸函数和凸规划凸规划例：例：43凸集和凸函数和凸规划凸规划定理定理2.4(1)凸凸规划划问题的任一局部极小点是全局的任一局部极小点是全局极小点，且全体极小点的集合极小点，且全体极小点的集合为凸集凸集(2) 若若是凸集是凸集上的上的严格凸函数，格凸函数，且凸且凸规划划问题局部极小点局部极小点x*存在，存在，则x*是唯一的全局极小点是唯一的全局极小点凸凸规划的基本性划的基本性质44凸集和凸函数和凸规划定理定理 凸规划的任一局部最优解都是它
16、的整体最优解。凸规划的任一局部最优解都是它的整体最优解。证明：设证明：设x*是凸规划的一个局部解，则存在是凸规划的一个局部解，则存在0,使使如果如果x*不是整体最优解，则不是整体最优解，则又因为又因为f是凸函数，所以是凸函数，所以取取0充分小，有充分小，有45凸集和凸函数和凸规划例例如下非线性规划是否为凸规划：如下非线性规划是否为凸规划：正定，正定，凸函数凸函数46凸集和凸函数和凸规划所以，该问题为凸规划。半正定，半正定，凸函数凸函数半正定，半正定，凸函数凸函数47凸集和凸函数和凸规划如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在x x* *点取得。点取得。点取得。点取得。48凸集和凸函数和凸规划例例验证下列（验证下列（MP）是凸规划）是凸规划49凸集和凸函数和凸规划作业P382.1,2.2,2.4,2.9-14,2.19,2.20(后),2.32,2.3650凸集和凸函数和凸规划此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！51凸集和凸函数和凸规划
