1-2凸集与凸函数

2020/2/281§1.2凸集与凸函数2020/2/282一、凸集定义1.1设集合,nRD若对于任意两点,,Dyx及实数01,都有：1xyD则称集合D为凸集．注：常见的凸集：空集，整个欧氏空间nR超平面：bxaxaxaRxHnnn2211半空间：bxaxaxaRxHnnn22112020/2/283例1：证明超球rx为凸集．证明：设yx,为超球中的任意两点，01,则有：1xy1xy1rrr即点1xy属于超球所以超球为凸集．2020/2/284凸集的性质（１）有限个（可以改成无限）凸集的交集为凸集．（２）设D是凸集，是一实数，则下面的集合是凸集：DxxyyD,（３）设21,DD是凸集，则21,DD的和集2121,,DzDxzxyyDD是凸集;12,DD的差集1212,,DDyyxzxDzD也是凸集。2020/2/285注：和集和并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集．例2：RxxDT0,1表示x轴上的点．RyyDT,02表示y轴上的点．则21DD表示两个轴的所有点，它不是凸集；221RDD而凸集．2020/2/286推论：1miiiD设,1,2,,iDim是凸集，则也是凸集，其中i是实数．定义1.2:设,1,2,,,ixDim实数0,ia11,miia则1,miiixax称为,1,2,,,ixim的凸组合．注：凸集中任意有限个点的凸组合仍然在该凸集中．2020/2/287二、极点若x是S中的一个极点,且有121,0,1,xxx12,xxS,则必有12xxx.,0aaxRxDn定义1.3设D为凸集，,Dx若D中不存在两个相异的点zy,及某一实数0,1使得1,xyz则称x为D的极点．注：例3：则ax上的点均为极点．2020/2/288证：设,ax若存在Dzy,及0,1,使得1,xyz则：221,1axyzyz2222121yzyz2a不等式要取等号，必须,azy且,,zyzy容易证明,xzy根据定义可知x为极点．2020/2/289三、凸函数定义1.4:设函数fx定义在凸集nDR上,若对任意的,,0,1xyD,都有:11fxyfxfy,则称fx为凸集D上的凸函数。定义1.5严格凸函数注:将上述定义中的不等式反向,可以得到凹函数的定义。例:设21fxx,试证明fx在,上是严格凸函数.2020/2/2810证明:设,xyR,且,0,1xy,都有11fxyfxfy22211111xyxy210xy因此fx在,上是严格凸函数.2020/2/2811例:试证线性函数是nR上的凸函数1122Tnnfxcxcxcxcx证明:设,,0,1xyR,则11Tfxycxy11TTcxcyfxfy所以Tcx是凸函数.类似可以证明Tcx是凹函数.2020/2/2812凸函数的几何性质对一元函数fx,在几何上121,fxfx0,1表示连接1122,,,xfxxfx的线段.121fxx表示在点121xx处的函数值.所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方．2020/2/28132020/2/2814凸函数的性质(1)设fx是凸集nDR上的凸函数,实数0k,则kfx也是D上的凸函数.(2)设12,fxfx是凸集nDR上的凸函数,实数,0,则12fxfx也是D上的凸函数.(3)设fx是凸集nDR上的凸函数,是实数,则水平集,,SfxxDfx是凸集.2020/2/2815下面的图形给出了凸函数4242,3fxyxxyyxy的等值线的图形,可以看出水平集是凸集.2020/2/2816凸函数的判定定理1.1:设fx是定义在凸集nDR上,,xyD,令1,0,1,tftxtyt则:(1)fx是凸集D上的凸函数的充要条件是对,xyD,一元函数t在0,1上为凸函数.(2)设,,xyDxy,若t在0,1上为严格凸函数,则fx在D上为严格凸函数.2020/2/2817该定理的几何意义是：凸函数上任意两点之间的部分是一段向下凸的弧.2020/2/2818一阶判别条件定理1.2:设在凸集nDR上fx可微,则:fx在D上为凸函数的充要条件是对,xyD,都有:Tfyfxfxyx定理1.3:严格凸函数(充要条件)2020/2/2819二阶判别条件定理1.4:设在开凸集nDR内fx二阶可微,则(1)fx是D内凸函数的充要条件为:对,xDfx的Hesse矩阵半正定.其中22221121222222122222212nnnnnfffxxxxxfffGxfxxxxxxfffxxxxx2020/2/2820(2)若在D内Gx正定,则fx在D内是严格凸函数.注：反之不成立．例:4fxx显然是严格凸的,但在点0x处Gx不是正定的.二、凸规划定义1.6:设nDR为凸集,fx为D上的凸函数,则称规划问题minxDfx为凸规划问题.2020/2/2821定理1.5:(1)凸规划问题的任一局部极小点x是全局极小点,全体极小点组成凸集.(2)设nDR为凸集,fx为D上的严格凸函数,且凸规划问题minxDfx的全局极小点存在,则全局极小点是唯一的.