《基本知识简介(2)》由会员分享，可在线阅读，更多相关《基本知识简介(2)（53页珍藏版）》请在金锄头文库上搜索。
1、工程优化设计中的数学方法工程优化设计中的数学方法工程优化设计中的数学方法工程优化设计中的数学方法硕士研究生课程硕士研究生课程硕士研究生课程硕士研究生课程理学院数学系：穆学文理学院数学系：穆学文 Tel:88207669 E-mail:?下载课件邮箱：下载课件邮箱： mxw_?密码：密码：654321第二章 基础知识第二章 基础知识?多元函数及其导数多元函数及其导数?等高线等高线?二元函数二元函数?多元函数的极值多元函数的极值?凸集、凸函数和凸规划凸集、凸函数和凸规划?重要的不等式重要的不等式?下降迭代算法及其收敛性下降迭代算法及其收敛性4 多元函数的极值多元函数的极值全局极小点可能在某个局部极
2、小点达到，也全局极小点可能在某个局部极小点达到，也 可能在边界达到。可能在边界达到。我们希望知道的当然是全局极小点，而到目前我们希望知道的当然是全局极小点，而到目前 为止的一些最优化算法却基本上是求局部极小值为止的一些最优化算法却基本上是求局部极小值 点的。因此一般要先求出所有局部极小值点，再点的。因此一般要先求出所有局部极小值点，再 从中找出全局极小点。从中找出全局极小点。为了求出函数的局部极小值点，我们首先希 望知道函数为了求出函数的局部极小值点，我们首先希 望知道函数 f 在局部极小点处满足什么条件？以 及满足什么条件的点是局部极小点。在局部极小点处满足什么条件？以 及满足什么条件的点是
3、局部极小点。定理定理3：设具有连续的一阶偏导 数，若是的局部极小点，且为可行集设具有连续的一阶偏导 数，若是的局部极小点，且为可行集 D 的 内点的 内点, 则则1:,nfDRR()*0.f x=*xf注意：定理中条件仅为必要的，而不是充分的。注意：定理中条件仅为必要的，而不是充分的。证明证明:设 为任意单位向量设 为任意单位向量, 因为是的局部极小点。 由定义知：当因为是的局部极小点。 由定义知：当, 即时，总有：即时，总有：*x0, ()*,xte N x+ e( )f xtnpR ()22*0Tpf xpp()*0f x=( )( )()( )()()()222*2*11022Tf xf
4、 xx xf xx xx xx xo x x=+证明：因正定，则，使对， 均有：将证明：因正定，则，使对， 均有：将 f 在处按在处按Taylor公式展开。， 有：当公式展开。， 有：当 x 充分接近时，上式左端的符号取 决于右端的一项（为正）。故充分接近时，上式左端的符号取 决于右端的一项（为正）。故()*x x x( )()*.fxfx( )0f xQxb=+=*1xQ b= *1xQ b= ()2*f xQ=( )1 2TTfxx Qxb xC=+*1xQ b= 推论推论1：对于具有对称正定矩阵的二次函数：是它的唯一极小点。证明对于具有对称正定矩阵的二次函数：是它的唯一极小点。证明: 求
5、此二次函数的驻点，由知有唯一驻点，而这点处的求此二次函数的驻点，由知有唯一驻点，而这点处的Hesse 阵正定。 故由定理又知：是其唯一极小点。阵正定。 故由定理又知：是其唯一极小点。推论推论2：若多元函数在其极小点处的若多元函数在其极小点处的 Hesse 阵正阵正定，则它在这个极小点附近的等值面近似地呈定，则它在这个极小点附近的等值面近似地呈 现为同心椭球面族。现为同心椭球面族。证明：设是多元函数证明：设是多元函数 f 的极小点。并设是充分 靠近极小点的一个等值面，即充分小。将 在点展开为的极小点。并设是充分 靠近极小点的一个等值面，即充分小。将 在点展开为Taylor公式。因为极小值点。 又
6、是高阶无穷小量。省略。则有：这是等值面的一个近似曲面。 由于假设正定，则是以为中心的椭球面方程。公式。因为极小值点。 又是高阶无穷小量。省略。则有：这是等值面的一个近似曲面。 由于假设正定，则是以为中心的椭球面方程。*x*x*x*x*x*xx( )()() ()()()()()2*2*102TTfxfxfxxxxxfxxxxx=+ +()*0f x=2*0()xx()()()()( )*2*1.2Tfxxxfxxxfxr+=()2*f x()()()()*2*1.2Tfxxxfxxxr+=( )f xr= ( )f x( )f xr=可行方向：可行方向：设，若对以点为始点的向量均位于的内部，则
7、称为点的一个可行方向。设，若对以点为始点的向量均位于的内部，则称为点的一个可行方向。,nnxDRhR0,(0, )xhDhx注意：注意：1. 如果为的内点，则任何方向都是可行方 向； 若为边界点，则只有一部分为可行方向如果为的内点，则任何方向都是可行方 向； 若为边界点，则只有一部分为可行方向2. 如果为的极小点如果为的极小点, 则在处沿任何方 向，函数值均不减少，即则在处沿任何方 向，函数值均不减少，即xDh xD*x( )f x( )f x*x h()( )01Tfhf xhh=定理定理5：设设,如果二阶可微， 且对于在点的任何可行方向，都有， 并有，则为的严格局部极小值点。如果二阶可微，
8、 且对于在点的任何可行方向，都有， 并有，则为的严格局部极小值点。1*:,nfDR DRxD( )f x*xh*()0Thf x2*()0f x*x( )f x5 凸集、凸函数和凸规划凸集、凸函数和凸规划5.1 凸集凸集定义定义4：设，恒有称集合为凸集 。设，恒有称集合为凸集 。nDR12,0,1 ,x xD12(1),0,1 ,xxD+D?凸集的几何特征：连接形体中任意两点的凸集的几何特征：连接形体中任意两点的直线 段直线 段，都在该形体之中。，都在该形体之中。?空集和只有一个元素的集合也是凸集。空集和只有一个元素的集合也是凸集。?三角形，矩形，圆，球，是凸的三角形，矩形，圆，球，是凸的.?
9、例例1: 证明集合证明集合 S = xAx = b 是凸集。其中是凸集。其中A为为 m n矩阵，矩阵，b为为m维向量。维向量。?例例2: 集合是凸集集合是凸集, 称为超平 面，称为超平 面，c为为n维向量。维向量。?例例3：邻域是凸集。：邻域是凸集。,nTHx xRc xb=()00,|,0N xxxx = 0 有有 x C, 则称则称 C 是以是以 0 为顶点的锥。如果为顶点的锥。如果 C 还是凸集，则称为凸 锥。还是凸集，则称为凸 锥。?集合集合 0 、Rn 是凸锥。是凸锥。0定义7：定义7：设设 x(1), x(2), , x(m) RnRn, , jj 0 , 那么称那么称 j x(j
10、) 为为x(1), x(2), , x(m)的的非负线性组合。非负线性组合。命题：命题：C是凸锥是凸锥C中任意有限点的非负线性组合中任意有限点的非负线性组合 属于属于S证明参见书中定理证明参见书中定理2.9的证明的证明5.2 凸函数5.2 凸函数5.2.1 凸函数凸函数定义定义7: 设集合设集合 S Rn 为凸集，函数为凸集，函数 f :SR, 若 若 x(1), x(2) S, ( 0 , 1 ) ，均有，均有f ( x(1)(1- ) x(2) ) f (x(1)+(1- ) f (x(2) ，则称则称 f(x) 为凸集为凸集 S 上的凸函数。若进一步有上面不上的凸函数。若进一步有上面不
11、等式以严格不等式成立，则称等式以严格不等式成立，则称 f(x) 为凸集为凸集 S 上的严上的严 格凸函数。格凸函数。?当当- f(x) 为凸函数（严格凸函数）时，则称为凸函数（严格凸函数）时，则称 f(x) 为凹 函数（严格凹函数）。为凹 函数（严格凹函数）。严格凸函数凸函数严格凹函数严格凸函数凸函数严格凹函数定理定理6： f (x) 为凸集为凸集S S 上的凸函数上的凸函数S S 上任 意有限点的凸组合的函数值不大于各点函数值 的凸组合。上任 意有限点的凸组合的函数值不大于各点函数值 的凸组合。证明：参见文中定理2.9的证明。证明：参见文中定理2.9的证明。思考：设思考：设f1, f2是凸函
12、数，是凸函数，?设设 1, 2 0, 1f1+ 2f2, 1f1 - 2f2是否凸函数？是否凸函数？?f(x)= max f1(x) , f2 (x) , g(x)= min f1(x) , f2 (x) 是否凸函数？是否凸函数？题示：题示： 1f1+ 2f2，f(x)= max f1(x) , f2 (x) 是是, 可以证明可以证明. 1f1 - 2f2，g(x)= min f1(x) , f2 (x) 举反例举反例.例3：设二次函数 （1）：若为半定矩阵，在中为凸函数 （2）：若为正定矩阵，在中为严格凸函数 证明：留做作业 提示：定义例3：设二次函数 （1）：若为半定矩阵，在中为凸函数 （
13、2）：若为正定矩阵，在中为严格凸函数 证明：留做作业 提示：定义( )1,2TTTnfxx Qxb xc QQxR=+=( )1,2TTTnfxx Qxb xc QQxR=+=Q( )f xnR( )f xnRQ5.2.2凸函数的判定定理凸函数的判定定理定理定理7：设设S Rn为非空凸集，函数为非空凸集，函数 f :SR ，f 在在 S 上可微，则上可微，则 f 在在 S 上为凸函数上为凸函数(严格凸函数严格凸函数) 任意 任意x，y S，恒有，恒有f (y) f (x)+ f T(x)(y-x) f (y) f (x)+ f T(x)(y-x)（x不等于不等于 y）证明证明:见书中定理见书中
14、定理2.11定理定理8: 设设S Rn为非空开凸集，函数为非空开凸集，函数 f :SR , f 在在 S 上二次可微，则上二次可微，则 a) f 在在S上为凸函数 上为凸函数 x S，2f (x) 半正定；半正定； b) 若 若 x S，2f (x) 正定，则正定，则f在在S上为严格凸函 数。（逆定理不成立）上为严格凸函 数。（逆定理不成立）证明证明:由定理由定理7 和多元函数的泰勒展开式和多元函数的泰勒展开式.5.3 凸规划凸规划定义定义8: 考虑如下非线性规划考虑如下非线性规划( ) ( )min. .0.1,2,if xstgxim=L当都是凸函数时当都是凸函数时,称规划为凸规划称规划为
15、凸规划.( ),( )(1,2,)if xg x im=L( )P( )P注注: 1. 非线性规划的局部最优解不一定是整体最优解非线性规划的局部最优解不一定是整体最优解,其可行解 和最优解集也不一定是凸集其可行解 和最优解集也不一定是凸集,甚至不是连通集甚至不是连通集.如果是凸规划的话如果是凸规划的话 ,就有很多好的性质就有很多好的性质. 2. 如果如果, 都是凹函数时都是凹函数时,非线性规 划有着另外一些好的性质非线性规 划有着另外一些好的性质,但无法跟凸规划相比但无法跟凸规划相比.只是比一般的规 划要多一些解法只是比一般的规 划要多一些解法.( ),( )(1,2,)if xg x im=L凸规划的一些性质凸规划的一些性质凸规划的一些性质凸规划的一些性质定理定理9: 设为凸规划，则（设为凸规划，则（1）规划的容许解集合为凸集；（）
