第4章优化2(10.5).ppt

《第4章优化2(10.5).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§4.3无约束最优化方法4.3.1凸集和凸函数定义1设DRn，若对D中任意两点x(1)与x(2)，连接x(1)与x(2)的线段仍属于D；换言之，对x(1),x(2)∈D，∈[0,1]恒有x(1)+(1-)x(2)∈D则称D为凸集。x(1)+(1-)x(2)称为x(1)和x(2)的凸组合。例(i)下图中(a),(b)为凸集,(c)为非凸集。x2x2x1x1x1x2(a)(c)(b)(ii)超平面H={x

2、PTx=}为凸集。定义为(iii)半空间H-={x

3、PTx≤}为凸集。定义为(iv)射线L={x

4、x=x(0)+

5、d,≥0}为凸集，其中d为给定的非零向量,x(0)为定点。定义2设D为Rn中非空凸集，若对x(1),x(2)∈D，a∈(0,1)恒有f(+(1-))≤+(1-)f(*))1(xa)2(xa)()1(xfaa)()2(x则称f(x)为D上的凸函数；进一步，若x(1)≠x(2)时，(*)式仅〝<〞成立,则称为f(x)D上严格凸函数。凸函数定义中的条件也可描述为：a1,a2>0,a1+a2=1,有f(a1x(1)+a2x(2)≤a1f(x(1))+a2f(x(2))对下凸的一元函数f(x)的几何意义为：在曲线上任取两点P1(x1

6、,f(x1)),P2(x2,f(x2))弦P1P2位于弧之上（见图）。21PPx1x2x(x,y)p1p2)(xf+(1-)-a)(1xfa)(2xf))1((21xxfaa-+=2221)1(xxaa-+221])1([xxaa-+-=2221)1(xxaa-+-])1(2)1([21222212xxxxaaaa-+-+=212221)1(2)1()1(xxxxaaaaaa---+-=(1-)aa)2(212221xxxx-+=(1-)aa(x1-x2)≥02∴+(1-)≥a)(1xfa)(2xf])1([21xxfaa-+所以，

7、f(x)=x2是R上凸函数。例如，对f(x)=x2，因x1,x2∈R，a∈(0,1)2．凸函数的性质定理1设f1,f2为定义在凸集D上的凸函数，为非负实数，则f1,f1+f2也是D上凸函数。定理2设D是Rn中一个凸集，f是定义在D上的一个凸函数，则f在D的内部连续。定理3设D是Rn中一个非空凸集，f是定义在D上的一个凸函数，则(1)水平集D={x

8、x∈D,f(x)≤}是凸集。(2)f在D上的局部极小点是整体极小点，且极小点的集合为凸集。3.凸函数的判断设函数f(x)存在一阶偏导数，x∈Rn，向量为f(x)在点x处的梯度。

9、进一步，我们有定义3设函数f(x)存在二阶偏导数，x∈Rn，则称矩阵为f(x)在点x处的Hesse矩阵。úúúúúúúúûùêêêêêêêêë鶶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶¶2222122222212212212212nnnnnxfxxfxxfxxfxfxxfxxfxxfxfLLL▽2f(x)=………Tnxfxfxføöççè涶¶¶¶¶,,,21…▽f(x)=例2给定二次函数f(x1,x2)=2x12+x22-2x1x2+x1+1(3.1)求▽f(x)及▽2f(x)。解∵=4x1-2x2+1，=2x2-2x11

10、xf¶¶2xf¶¶∴▽f(x)=(4x1-2x2+1,-2x1+2x2)T(3.2)又∵=4,=-2；=-2,=2222xf¶¶122xxf¶¶¶212xxf¶¶¶212xf¶¶∴▽2f(x)=úûùêëé--2224(3.3)(3.1)式可表为),(21xxf=),(2121xxúûùêëé--2224úûùêëé21xx+(1,0)úûùêëé21xx+1即可表为)(xfcTT++xbAxx21=（3.4）其中A为n阶（此例n=2）对称方阵，x,b为n维列向量，c为常数。而(3.2)式及（3.3）式可表为▽f(x)=úûùêëé

11、--2224),(21xx+=Ax+b,▽2f(x)=Aúûùêëé01实际上，对任意的由(3.4)式给出的二次函数,均有▽f(x)=Ax+b,▽2f(x)=A定理4设D是Rn中非空开凸集,f(x)是定义在D上的可微函数,则f(x)是凸函数的充要条件为x,y∈D,有f(y)≥f(x)+(y-x)T▽f(x)(3.5)而f(x)是D上严格凸函数为x,y∈D,x≠y,(3.5)式仅〝>〞成立。例如，对f(x)=x2f(y)–[f(x)+(y-x)T▽f(x)]=y2–[x2+(y-x)2x]=y2–2xy+x2≥0∴f(x)=x2是

12、R上凸函数。定理5设D是R中非空开凸集,f(x)是定义在D上的二次可微函数,则f(x)是凸函数的充要条件为对x∈D,≥0,即Hesse矩阵半正定。n")(2xfÑ)(2xfÑ若x∈D,>0，即Hesse矩阵正定，则f(x)为严格凸函数