最优化方法.ppt
最优化方法课件最优化方法课件现在学习的是第1页，共26页凸凸 集集定义定义1.7.1 设集合设集合D Rn,若对于任意点若对于任意点x,y D,及实数及实数a a,0a a1,都有都有a ax+(1-a a)y D,则称集合则称集合D为为凸集凸集.常见的凸集常见的凸集:空集空集(补充定义补充定义),整个整个欧式空间欧式空间Rn,超平面超平面 H=x Rn|a1x1+a2x2+anxn=b半空间半空间 H+=xRn|a1x1+a2x2+anxnb2 2现在学习的是第2页，共26页例例 3 3现在学习的是第3页，共26页凸集的例凸集的例例例1.7.1 超球超球|x|r为凸集为凸集证明证明 设设x,y为超球中任意两点为超球中任意两点,0 0a a1,则有则有|a ax+(1-a a)y|a a|x|+(1-a a)|y|a a r+(1-a a)r=r,即点即点a ax+(1-a a)y属于超球属于超球,所以超球为凸集所以超球为凸集.4 4现在学习的是第4页，共26页凸集的性质凸集的性质(i)有限个有限个(可以改成无限可以改成无限)凸集的交集为凸集凸集的交集为凸集.即即:若若Dj(j J)是凸集是凸集,则它们的交集则它们的交集D=x|x Dj,j J 是凸集是凸集.(ii)设设D是凸集是凸集,b b是一实数是一实数,则下面集合是凸集则下面集合是凸集b b D=y|y=b b x,x D.5 5现在学习的是第5页，共26页凸集的性质凸集的性质(iii)(iii)设设设设D D1 1,D D2 2是凸集是凸集是凸集是凸集,则则则则D D1 1与与与与D D2 2的和集的和集的和集的和集D D1 1+D D2 2=y y|y y=x x+z z,x x D D1 1,z z D D2 2 是凸集是凸集是凸集是凸集.注注注注:和集与并集有很大的区别和集与并集有很大的区别和集与并集有很大的区别和集与并集有很大的区别,凸集的并集未必是凸集凸集的并集未必是凸集凸集的并集未必是凸集凸集的并集未必是凸集,而凸集而凸集而凸集而凸集的和集是凸集的和集是凸集的和集是凸集的和集是凸集.例例例例:D D1 1=(=(x x,0),0)T T|x x R R 表示表示表示表示 x x 轴上的点轴上的点轴上的点轴上的点,D D2 2=(0,=(0,y y)T T|y y R R,表表表表示示示示 y y 轴上的点轴上的点轴上的点轴上的点.则则则则D D1 1D D2 2表示两个轴的所有点表示两个轴的所有点表示两个轴的所有点表示两个轴的所有点,它不是凸集它不是凸集它不是凸集它不是凸集;D D1 1+D D2 2=R R2 2是凸集是凸集是凸集是凸集6 6现在学习的是第6页，共26页推论推论 凸集的线性组合是凸集凸集的线性组合是凸集.定义定义1.7.2 设设xi Rn,i=1,k,实数实数l li 0,则则 称为称为x1,x2,xk的的凸组合凸组合.容易证明容易证明:凸集中任意有限个点的凸组合仍然在凸集中任意有限个点的凸组合仍然在该凸集中该凸集中.两点的凸组合两点的凸组合三点的凸组合三点的凸组合多点的凸组合多点的凸组合7 7现在学习的是第7页，共26页极极 点点定义定义1.7.3 设设D为凸集为凸集,xD.若若D中不存在两中不存在两个相异的点个相异的点y,z及某一实数及某一实数a a(0,1)使得使得x=a ay+(1-a a)z则称则称x为为D的极点的极点.凸凸集集极点极点凸凸集集极点极点8 8现在学习的是第8页，共26页极极 点点例例1.7.2 D=x Rn|x|a(a0),则则|x|=a上的上的点均为极点点均为极点证明证明:设设|x|=a,若存在若存在y,z D及及a a(0,1),使得使得x=a ay+(1-a a)z.则则a2=|x|2=（a ay+(1-a a)z,a ay+(1-a a)z）a a2|y|2+(1-a a)2|z|2+2a a(1-a a)|y|z|a2不等式取等号不等式取等号,必须必须|y|=|z|=a,且且（y,z）=|y|z|,容易证明容易证明y=z=x,根据定义可知根据定义可知,x为极点为极点.9 9现在学习的是第9页，共26页凸凸 函函 数数定义定义1.7.4 设函数设函数f(x)定义在凸集定义在凸集D Rn上上,若若对任意的对任意的x,y D,及任意的及任意的a a 0,1都有都有f(a a x+(1-a a)y)a a f(x)+(1-a a)f(y)则称函数则称函数f(x)为凸集为凸集D上的上的凸函数凸函数.1010现在学习的是第10页，共26页凸凸 函函 数数定义定义1.7.5 设函数设函数f(x)定义在凸集定义在凸集D Rn上上,若对任若对任意的意的x,yD,xy,及任意的及任意的a a(0,1)都有都有f(a a x+(1-a a)y)a a f(x)+(1-a a)f(y)则称函数则称函数f(x)为凸集为凸集D上的上的严格凸函数严格凸函数.将上述定义中的不等式反向将上述定义中的不等式反向,可以得到可以得到凹函数凹函数和和严严格凹函数格凹函数的定义的定义.1111现在学习的是第11页，共26页凸函数的例凸函数的例例例1.7.3 设设f(x)=(x1)2,试证明试证明f(x)在在(,+)上上是严格凸函数是严格凸函数.证明证明:设设x,y R,且且xy,a a(0,1)都有都有 f(a ax+(1-a a)y)-(a a f(x)+(1-a a)f(y)=(a ax+(1-a a)y-1)2-a a(x-1)2-(1-a a)(y-1)2=a a(1-a a)(x-y)2f(x)+f(x)T(y-x)1919现在学习的是第19页，共26页二阶条件二阶条件定理定理定理定理1.7.4(1.7.4(二阶条件二阶条件二阶条件二阶条件)设在开凸集设在开凸集设在开凸集设在开凸集D D R Rn n上上上上f f(x x)可微可微可微可微,则则则则(i)(i)f f(x x)是是是是D D内的凸函数的充要条件为内的凸函数的充要条件为内的凸函数的充要条件为内的凸函数的充要条件为,在在在在D D内任一点内任一点内任一点内任一点x x处处处处,f f(x x)的的的的HesseHesse矩阵矩阵矩阵矩阵G G(x x)半正定半正定半正定半正定,其中其中其中其中(ii)若在若在D内内G(x)正定正定,则则f(x)在在D内是严格凸函数内是严格凸函数.2020现在学习的是第20页，共26页 +(1-)-+(1-)-a a)(1 1x xf fa a)(2 2x xf f)1(2 21 1xxfa aa a-+=2 22 22 21 1)1(xxa aa a-+2 22 21 1)1(xxa aa a-+-=2 22 22 21 1)1(xxa aa a-+-)1(2)1(2 21 12 22 22 22 21 12 2xxxxa aa aa aa a-+-+=2 21 12 22 22 21 1)1(2)1()1(xxxxa aa aa aa aa aa a-+-=(1-)(1-)a aa a)2(2 21 12 22 22 21 1xxxx-+=(1-)(1-)a aa a(x1 1-x2 2)0)02 2 +(1-)+(1-)a a)(1 1x xf fa a)(2 2x xf f)1(2 21 1xxfaa-+所以，所以，所以，所以，=x 是是是是R R上凸函数。上凸函数。上凸函数。上凸函数。)(x xf f2 2例如，对例如，对例如，对例如，对 =x x，因，因，因，因 x x1 1 1 1,x x2 2 2 2R R R R，(0,1)(0,1)(0,1)(0,1)(x xf f a a a a 2 22121现在学习的是第21页，共26页例：判断下列函数的凹凸性。例：判断下列函数的凹凸性。例：判断下列函数的凹凸性。例：判断下列函数的凹凸性。（1 1）（2 2）解解解解：2222现在学习的是第22页，共26页凸规划凸规划定义定义1.7.6 设设D Rn为凸集为凸集,则则f(x)为为D上的凸函数上的凸函数,则称规则称规划问题划问题min f(x)s.t.x D为凸规划问题为凸规划问题.定理定理2.1.5(i)凸规划的任一局凸规划的任一局部极小点部极小点x是整体极小点是整体极小点,全全体极小点组成凸集体极小点组成凸集.(ii)若若f(x)是是D Rn上的严格凸上的严格凸函数函数,且凸规划问题且凸规划问题min f(x)s.t.x D的整体极小点存在的整体极小点存在,则整体则整体极小点唯一极小点唯一.2323现在学习的是第23页，共26页定理定理1.7.5证明证明(思路思路)(i)x*为局部极小点为局部极小点,若存在若存在x0使得使得f(x0)f(x*),则则f(t x0+(1-t)x*)t f(x0)+(1-t)f(x*)令令 t 取一个足够小的正数取一个足够小的正数,可导出矛盾可导出矛盾.(ii)若存在若存在x*,y*都是整体极小点都是整体极小点(f(x*)=f(y*),则则f(t x*+(1-t)y*)t f(x*)+(1-t)f(y*)=f(x*)矛盾矛盾.2424现在学习的是第24页，共26页若规划若规划 =l lj jh hmmi ig gt t s sf fj ji i,2 2,1 1,0 0)(,2 2,1 1,0 0)(.)(minminx xx xx x中中中中,和和和和-为凸函数为凸函数为凸函数为凸函数,是线性函数是线性函数是线性函数是线性函数,则上述问题为则上述问题为则上述问题为则上述问题为凸规划。凸规划。凸规划。凸规划。)(x xf f)(x xi ig g)(x xi ih h定义定义定义定义1.7.7:1.7.7:凸规划凸规划凸规划凸规划 设设设设D D 为凸集为凸集为凸集为凸集,是定义在是定义在是定义在是定义在DD上的凸函数，则称规划问题上的凸函数，则称规划问题上的凸函数，则称规划问题上的凸函数，则称规划问题 为凸规划。为凸规划。为凸规划。为凸规划。2525现在学习的是第25页，共26页例：线性规划例：线性规划 是凸规划。是凸规划。例：数学规划例：数学规划 易知，易知，与与 都是凸函数，所以该规划是凸规划。都是凸函数，所以该规划是凸规划。2626现在学习的是第26页，共26页
