最优化方法课件.ppt

最优化方法课件凸集定义1.7.1设集合DRn,若对于任意点x,y∈D,及实数a,0≤a≤1,都有ax+(1-a)y∈D,则称集合D为凸集.常见的凸集:空集(补充定义),整个欧式空间Rn,超平面H={x∈Rn|a1x1+a2x2+…anxn=b}半空间H+={x∈Rn|a1x1+a2x2+…anxn≥b}第2页,共26页，星期六，2024年，5月例第3页,共26页，星期六，2024年，5月凸集的例例1.7.1超球||x||≤r为凸集证明设x,y为超球中任意两点,0≤a≤1,则有||ax+(1-a)y||≤a||x||+(1-a)||y||≤ar+(1-a)r=r,即点ax+(1-a)y属于超球,所以超球为凸集.第4页,共26页，星期六，2024年，5月凸集的性质(i)有限个(可以改成无限)凸集的交集为凸集.即:若Dj(j∈J)是凸集,则它们的交集D={x|x∈Dj,j∈J}是凸集.(ii)设D是凸集,b是一实数,则下面集合是凸集bD={y|y=bx,x∈D}.第5页,共26页，星期六，2024年，5月凸集的性质(iii)设D1,D2是凸集,则D1与D2的和集D1+D2={y|y=x+z,x∈D1,z∈D2}是凸集.注:和集与并集有很大的区别,凸集的并集未必是凸集,而凸集的和集是凸集.例:D1={(x,0)T|x∈R}表示x轴上的点,D2={(0,y)T|y∈R},表示y轴上的点.则D1∪D2表示两个轴的所有点,它不是凸集;D1+D2=R2是凸集第6页,共26页，星期六，2024年，5月推论凸集的线性组合是凸集.定义1.7.2设xi∈Rn,i=1,…,k,实数li≥0,则称为x1,x2,…,xk的凸组合.容易证明:凸集中任意有限个点的凸组合仍然在该凸集中.两点的凸组合三点的凸组合多点的凸组合第7页,共26页，星期六，2024年，5月极点定义1.7.3设D为凸集,x∈D.若D中不存在两个相异的点y,z及某一实数a∈(0,1)使得

x=ay+(1-a)z

则称x为D的极点.凸集极点凸集极点第8页,共26页，星期六，2024年，5月极点例1.7.2D={x∈Rn|||x||≤a}(a0),则||x||=a上的点均为极点证明:设||x||=a,若存在y,z∈D及a∈(0,1),使得x=ay+(1-a)z.则a2=||x||2=（ay+(1-a)z,ay+(1-a)z）≤a2||y||2+(1-a)2||z||2+2a(1-a)||y||||z||≤a2不等式取等号,必须||y||=||z||=a,且（y,z）=||y||||z||,

容易证明y=z=x,根据定义可知,x为极点.第9页,共26页，星期六，2024年，5月凸函数定义1.7.4设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,及任意的a∈[0,1]都有

f(ax+(1-a)y)≤af(x)+(1-a)f(y)

则称函数f(x)为凸集D上的凸函数.第10页,共26页，星期六，2024年，5月凸函数定义1.7.5设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,x≠y,及任意的a∈(0,1)都有

f(ax+(1-a)y)af(x)+(1-a)f(y)

则称函数f(x)为凸集D上的严格凸函数.将上述定义中的不等式反向,可以得到凹函数和严格凹函数的定义.第11页,共26页，星期六，2024年，5月凸函数的例例1.7.3设f(x)=(x–1)2,试证明f(x)在(–∞,+∞)上是严格凸函数.证明:设x,y∈R,且x≠y,a∈(0,1)都有f(ax+(1-a)y)-(af(x)+(1-a)f(y))

=(ax+(1-a)y-1)2-a(x-1)2-(1-a)(y-1)2=–a(1-a)(x-y)20因此f(x)在(–∞,+∞)上是严格凸函数.例1.7.4线性函数f(x)=cTx=c1x1+c2x2+···+cnxn既是Rn上凸函数也是Rn上凹函数.第12页,共26页，星期六，2024年，5月凸函数的几何性质对一元函数f(x),在几何上af(x1)+(1-a)f(x2)

(0≤a≤1)表示连接(x1,f(x1)),(x2,f(x2))的线段,f(ax1+(1-a)x2)表示在点ax1+(1-a)x2处的函数值,所