资源描述
1.7 凸集与凸函数凸集与凸函数1 1凸凸 集集定义定义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例例 3 3凸集的例凸集的例例例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凸集的性质凸集的性质(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凸集的性质凸集的性质(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推论推论 凸集的线性组合是凸集凸集的线性组合是凸集.定义定义1.7.2 设设xi Rn,i=1,k,实数实数l li0,则则 称为称为x1,x2,xk的的凸组合凸组合.容易证明容易证明:凸集中任意有限个点的凸组合仍然凸集中任意有限个点的凸组合仍然在该凸集中在该凸集中.两点的凸组合两点的凸组合三点的凸组合三点的凸组合 多点的凸组合多点的凸组合7 7极极 点点定义定义1.7.3 设设D为凸集为凸集,xD.若若D中不存在两中不存在两个相异的点个相异的点y,z及某一实数及某一实数a a(0,1)使得使得x=a ay+(1-a a)z则称则称x为为D的极点的极点.凸凸集集极点极点凸凸集集极点极点8 8极极 点点例例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凸凸 函函 数数定义定义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凸凸 函函 数数定义定义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凸函数的例凸函数的例例例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二阶条件二阶条件定理定理定理定理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 +(1-)-a a)(1xfa a)(2xf)1(21xxfa aa a-+=2221)1(xxa aa a-+221)1(xxa aa a-+-=2221)1(xxa aa a-+-)1(2)1(21222212xxxxa aa aa aa a-+-+=212221)1(2)1()1(xxxxa aa aa aa aa aa a-+-=(1-)a aa a)2(212221xxxx-+=(1-)a aa a(x1-x2)02 +(1-)a a)(1xfa a)(2xf)1(21xxfaa-+所以，所以，=x 是是R上凸函数。上凸函数。)(xf2例如，对例如，对 =x x，因，因 x x1 1,x x2 2R R，(0,1)(0,1)(xf a a22121例：判断下列函数的凹凸性。例：判断下列函数的凹凸性。例：判断下列函数的凹凸性。例：判断下列函数的凹凸性。（1 1）（2 2）解解解解：2222凸规划凸规划定义定义1.7.6 设设D Rn为凸集为凸集,则则f(x)为为D上的凸函数上的凸函数,则称则称规划问题规划问题min f(x)s.t.x D为凸规划问题为凸规划问题.定理定理1.7.5(i)f(x)是凸函数，是凸函数，凸规划的任一局部极小点凸规划的任一局部极小点x是整体极小点是整体极小点,全体极小点全体极小点组成凸集组成凸集.(ii)若若f(x)是是D Rn上的严上的严格凸函数格凸函数,且凸规划问题且凸规划问题min f(x)s.t.x D的整体极小点存在的整体极小点存在,则整体则整体极小点唯一极小点唯一.2323定理定理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定义定义1.7.7:1.7.7:若规划若规划中，中，和和 为凸函数，为凸函数，是线性函是线性函数，则上述问题为凸规划数，则上述问题为凸规划2525例：线性规划例：线性规划例：线性规划例：线性规划 是凸规划。是凸规划。是凸规划。是凸规划。例：数学规划例：数学规划 易知，易知，与与 都是凸函数，所以该规划是凸规划。都是凸函数，所以该规划是凸规划。2626 对于一般的规划（对于一般的规划（对于一般的规划（对于一般的规划（P P P P），其局部最优解不一定是全局最优解，），其局部最优解不一定是全局最优解，），其局部最优解不一定是全局最优解，），其局部最优解不一定是全局最优解，其可行集也未必是凸集。但若（其可行集也未必是凸集。但若（其可行集也未必是凸集。但若（其可行集也未必是凸集。但若（P P P P）是凸规划，则有下面的结）是凸规划，则有下面的结）是凸规划，则有下面的结）是凸规划，则有下面的结论。论。论。论。定理定理定理定理1.7.61.7.61.7.61.7.6：设规划（设规划（设规划（设规划（P P P P）是凸规划，则）是凸规划，则）是凸规划，则）是凸规划，则 （1 1 1 1）（P P P P）的可行集）的可行集）的可行集）的可行集R R R R为凸集；为凸集；为凸集；为凸集；（2 2 2 2）（P P P P）的最优解集合）的最优解集合）的最优解集合）的最优解集合R*R*R*R*是凸集；是凸集；是凸集；是凸集；（3 3 3 3）（P P P P）的任何局部最优解都是全局最优解。）的任何局部最优解都是全局最优解。）的任何局部最优解都是全局最优解。）的任何局部最优解都是全局最优解。定理定理定理定理1.7.71.7.71.7.71.7.7：（1)1)1)1)凸规划的任意局部极小点就是凸规划的任意局部极小点就是凸规划的任意局部极小点就是凸规划的任意局部极小点就是整体极小点，且极小点集合是凸集。整体极小点，且极小点集合是凸集。整体极小点，且极小点集合是凸集。整体极小点，且极小点集合是凸集。（2 2）如果凸规划的目标函数是严格凸函数，又如果凸规划的目标函数是严格凸函数，又如果凸规划的目标函数是严格凸函数，又如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点还是唯一的。存在极小点，则它的极小点还是唯一的。存在极小点，则它的极小点还是唯一的。存在极小点，则它的极小点还是唯一的。2727练习：练习：1、求、求 的梯度和的梯度和Hesse矩阵。矩阵。2、判断函数、判断函数 的凹凸性。的凹凸性。3、判断下述非线性规划是否为凸规划？、判断下述非线性规划是否为凸规划？2828例例:证明集合证明集合 是凸集。其中，是凸集。其中，A A为为 m m n n矩阵，矩阵，b b为为m m维向量。维向量。证明：任取证明：任取 ，则，则所以，所以，2929 1.8 1.8 极小点的判定条件极小点的判定条件3030最优化问题的一般形式为最优化问题的一般形式为:(1.1)(目标函数目标函数)(1.3)(不等式约不等式约束束)(1.2)(等式约束等式约束)其中其中x是是n维向量维向量.在实际应用中在实际应用中,可以将求最大值的目标函数取可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式相反数后统一成公式中求最小值的形式.我们总是讨论我们总是讨论P P:3131 函数函数 在在局部极小点局部极小点满足什么条满足什么条件？反之满足什么条件的是局部极小点件？反之满足什么条件的是局部极小点？什么是？什么是整体整体（全局）极小点全局）极小点？那么怎？那么怎样找到全局极小点呢？样找到全局极小点呢？下面我们给出各类极小点的定义下面我们给出各类极小点的定义3232无约束优化无约束优化:最优解的分类和条件最优解的分类和条件给定一个函数给定一个函数给定一个函数给定一个函数 ,寻找寻找寻找寻找 使得使得使得使得 最小，最小，最小，最小，即即局部最优解局部最优解全局最优解全局最优解x*f(x)xlxgo 怎样寻求局部最优解，和全局最优解？怎样寻求局部最优解，和全局最优解？3333vv邻域的定义邻域的定义3434整体最优解整体最优解定义定义1.2.3 若若x*D,对于一切对于一切xD恒有恒有f(x*)f(x),则称则称x*为最优化问题为最优化问题(P)的的整体最优整体最优解解.若若x*D,xx*,恒有恒有f(x*)4343极值存在的条件极值存在的条件例例2 2 试研究函数试研究函数 的驻点的驻点得得 点为驻点，点为驻点，是一无函数是一无函数 的极大点，而的极大点，而 却是一元函数却是一元函数 的极小点，即：的极小点，即：故驻点故驻点 不是极值点，而是一个鞍点不是极值点，而是一个鞍点解：令解：令4444如如函函数数 在在点点 处处的的梯梯度度 ，但但 是是双双曲曲面面的鞍点，而不是极小点。的鞍点，而不是极小点。o o4545鞍点：设X和Y是两个非空集,f是积空间XY上的 一 个 函 数,点(x0,Y0)XxY，若 满 足 min,f(x,Yo)。maxf(xo,y)则称为f在xY上一个鞍点。为了确保鞍点的存在,我们通常加上一些先决条件,例如:如果X和Y是拓扑向量空间内紧集,f是XY上一个连续凸一凹的 o4646例例3 3 试试求求函函数数f(xf(x1 1,x,x2 2)=2x)=2x1 12 2-8x-8x1 1+2x+2x2 2-4x4x2 2+20+20的极值和极值点的极值和极值点解：令解：令得（得（2,12,1）点为驻点）点为驻点4747极值存在的条件极值存在的条件其海赛矩阵之行列式其海赛矩阵之行列式可知（可知（2,12,1）点为极小点）点为极小点,其极小值为其极小值为:4848定理定理1.5 1.5 若多元函数在其极小点处的若多元函数在其极小点处的HesseHesse矩阵是正定的，则它在这个极小点附近的等矩阵是正定的，则它在这个极小点附近的等值面近似地呈现为同心椭圆球面簇值面近似地呈现为同心椭圆球面簇4949
展开阅读全文