工程优化方法 第二章-2

第二章基本概念和理论基础本章主要内容：§1多元函数的梯度及其Hesse矩阵§2多元函数的极值及其判别条件§3等高线§4多元函数分析（二次函数）§5凸集、凸函数、凸规划§6几个重要的不等式凸集、凸函数和凸规划''()0fx问题（极小值点和最小值点之间的关系）：设f(x)定义在D内，f(x*)为极小值，这是一局部概念，即在x*的邻域内，f(x*)最小。若x*为f(x)的最小值点，则x*为f(x)的极小值点。反过来不一定成立。一元函数有结论：若f(x)在区间[a,b]上是凸的，则x*是f(x)的极小值点等价于x*是f(x)的最小值。且由微分学知：若，则f(x)是凸的。为研究多元函数的极值与最值的关系，下面介绍多元函数凸性。12,,0,1,xxD12(1),0,1,xxDD,nDR规定：空集和单元素集也是凸集。三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸的。等价定义（凸集）：设凸集与性质定义（凸集）：若集合中任意两点的连线都属于，则称为凸集。因为两点连线上任一点可以表示为12(1),0,1.xxx12,xxDDD称集合为凸集。恒有凸集：在点集中任取两点，则其连线仍在其中。即没有凹入的部分；没有空洞。⑴⑵⑶⑷⑸⑹ABCD凸集与性质例1:证明集合S={x∣Ax=b}是凸集。其中A为mn矩阵，b为m维向量。0,1,1212((1))(1)(1),AxxAxAxbbb凸集与性质12,,xxS证明:12,,AxbAxb即12(1),xxS所以即S是凸集。{,}nTHxxRcxb例2:集合是凸集,称为超平面，c为n维向量。例3：邻域00,|,0Nxxxx是凸集。定义：设那么称是的凸组合。121,,...,,0,1,mmniiixxxR性质2：S是凸集S中任意有限个点的凸组合属于S。证明：见书中定理2.9(P23).提示：充分性显然。必要性用数学归纳法。1miiix12,,...,mxxx凸集与性质性质1：设是凸集，则也是凸集。,,ABABAB,nABR:{:,},:{:,}.ABabaAbBABabaAbB注：不一定是凸集。AB定义（凸包）：包含集合D的所有凸集的交集称为D的凸包，记作Co(D)或者H(D).注：由性质1可知，Co(D)是包含D的最小凸集。nDR0凸集与性质xDxDD0定义（凸锥）：设，如果对任意的及所有的，都有，则称是一个锥。一个同时是凸集的锥，称为凸锥。多胞形：有限个点的凸包12{,,...,}mcoxxx由一元函数的几何图形知：f(x)是凸函数，任意给定曲线上两点A，B，则弦AB在与弧AB之上，用数学式子表示：凸函数211121fxfxyfxxxxx211221xxfxxxfxxx221xxxx，1211xxxx，121xxx121yfxfx121fxyfxfx121211fxxfxfx弦AB的方程：令则上式可写为：所以：定义（凸函数）:设集合DRn为凸集，函数f:DR,若x,yD,(0,1)，均有f(x+(1-)y)≤f(x)+(1-)f(y)，则称f(x)为凸集D上的凸函数。若进一步有上面不等式以严格不等式成立，则称f(x)为凸集D上的严格凸函数。•当-f(x)为凸函数(严格凸函数)时，则称f(x)为凹函数(严格凹函数)。严格凸函数凸函数严格凹函数凸函数----推广到多元函数,,TTnfxxAXAAxR12,,0,1nxxR，121211fxxfxfx例：设1)若A半正定，则在上是凸函数；2)若A正定，则在上是严格凸函数。证明:fxnRnR凸函数----推广到多元函数12121122111TTTxxAxxxAxxAx111222(1)21(1)TTTxAxxAxxAx111222(1)2TTTxAxxAxxAx11122221(1)TTTTxAxxAxxAxxAx12121TxxAxxfx00AA半正定正定性质2：设f1,f2是凸集D上的凸函数，1)设a,b0,则af1+bf2是凸函数；2)f(x)=max{f1(x),f2(x)}是凸函数。思考：af1-bf2是否是凸函数？g(x)=min{f1(x),f2(x)}是否是凸函数？凸函数的性质性质1：f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。证明参见文中定理2.10的证明。定理(一阶条件):设DRn为非空凸集，函数f:DR在D上可微，则(1)f在D上为凸函数任意x，yD，恒有f(y)≥f(x)+fT(x)(y-x)(1)(2)f在D上为严格凸函数任意x≠yD，恒有f(y)f(x)+fT(x)(y-x).(2)证明:见书中定理2.11(P27)凸函数的判定定理定理5（二阶条件）:设DRn为含有内点的非空凸集，函数f:DR在D上二次可微，则a)f在D上为凸函数xD，2f(x)半正定；b)若xD，2f(x)正定，则f在D上为严格凸函数。证明:见书中定理2.12（P28）由一阶条件和多元函数的泰勒展开式可证。回忆：一个矩阵半正定充要条件是所有主子式非负；一个矩阵正定充要条件是所有顺序主子式为正。凸函数的判定定理例：设二次函数(1)：若为半定矩阵，在中为凸函数；(2)：若为正定矩阵，在中为严格凸函数。例：判断f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函数？的顺序主子式都是正的，所以正定，因此f(x)在凸集D上是严格凸函数。2106()610fxTfxxAxA()fxnRnR()fxA凸函数的判定定理22211121112(1)()(1)()xxxx221112()()0xx01,20.221112()()0xx211()gxx222()gxx2212()+gxxx由于故证明为凸函数。也是凸函数。根据性质2，为凸函数。2222211111212()2()()0xxxx看下述各式是否成立：12,x11x证明：首先用定义证明是凸函数，即对任意和2212()fxxx例:试证明为凹函数。或即显然，不管和取什么值，总有11x12x211()gxx2212()fxxx为凹函数。因此从而用同样的方法可以证明用一阶条件证明只需证TT1212(,),(,),yyyxxx()()()Tfyfxfxyx11222212121222(22)yxyyxxxxyx任意选取两点222212121112222()2()yyxxxyxxyx或222211112222(2)(2)0yyxxyyxx或221122()()0yxyx或不管y1、y2、x1、x2取什么值，上式均成立，从而得证。22221212(),()fyyyfxxx2212()fxxx是凹函数，要证122()2xfxx2212()fxxx例:试证明为凹函数。1212()()2,2,fxfxxxxx()fx-f(x)的海赛矩阵处处负定，故为(严格)凹函数。下面用二阶条件证明:由于222212()()20,2,fxfxxx221221()()0,fxfxxxxx2002H2212()fxxx例:试证明为凹函数。定义（凸规划）:考虑如下非线性规划当都是凸函数时,称规划为凸规划(),()(1,2,,)ifxgxim(1)凸规划min(1)..0,1,2,,ifxstgxim性质1:设(1)为凸规划，则i)(1)的可行集R是凸集；ii)(1)的最优解集是凸集；iii)(1)的任何局部极小点都是全局极小点。证明：见书中定理2.13.性质2:设(1)为凸规划，若f(x)在非空可行集R上是严格凸函数，则(1)的全局极小点是唯一的。证明：见书中定理2.14.注:非线性规划的局部最优解不一定是整体最优解,其可行解和最优解集也不一定是凸集,甚至不是连通集.如果是凸规划,就有很多好的性质。凸规划的性质一个凸集有非空的相对内部；一个凸集是连通的并且在任意点具有可行方向；一个凸函数的局部极小点都是全局极小点；一个凸函数是连续的并且具有良好的可微性。为什么凸在最优化中如此特殊课后作业P382.192.20(1,3)2.282.29第二章基本概念和理论基础本章主要内容：§1多元函数的梯度及其Hesse矩阵§2多元函数的极值及其判别条件§3等高线§4多元函数分析（二次函数）§5凸集、凸函数、凸规划§6几个重要的不等式向量运算：x,yRnx,y的内积：x,y=xTy=xiyi=x1y1+x2y2+…+xnynx,y的距离：‖x-y‖=[(x-y)T(x-y)](1/2)x的长度：‖x‖=[xTx](1/2)三角不等式：‖x+y‖≤‖x‖+‖y‖定理（Cauchy-Schwarz不等式）重要的不等式定理1设A为n阶对称正定矩阵，则，恒有等号成立当且仅当x与线性相关;,nxyR2-1,,,(1)xyxAxyAy1Ay等式成立当且仅当x与y线性相关。2,,,xyxxyy,(2)nxyR,xy=AI当时其中表示向量的内积。定理3：设A为n阶对称正定矩阵，m与M分别为A的最小与最大特征值，则，恒有1,,xAxxAx定理2：设A为n阶对称正定矩阵，m与M分别为A的最小与最大特征值，则，恒有,0nxRx220,mxxAxMx,0nxRx重要的不等式221110,xxAxxMm1/M与1/m分别为A-1的最小与最大特征值2-1,,,,,(1)xyxAxyAyxy22(),4mMxxmM2,xxmaxixx11niixx12221niixx11nppipixx12TAxxAx范数（A正定）椭球范数范数范数范数l1l2lpl范数----向量范数nxR定义1：方阵A的范数是指与A相关联并记做的一个非负数，它具有下列性质：a)对于都有，而时；b)对于任意，都有；c)；d)；若还进一步满足：则称之为与向量范数相协调（相容）的方阵范数.kAkA0AABABABABppAxAx0A0A0AkRpA范数----矩阵范数定义2:设与是上的两个范数，若存在，使得，则称范数与是等价的。容易证明：其中是的最大特征值，而是的最小特征值。12,012,nxRxxx212xxnx2xxnx1xxnx1211xxxn122nAxxx1AnRnAnR范数----范数等价中所有向量范数均等价。Cauchy-Schwarz不等式当且仅当与线性相关时，等式成立。Txyxyxy关于范数的几个重要不等式定理（Cauchy-Schwarz不等式）2,,,xyxxyy,(2)nxyR等式成立当且仅当x与y线性相关。,=Txyxy2,=xxx当且仅当与线性相关时，等式成立。Txyxyxy关于范数的几个重要不等式1/21/2,AxAxyAy正定，取取定理4：设A是正定矩阵