最优化方法课件01.4

§1.7

凸集与凸函数1凸集定义1.7.1

设集合D

Rn,若对于任意点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例3凸集的例例1.7.1

超球||x||≤r为凸集证明设x,y为超球中任意两点,0≤a≤1,则有||ax+(1-a)y||≤a||x||+(1-a)||y||≤a

r+(1-a)r=r,即点ax+(1-a)y属于超球,所以超球为凸集.4凸集的性质(i)有限个(可以改成无限)凸集的交集为凸集.即:若Dj(j

∈

J)是凸集,则它们的交集D={x|x

∈

Dj,j

∈J}是凸集.(ii)设D是凸集,b是一实数,则下面集合是凸集bD={y|y=bx,x∈

D}.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推论凸集的线性组合是凸集.定义1.7.2

设xi∈

Rn,i=1,…,k,实数li≥0,则称为x1,x2,…,xk的凸组合.容易证明:凸集中任意有限个点的凸组合仍然在该凸集中.两点的凸组合三点的凸组合多点的凸组合7极点定义1.7.3

设D为凸集,x∈D.若D中不存在两个相异的点y,z及某一实数a∈(0,1)使得

x=ay+(1-a)z

则称x为D的极点.凸集极点凸集极点8极点例1.7.2D={x∈Rn|||x||≤a}(a>0),则||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凸函数定义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凸函数定义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凸函数的例例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)2<0因此f(x)在(–∞,+∞)上是严格凸函数.例1.7.4

线性函数f(x)=cTx=c1x1+c2x2+···+cnxn既是Rn上凸函数也是Rn上凹函数.12凸函数的几何性质对一元函数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处的函数值,所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.13对于一元凸函数f(x),可以发现,位于函数曲线上方的图形是凸集.事实上这一结论对于多元函数也是成立的,而且是充要条件,即有下面的定理.定理:设f(x)是定义在凸集DRn上的函数,则f(x)是凸函数的充要条件是其上图epi(f)为凸集,其中epi(f)={(x,y)|x∈

D,y

∈

R,y≥f(x)}.证明:作业14凸函数的性质(i)设f(x)是凸集DRn上的凸函数,实数k≥0,则kf(x)也是D上的凸函数.(ii)设f1(x),f2(x)是凸集DRn上的凸函数,实数l,m≥0,则lf1(x)+mf2(x)也是D上的凸函数.(iii)设f(x)是凸集DRn上的凸函数,b为实数,则水平集S(f,b)={x|x∈D,f(x)≤b

}是凸集.下面的图形给出了凸函数f(x,y)=x4+3x2+y4+y2+xy的等值线(f(x,y)=2,4,6,8,10,12)的图形.可以看出水平集为凸集.15凸函数的性质16凸函数的判断定理1.7.1

设f(x)定义在凸集DRn上,x,y∈D.令F(t)=f(tx+(1-t)y),t∈[0,1],则该定理的几何意义是:凸函数上任意两点之间的部分是一段向下凸的弧线.(i)f(x)是凸集D上的凸函数的充要条件是对任意的x∈D,一元函数F(t)为[0,1]上的凸函数.(ii)f(x)是凸集D上的严格凸函数的充要条件是对任意的x,y∈D(x≠y),一元函数F(t)为[0,1]上的严格凸函数.17凸函数的判断18一阶条件定理1.7.2

