凸集和凸函数和凸规划

关于凸集和凸函数和凸规划凸集---定义线性组合(linearCombination)仿射组合(AffineCombination)凸组合(ConvexCombination)凸锥组合(ConvexConeCombination)第2页,共50页，2024年2月25日，星期天凸集---定义例

二维情况下，两点x1,x2的

(a)线性组合为全平面；

(b)仿射组合为过这两点的直线；

(c)凸组合为连接这两点的线段；

(b)凸锥组合为以原点为锥顶并通过这两点的锥.第3页,共50页，2024年2月25日，星期天凸集---定义第4页,共50页，2024年2月25日，星期天凸集---定义定义1设集合若对于任意两点及实数都有：则称集合为凸集．常见的凸集：单点集{x}，空集

，整个欧氏空间Rn，超平面：半空间：第5页,共50页，2024年2月25日，星期天例：证明超球为凸集．证明：设为超球中的任意两点，则有：即点属于超球,所以超球为凸集．凸集----举例第6页,共50页，2024年2月25日，星期天(1)任意多个凸集的交集为凸集．

(2)设是凸集，是一实数，则下面的集合是凸集：凸集-----性质(3)第7页,共50页，2024年2月25日，星期天推论：设是凸集，则也是凸集，其中是实数．

(4)

S是凸集当且仅当S中任意有限个点的凸组合仍然在S中.P23,定理2.9凸集-----性质第8页,共50页，2024年2月25日，星期天注：和集和并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集．例：表示轴上的点．表示轴上的点．则表示两个轴的所有点，它不是凸集；而凸集．凸集-----性质第9页,共50页，2024年2月25日，星期天定义设S

中任意有限个点的所有凸组合所构成的集合称为S的凸包，记为H(S),即凸集-----凸包(ConvexHull)定理2.1.4

H(S)是Rn

中所有包含S的凸集的交集.H(S)是包含S的最小凸集.第10页,共50页，2024年2月25日，星期天定义锥、凸锥凸集-----凸锥(ConvexCone)第11页,共50页，2024年2月25日，星期天定义分离(Separation)凸集-----凸集分离定理第12页,共50页，2024年2月25日，星期天性质定理2.1.5凸集-----凸集分离定理(2)是点到集合的最短距离点的充要条件为：注：闭凸集外一点与闭凸集的极小距离，即投影定理。第13页,共50页，2024年2月25日，星期天定理2.1.5直观解释我们不妨把一个闭凸集想象为一个三维的充满了气体的气球（不一定为标准球形，但必须是凸的），那么，在气球外一点，到气球各点（包括内部）的距离是不一样的，但直觉告诉我们，肯定在气球上有一点，它到该点的距离是所有距离中最小的。这是凸集的特有性质。如果不是凸集，就不会这样了，比如一个平面上对称心形的图形（它不是凸的）外一点，至少可以找到2点，使其到外面那一点的距离最小。凸集-----凸集分离定理第14页,共50页，2024年2月25日，星期天凸集分离定理定理2.1.6凸集-----凸集分离定理ylS点与闭凸集的分离定理第15页,共50页，2024年2月25日，星期天凸集分离定理应用---Farkas引理定理2.1.7凸集-----凸集分离定理应用Farkas引理在我们即将学习的最优性条件中是重要的基础.第16页,共50页，2024年2月25日，星期天Farkas引理–几何解释

设A的第i个行向量为ai,i=1,2,…,m,则(2.1.4)式有解当且仅当凸锥{x|Ax≤0}与半空间{x|bTx>0}的交不空.即(2.1.4)式有解当且仅当存在向量x,它与各ai的夹角钝角或直角，而与b的夹角为锐角.(2.1.5)式有解当且仅当b在由a1,a2,…,am所生成的凸锥内.a2(2.1.4)有解，(2.1.5)无解a1amb凸集-----凸集分离定理应用a1a2amb(2.1.4)无解，(2.1.5)有解第17页,共50页，2024年2月25日，星期天凸集分离定理应用---Gordan定理定理2.1.8凸集-----凸集分离定理应用利用Farkas引理可推导下述的Gordan定理和择一性定理.凸集分离定理应用---择一性定理定理2.1.9第18页,共50页，2024年2月25日，星期天凸函数凸函数(ConvexFunction)----定义2.4设是非空凸集，若对任意的及任意的都有：则称函数为上的凸函数．注：将上述定义中的不等式反向，可以得到凹函数的定义．第19页,共50页，2024年2月25日，星期天凸函数严格凸函数设是非空凸集，若对任意的及任意的都有：则称函数为上的严格凸函数．注：将上述定义中的不等式反向，可以得到严格凹函数的定义．第20页,共50页，2024年2月25日，星期天凸函数

