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

关于凸集和凸函数和凸规划
第1页，讲稿共50张，创作于星期日
凸集---定义
线性组合 (linear Combination)
仿射组合 (Affine Combination)
凸组合 (Convex Combi令
第26页，讲稿共50张，创作于星期日
例：
设
试证明
在
上是严格凸函数．
证明:
设
且
都有：
因此,
在
上是严格凸函数．
凸函数
第27页，讲稿共50张，创作于星期日
例：
试证线性函数是
上的凸函数．
证明:
设
则
故,
是凸函数．
类似可以证明
也是凹函数.
凸函数
第28页，讲稿共50张，创作于星期日
凸函数
定理1
设
是凸集
上的凸函数充要条件
性质
詹生(Jensen)不等式
不等式应用: 设
，证明:
P41
第29页，讲稿共50张，创作于星期日
凸函数
定理2
性质
正线性组合
第30页，讲稿共50张，创作于星期日
凸函数
定理3
设
是凸集
上的凸函数，
则对任意
，水平集
是凸集．
水平集(Level Set)
称为函数f在集合S上关于数 的水平集.
注：定理3 的逆命题不成立.
第31页，讲稿共50张，创作于星期日
下面的图形给出了凸函数
的等值线的图形，可以看出水平集是凸集.
凸函数
第32页，讲稿共50张，创作于星期日
凸函数
第33页，讲稿共50张，创作于星期日
定理1:
设
是定义在凸集
上，
令
则:
(1)
是定义在凸集
是凸集
上的凸函数的充要条件是对
任意的
一元函数
为
上的凸函数.
(2)
设
若
在
上为严格
凸函数，
则
在
上为严格凸函数．
凸函数
凸函数的判别定理
第34页，讲稿共50张，创作于星期日
该定理的几何意义是：凸函数上任意两点之
间的部分是一段向下凸的弧．
凸函数
第35页，讲稿共50张，创作于星期日
定理4
设在凸集
上
可微，
则：
在
上为凸函数的充要条件是对任意的
都有：
严格凸函数(充要条件)??
凸函数
凸函数的判别定理---一阶条件
注：定理4提供了一个判别可微函数是否为凸 函数的依据.
第36页，讲稿共50张，创作于星期日
凸函数
定理4-----几何解释
一个可微函数是凸函数当且仅当函数图形上任一点处的切平面位于曲面的下方.
第37页，讲稿共50张，创作于星期日
凸函数
定理4-----几何解释
一个可微函数是凸函数当且仅当函数图形上任一点处的切平面位于曲面的下方.
第38页，讲稿共50张，创作于星期日
定理5:
设在开凸集
内
二阶可微,则
是
内的凸函数的充要条件为:
对任意
的Hesse矩阵
半正定,
其中：
凸函数
凸函数的判别定理---二阶条件
第39页，讲稿共50张，创作于星期日
:
设在开凸集
内
二阶可微,
若在
内
正定,
则
在
内
是严格凸函数．
注:
反之不成立．
例：
f(x)是严格凸的，
但在点
处
不是正定的
凸函数
凸函数的判别定理---二阶条件
第40页，讲稿共50张，创作于星期日
例：
凸函数
凸函数的判别定理---二阶条件
第41页，讲稿共50张，创作于星期日
凸规划
凸规划(Convex Programming)
设
为凸集，
为
上的凸函数，
则称规划问题
为凸规划问题．
例：
为
上的凸函数，
为无约束凸规划问题．
例：
凸规划
第42页，讲稿共50张，创作于星期日
凸规划
例：
第43页，讲稿共50张，创作于星期日
凸规划

(1)凸规划问题的任一局部极小点是全局
极小点，且全体极小点的集合为凸集．
(2)
若
是凸集
上的严格凸函数，
且凸规划问题
局部极小点x*存在，
则x*是唯一的全局极小点．
凸规划的基本性质
第44页，讲稿共50张，创作于星期日
定理 凸规划的任一局部最优解都是它的整体最优解。
证明：设x*是凸规划的一个局部解，则存在δ>0,使
如果x*不是整体最优解，则
又因为f是凸函数，所以
取α>0充分小，有
第45页，讲稿共50张，创作于星期日
例 如下非线性规划是否为凸规划：
正定，凸函数
第46页，讲稿