(一阶条件)设在凸集DRn上f(x)可微,则f(x)在D上为凸函数的充要条件是对任意的x,y∈D,都有f(y)≥f(x)+f(x)T(y-x)定理1.7.3(一阶条件)设在凸集DRn上f(x)可微,则f(x)在D上为严格凸函数的充要条件是对任意的x,y∈D,x≠y,都有f(y)>f(x)+f(x)T(y-x)19二阶条件定理1.7.4(二阶条件)设在开凸集DRn上f(x)可微,则(i)f(x)是D内的凸函数的充要条件为,在D内任一点x处,f(x)的Hesse矩阵G(x)半正定,其中(ii)若在D内G(x)正定,则f(x)在D内是严格凸函数.20+(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-+所以，=

x是R上凸函数。)(xf2例如，对=x，因x1,x2∈R，∈(0,1))(xf"a"221例：判断下列函数的凹凸性。（1）（2）解：

22凸规划定义1.7.6

设DRn为凸集,则f(x)为D上的凸函数,则称规划问题

minf(x)

s.t.x∈D

为凸规划问题.定理1.7.5(i)f(x)是凸函数，凸规划的任一局部极小点x是整体极小点,全体极小点组成凸集.(ii)若f(x)是DRn上的严格凸函数,且凸规划问题minf(x)s.t.x∈D的整体极小点存在,则整体极小点唯一.23定理1.7.5证明(思路)(i)x*为局部极小点,若存在x0使得f(x0)<f(x*),

则f(tx0

+(1-t)x*)≤tf(x0)+(1-t)f(x*)

令t取一个足够小的正数,可导出矛盾.(ii)若存在x*,y*都是整体极小点(f(x*)=f(y*)),则f(tx*+(1-t)y*)<tf(x*)+(1-t)f(y*)=f(x*)矛盾.24定义1.7.7:若规划中，和为凸函数，是线性函数，则上述问题为凸规划25例：线性规划是凸规划。例：数学规划易知，与都是凸函数，所以该规划是凸规划。26

对于一般的规划（P），其局部最优解不一定是全局最优解，其可行集也未必是凸集。但若（P）是凸规划，则有下面的结论。定理1.7.6：设规划（P）是凸规划，则（1）（P）的可行集R为凸集；（2）（P）的最优解集合R*是凸集；（3）（P）的任何局部最优解都是全局最优解。定理1.7.7：（1)凸规划的任意局部极小点就是整体极小点，且极小点集合是凸集。（2）如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点还是唯一的。27练习：1、求的梯度和Hesse矩阵。2、判断函数的凹凸性。3、判断下述非线性规划是否为凸规划？28例:证明集合是凸集。其中，A为mn矩阵，b为m维向量。证明：任取，则所以，29

§1.8极小点的判定条件30最优化问题的一般形式为:(1.1)(目标函数)(1.3)(不等式约束)(1.2)(等式约束)其中x是n维向量.在实际应用中,可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式.我们总是讨论P:31

函数在局部极小点满足什么条件？反之满足什么条件的是局部极小点？什么是整体（全局）极小点？那么怎样找到全局极小点呢？下面我们给出各类极小点的定义32无约束优化:最优解的分类和条件给定一个函数,寻找

使得

最小，即局部最优解全局最优解x*f(x)xlxgo

怎样寻求局部最优解，和全局最优解？33邻域的定义34整体最优解定义1.2.3

若x*∈D,对于一切x∈D恒有f(x*)≤f(x),则称x*为最优化问题(P)的整体最优解.若x*∈D,x≠x*,恒有f(x*)<f(x),则称x*为最优化问题(P)的严格整体最优解.35定义1.2.4(局部最优解)

若x*∈D,存在x*的某邻域Ne(x*),使得对于一切x∈D∩Ne(x*),恒有f(x*)≤f(x),则称x*为最优化问题(P)的局部最优解.当x≠x*时,若上面的不等式为严格不等式则称x*为问题(P)的严格局部最优解.显然,整体最优解一定是局部最优解,而局部最优解不一定是整体最优解.x*对应的目标函数值f(x*)称为最优值，记为f

*.36１必要条件：设Ｒ是n维欧氏空间的某一区域，

为定义在Ｒ上的实值函数，是区域Ｒ的内点，若在处可微，且在该点取得局部极小值，则必有或极值存在的条件37其中，为函数

在处的梯度，梯度的方向为

的等值面（等值线）的法线方向，沿这个方向函数值增加最快．满足上式的点称为驻点，在区域内部，极值点必为驻点；但驻点不一定是极值点．

38２充分条件：设Ｒ是n维欧氏空间的某一区域，为定义在Ｒ上的实值函数，是区域Ｒ的内点，

在Ｒ上二次连续可微，若则是的严格局部极小点.极