对一元函数在几何上表示连接的线段．所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方．几何性质表示在点处的函数值．

第21页,共50页，2024年2月25日，星期天f(X)Xf(X1)f(X2)

X1X2第22页,共50页，2024年2月25日，星期天f(X)Xf(X1)f(X2)

X1X2αx1+(1-α)x2f(αx1+(1-α)x2)第23页,共50页，2024年2月25日，星期天f(X)Xαf(x1)

+(1-α)f(x2)f(X1)f(X2)

X1X2αx1+(1-α)x2f(αx1+(1-α)x2)第24页,共50页，2024年2月25日，星期天f(X)Xf(X1)f(X2)

X1X2任意两点的函数值的连线上的点都在曲线的上方αx1+(1-α)x2f(αx1+(1-α)x2)αf(x1)

+(1-α)f(x2)例4.2.1第25页,共50页，2024年2月25日，星期天(a)凸函数(b)凹函数该定义的一个应用——证明不等式例：证明Young不等式推广：Hölder不等式P412.37证法：在Young不等式中令第26页,共50页，2024年2月25日，星期天例：设试证明在上是严格凸函数．证明:设且都有：因此,在上是严格凸函数．凸函数第27页,共50页，2024年2月25日，星期天例：试证线性函数是上的凸函数．证明:设则故,是凸函数．类似可以证明也是凹函数.凸函数第28页,共50页，2024年2月25日，星期天凸函数定理1设是凸集上的凸函数充要条件性质詹生(Jensen)不等式不等式应用:设，证明:P412.36第29页,共50页，2024年2月25日，星期天凸函数定理2性质正线性组合第30页,共50页，2024年2月25日，星期天凸函数定理3设是凸集上的凸函数，则对任意，水平集是凸集．水平集(LevelSet)称为函数f在集合S上关于数的水平集.注：定理3的逆命题不成立.第31页,共50页，2024年2月25日，星期天下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集.凸函数第32页,共50页，2024年2月25日，星期天凸函数第33页,共50页，2024年2月25日，星期天定理1:设是定义在凸集上，令则:(1)是定义在凸集是凸集上的凸函数的充要条件是对任意的一元函数为上的凸函数.(2)设若在上为严格凸函数，则在上为严格凸函数．凸函数凸函数的判别定理第34页,共50页，2024年2月25日，星期天该定理的几何意义是：凸函数上任意两点之间的部分是一段向下凸的弧．凸函数第35页,共50页，2024年2月25日，星期天定理4设在凸集上可微，则：在上为凸函数的充要条件是对任意的都有：严格凸函数(充要条件)??凸函数凸函数的判别定理---一阶条件注：定理4提供了一个判别可微函数是否为凸

函数的依据.第36页,共50页，2024年2月25日，星期天凸函数定理4-----

几何

解释一个可微函数

是凸函数当且

仅当函数图形

上任一点处的

切平面位于曲

面的下方.第37页,共50页，2024年2月25日，星期天凸函数定理4-----

几何

解释一个可微函数

是凸函数当且

仅当函数图形

上任一点处的

切平面位于曲

面的下方.第38页,共50页，2024年2月25日，星期天定理5:设在开凸集内二阶可微,则是内的凸函数的充要条件为:对任意的Hesse矩阵半正定,其中：凸函数凸函数的判别定理---二阶条件第39页,共50页，2024年2月25日，星期天定理2.3.6:设在开凸集内二阶可微,若在内正定,则在内是严格凸函数．注:反之不成立．例：f(x)是严格凸的，但在点处不是正定的凸函数凸函数的判别定理---二阶条件第40页,共50页，2024年2月25日，星期天例：凸函数凸函数的判别定理---二阶条件第41页,共50页，2024年2月25日，星期天凸规划凸规划(ConvexProgramming)设为凸集，为上的凸函数，则称规划问题为凸规划问题．例：为上的凸函数，为无约束凸规划问题．例：凸规划第42页,共50页，2024年2月25日，星期天凸规划例：第43页,共50页，2024年2月25日，星期天凸规划定理2.4(1)凸规划问题的任一局部极小点是全局极小点，且全体极小点的集合为凸集．(2)若是凸集上的严格凸函数，且凸规划问题局部极小点x*存在，则x*是唯一的全局极小点．凸规划的基本性质第44页,共50页，2024年2月25日，星期天定理凸规划的任一局部最优解都是它的整体最优解。证明：设x*是凸规划的一个局部解，则存在δ>0,使如果x*不是整体最优解，则又因为f是凸函数，所以取α>0充分小，有第45页,共50页，2024年2月25日，星期天例如下非