3--理论基础--2-2012.ppt

3.2函数的凸性,主要概念：1.单峰函数2.凸集3.凸函数4.凸规划,概念,1.单峰函数:函数f(x)的极值点在区间（或D）内是唯一的。又称为具有凸性的函数。特点：其极值即是最优值。,概念,对于有约束的函数，可行域D是Rn中设计点的集合，即2.凸集与非凸集：如果集合D中任两点x(1)、x(2)的连线落在集合D内，则称集合D为Rn的一个凸集。反之为非凸集。,概念,3.凸集的数学表达式：在Rn内，对任意两点x(1)、x(2)D，x为两点连线上任一点，对任意实数a(0a1)，恒有x=ax(1)+(1-a)x(2)D成立，则D称为凸集。Rn总是凸集。,4.凸函数：具有凸性或有唯一局部最优值的函数。（1）凸函数数学表达式：设f(x)为定义在Rn中一个凸集D上的函数，如对任意实数(01)及任意x(1)，x(2)D，存在以下关系：fx(1)+(1-)x(2)f(x(1)+(1-)f(x(2)，f(x)为定义在凸集D上的一个凸函数。如式中把变为，则f(x)称为严格凸函数。如变为，f(x)称为凹函数。,概念,概念说明,对于任意x(1)，x(2)及01，由矢量运算法：x(k)=x(1)+（1-）x（2），则f(x(k)=fx(1)+(1-)x(2)，yc=f(x(1)+(1-)f(x(2)，显然f(x(k)yc，则f(x)为凸集D上的的凸函数。即fx(1)+(1-)x(2)f(x(1)+(1-)f(x(2),（2）凸函数的基本性质：,1).如f1(x),f2(x)为凸集D上的凸函数，对于任意实数a0，b0，f(x)=af1(x)+bf2(x)仍为D上的凸函数。2).如x(1)，x(2)为凸函数f(x)中的两个最小点，则其连线上的一切点都是f(x)的最小点。,（3）判别法：,1）判别法1：若f(x)在D1上具有连续一阶偏导数，而D为D1内部的一个凸集，则f(x)为D上的凸函数的充分必要条件为：对任意x(1)、x(2)D，恒有,（3）判别法：,2）判别法2（常用）：若f(x)在凸集D上存在二阶（偏）导数并连续，则f(x)在D上为凸函数的充分必要条件为：对于任意xD，f(x)的H(x)矩阵处处是半正定的。如H(x)对于任意xD皆为正定，则f(x)为D上的严格凸函数，反之不一定成立（充分条件）。如H(x)对于任意xD皆为负定，则f(x)为D上的严格凹函数。,举例,例2试判断函数f(x)（x12+x22）的凸性。解：由判别法2，只需求出H(x)矩阵是否为（半）正定。所以，,由可知H(X)处处负定，因此，f(x)为严格凹函数。,5结论,凸性把f(x)的局部极值与全域最优值联系起来。如果f(x)为凸函数，D为凸集，则f(x)的任意极值点（极值点不一定唯一，但极值是唯一的）即最优点。如果f(x)为严格凸函数，则最优点是唯一的。,3.3约束极值点存在条件,1).约束极值点：指在约束条件下求得的函数极值点，一般位于可行域D的边界上。2).判别方法：KT条件（库恩塔克即Kuhn-Tuker条件）对于约束优化问题：,判别方法：,KT条件:如果xk是一个局部约束极小点，则该点的目标函数梯度f(xk)可表示成该点各个起作用的约束面梯度gu(xk)、hv(xk)的线性组合，即式中u（u=1,2,q）、v(v=1,2,j)0，称为拉格朗日乘子（u不等于v）。,3).KT条件的几何意义,3).KT条件的几何意义,二维情况:在设计点xk处有2个起作用的约束。目标函数-f(xk)方向落在点xk两个约束函数梯度g1(xk)，g2(xk)方向组成的锥角内。则在该点附近邻域内，任何目标函数值比f(xk)更小的设计点都在可行域外，因此,xk是约束极值点，满足KT条件：f(xk)+1g1(xk)+2g2(xk)=0，且10，20。见教材P23图3.10,KT条件的几何意义,反之，如图（a）所示，f(xk)不在锥角内，则在xk点邻近的可行域内，存在有比f(xk)更小的设计点，因此，xk不是约束极值点，不满足KT条件。,KT条件的几何意义,如果在xk点只有一个起作用的约束，则有1）f(xk)与g(xk)不重合，则在xk邻近的可行域内存在比f(xk)值更小的点，xk不是约束极值点。2)f(xk)与g(xk)重合，则在xk点邻域内比f(xk)小的点均在可行域之外，因此，xk是约束极值点，且必定满足KT条件：f(xk)g(xk)=0，且0。,4).凸规划问题：,目标函数f(x)为凸函数，可行域D为凸集的优化问题。反之为非凸规划问题。对凸规划问题，局部极值点即是全域最优点。,非凸规划问题,对非凸规划问题，在D内可能2个或更多局部极小点（都满足KT条件）但其中只有一个点为约束最优点。,补充说明：,用KT条件只能判断局部约束极小点，不能判断全域域最优点。用KT条件检验约束极值点是指具有起作用约束的可行点。即检验点在约束边界上。如约束不起作用，尽管x是约束极值点，但不属于KT条件检验的范围。如右图。,举例,例3.3用KT条件证明f(x)=(x1-3)2+x22在不等式约束g1(x)=4-x12-x20，g2(x)=x20，g3(x)=x10条件下，为其约束最优点。证：（1）找出在xk点起作用的约束g1(xk)=4-4-0=0起作用g2(xk)=0起作用g3(xk)=20不起作用,举例,（2）求xk点有关梯度。,举例,（3）代入KT条件，求拉格朗日乘子f(xk)1g1(xk)2g2(xk)=0可写成线性方程组：-241=012=0解得1=2=0.50，非负，满足KT条件，因此点为约束极值点。由于f(x)为凸函数，可行域D为凸域，故为凸规划问题。,例题的几何描述,由于f(x)为凸函数，可行域D为凸域，因此，xk点是约束最优点。,补充说明,两种特殊情况：1）如果所有约束都不起作用，且点Xk满足不等式，则表明点Xk为约束极值点，但不能用K-T条件判断。2）如果点Xk不满足不等式，则表明点Xk不是可行点。,作业题：,1证明函数f(X)=6010 x14x2x12x22x1x2在D=x1,x2|(0，b0，问：（1）该函数是否存在极值？（2）若存在极值试确定它的极值点X*，判断它是极小还是极大。,作业题：,3已知约束优化问题minf(X)=4x1x23-12g(X)=10 x1x2310 x2x22340h(X)=25x12x22=0试用KT条件判别X=1.002,4.899T是否为其极值点。,作业题：,4.试判断函数的驻点的性质(即是否为极值点,极大,极小)。5.求函数的极