机械优化设计第二章(哈工大)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第二章 优化设计的数学基础,2-1,多元函数的方向导数和梯度,2-2多元函数的泰勒展开,2-,3,无约束优化问题的极值条件,2-,4,凸集、凸函数与凸规划,2-,5,等式约束优化问题的极值条件,2-,6,不等式约束优化问题的极值条件,1,1,、方向导数,二元函数,在,点处的,偏导数,的定义是：,二元函数,在,点处沿某一方向,的变化率，其定义为,方向导数,2-1,多元函数的方向导数和梯度,2,图,1,二维空间中的方向,偏导数与方向导数的关系,O,x,2,x,1,x,10,x,20,x,0,x,1,x,2,s,x,S,1,2,3,三元函数,在,点处沿s方向的方向导数,依次类推，即可得到,n,元函数在点,x,0,处沿,s,方向的方向导数,4,2,、二元函数的梯度,令,为函数,F,(,x,1,，,x,2,),在,x,0,点处的梯度,5,当梯度方向和,d,方向重合时，方向导数值最大，即梯度方向是函数值变化最快方向，而梯度的模就是函数值变化率的最大值。,梯度的模：,6,多元函数的梯度,7,多元函数的梯度的模：,函数的梯度方向,与函数的等值面相垂直,，也就是和等值面上过,x0,的一切曲线相垂直。,由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种,局部性质,。,8,例,1,：,求二次函数,在点,处的梯度。,解：,在点,处的梯度为：,9,例,2,：,试,求二次函数,在点,处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。,解：,则函数在 处的最速下降方向为,10,该方向上的单位向量为,新点,该点函数值,11,常用梯度公式：,注意：梯度为向量,二次型,12,在,点处的泰勒展开为：,其中,1,、,一元函数,2-,2,多元函数的泰勒展开,13,2,、二元函数,其中：,二元函数 在 点处的泰勒展开式为：,14,上式写成矩阵形式：,15,令,上式可写成,称为函数 在 点处的,海赛（,Hessian,）矩阵,参见教材例题,P30,16,海赛矩阵,是由函数 在点 处的二阶偏导数组成的方阵。由于函数的二次连续性，有：,所以 矩阵为,对阵方阵。,17,海赛矩阵,3,、多元函数,其中：梯度,泰勒展开式,18,若将函数的泰勒展开式只取到线性项，即取,则 是过点 和函数 所代表的超曲面相切的切平面。,若将函数的泰勒展开式取到二次项时，则得到二次函数形式，在线性代数中将二次齐次函数称为二次型。,矩阵形式,-,对称矩阵,19,当对任何非零向量,x,使,则二次型函数正定，,G,为正定矩阵。,20,海赛矩阵的特征：是实对称矩阵。,4,、海赛矩阵与正定,矩阵,正定,的充要条件：矩阵,G,的各阶顺序主子式为正，即,矩阵,负定,的充要条件：矩阵,G,的,奇数阶主子式,主子式,偶数阶主子式,海赛矩阵的正定性：,正定,-,为全局极小值点的充分条件,负定,-,为全局极大值点的充分条件,21,例,3,判定矩阵 是否正定？,解：,该对称矩阵的三个主子式依次为：,故可知矩阵,G,是正定的。,22,定理：,若二次函数 中,Q,正定，则它的等值面是同心椭球面族，且中心为,证明：,作变换 ，代入二次函数式中：,结论：,Q,为正定矩阵的二次型 的等值面是以 的同心椭球面族。原二次函数就是以 为中心的同心椭球面族，椭圆中心为极小值点。,23,例,4,把二次函数 化为矩阵向量形式并检验,Q,是否正定，如正定，试用公式,求这个函数的极小点。,解：,与题中函数比较各系数得：,由计算知,Q,正定，极小点,24,的梯度和,Hesse,矩阵。,解：因为,则,又因为：,故,Hesse,阵为：,例5：,求目标函数,25,1,、一元函数,对于可微的一元函数,判断在,处是否取得极值的过程：,则,为极小点。,逐次检验其更高阶导数的符号，开始不为零的导数阶数若为偶次，则为极值点，若为奇次，则为拐点。,则,为极大点。,2-,3,无约束优化问题的极值条件,26,2,、二元函数,定理,1,：,若二元可微函数 在,处取得极值的,必要条件,是：,即,凡满足上式的点称为函数的,驻点,（零向量）,27,如下图所示的二元函数，在,M,0,点虽有 和,是个驻点，但它不是极值点。,28,定理,2,：,若二元可微函数 在,的某个邻域取得极小值的,充分条件,是要求在该点附近的一切点均满足：,若函数存在连续的一阶及二阶偏导数，当满足,则泰勒展开式的函数增量近似式（略三阶以上高阶微量）为：,29,令,则,可见，函数增量的性态与,A,B,C,的值有关。可以证明，当满足以下条件时， 为极小值（证明略）。,此条件反映了函数在该点的海赛矩阵的各阶主子式均大于零（即正定）。,30,结论：,二元函数在某点取得,极小值,的,充分条件,是要求,该点处的海赛矩阵为正定,。,且,对于二元函数 在,处取得极值的,充分必要条件,是：,参见教材例题,P32,31,3,、多元函数,对于多元函数 若在,处取得,极值,，则,必要条件：,充分条件：,正定,或负定,32,当极值点,x*,能使,f(x*),在整个可行域中为最小值时，即在整个可行域中对任一,x,都有,f(x)=f(x*),则,x*,为,全域最优点（全域极小点）。,若,f(x*),为局部可行域中的极小值而非整个可行域的最小值时，则称,x*,为,局部最优点或相对最优点,。优化的目标是全域最优点。为了判断某个极值点是否为全域最优点，研究函数的凸性是必要的。,2-,4,凸集、凸函数与凸规划,33,函数的凸性表现为,单峰性,。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优亦是全域最优点。,为了研究函数的凸性，下面引入,凸集,的概念：,34,1,、凸集,如果对一切,及一切满足,的实数 ，,点 则称集合,为,凸集,，否则称为非凸集。,y,x,2,x,1,若,y,是,x,1,和,x,2,连线上的点，则有,整理后即得,图,2-,8,二维空间的凸集与非凸集,35,凸集的性质：,若,D,为凸集， 为一个实数，则集合 仍是凸集；,若,D,和,F,均为凸集，则其和（或并）仍是凸集；,任何一组凸集的积（或交）仍是凸集。,图,2-,9凸集的性质,36,2,、凸函数,具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为凸函数或单峰函数。其数学定义是：,设,f(x),为定义在,n,维欧式空间中的一个凸集,D,上的函数，如果对于任何实数 以及对,D,中任意两点,x,1,，,x,2,恒有：,则 为,D,上的凸函数，若不满足上式，则为凹函数。,如式中的等号去掉，则称其为严格凸函数。,37,凸函数的,几何意义,：在函数曲线上取任意两点连成一直线段，则该线段上任一点的纵坐标值必大于或等于该点处的原函数值。,38,凸函数的性质,1,）若,f(x),为定义在凸集,D,上的一个凸函数，对于任意实数,a0,，则,af(x),也是凸集,D,上的凸函数；,2,）定义在凸集,D,上的两个凸函数,f1(x),f2(x),，其和,f1(x)+f2(x),亦为该凸集上的一个凸函数；,3,）若,f1(x),f2(x),为定义在凸集,D,上的两个凸函数，,为两个任意正数，则 仍为,D,上的凸函数。,39,3,、凸性条件,（,1,）根据一阶导数（函数的梯度）来判断函数的凸性,设,f(x),为定义在凸集,R,上，且具有连续的一阶导数,的函数，则,f(x),在,R,上为凸函数的,充要条件,是对凸,集,R,内任意不同两点 、 ，下面不等式,恒成立。,40,（,2,）根据二阶导数（海赛矩阵,),来判断函数的凸性,设,f(x),为定义在凸集,R,上且具有连续二阶导数的函数，则,f(x),在,R,上为凸函数的,充要条件,为：,海赛矩阵在,R,上处处半正定。对于严格的凸函数，其充要条件为海赛矩阵为正定。,当海赛矩阵,G,的主子式,:,det(G),0,时，矩阵正定,det(G)0,时，矩阵半正定,det(G),0,时，矩阵负定,det(G)0,时，矩阵半负定,G(x*),正定， 是,x*,为全局极小值点的充分条件,；,G(x*),半正定,是,x*,为局部极小值点的充分条件；,G(x*),负定， 是,x*,为全局极大值点的充分条件；,G(x*),半负定,是,x*,为局部极大值点的充分条件,。,说明：,41,4,、凸规划,对于约束优化问题,若,、,都为凸函数，则称此问题为凸规划。,42,凸规划的性质：,2,）可行域 为凸集。,3,）凸规划的任何局部最优解就是全局最优解。,1,）若给定一点 ，则集合,为凸集。,43,不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。,注意：,44,等式约束优化问题：,求解等式约束化问题的理论基础是导出极值存在的条件。,2-,5,等式约束优化问题的极值条件,45,1,、消元法（降维法）,46,47,2,、拉格朗日乘子法（升维法）,思想,:,通过增加变量将等式约束化问题变成无约束化问题。,所以又称作,升维法,。,引入,拉格朗日乘子,，并构成一个,新的目标函数,拉格朗日函数,拉格朗日乘子,新目标函数的极值的,必要条件：,48,49,库恩,塔克条件（,K-T,条件）,不等式约束的多元函数极值的必要条件是著名的,库恩,塔克（,Kuhn-Tucker,）条件,它是非线性优化问题的重要理论。,为了便于理解库恩,塔克条件，首先分析一元函数在给定区间的极值条件。,2-,6,不等式约束优化问题的极值条件,50,1,、一元函数在给定区间上的极值条件,一元函数,f(x),在区间,a,b,的极值问题，可表示为：,求解思想,:,引入松弛变量使不等式约束变成等式约束，再利用拉格朗日乘子法求解等式约束的极值问题。,51,这样可以转化为拉格朗日函数：,是对应于不等式约束的拉格朗日乘子，,其值均为非负的。,设 为松弛变量，则上两个不等式可写为如下两个等式：,52,对于一元函数,在给定区间,上的极值条件，可完整的表示为：,结论：,53,从以上分析可以看出，对应于不起作用的约束的拉格朗日乘子,取零值,，因此可以引入起作用约束的下标集合。,一元函数在给定区间的极值条件，可以改写为：,极值条件中只考虑起作用的约束和相应的乘子。,54,2,、库恩,塔克条件,库恩,塔克条件（,K-T,条件）可表述为：,对于多元函数不等式的约束优化问题：,55,库恩,塔克条件表明：,如点 是函数 的极值点，要么 （此时 ）或者目标函数的负梯度等于起作用约束梯度的非负线性组合 （此时 ）。,56,库恩,塔克条件的,几何意义,：在约束极小值点 处，函数 的负梯度一定能表示成起作用约束在该点梯度（法向量）的非负线性组合。,57,58,O,x,1,x,2,极值点处于等值线的中心,极值点处于两个约束曲线的交点上,x,g,1,(,x,),0,g,2,(,x,),0,g,3,(,x,),0,O,x,1,x,2,x,g,1,(,x,),0,g,2,(,x,),0,起作用约束：,59,从图中可以看出，,处在,和,即线性组合的系数为正，是在,取得极值的必要条件。,角锥之内，,x,1,x,2,O,g,2,(,x,)=0,g,1,(,x,)=0,F,(,x,)=,C,g,2,(,x,k,),g,1,(,x,k,),F,(,x,k,),x,k,可行域,点,x,k,处的切平面,x,1,x,2,O,g,2,(,x,)=0,g,1,(,x,)=0,F,(,x,)=,C,g,2,(,x,k,),g,1,(,x,k,),F,(,x,k,),x,k,可行域,点,x,k,处的切平面,(a),(b),60,同时具有等式和不等式约束的优化问题：,库恩,塔克条件（,K-T,条件）：,61,库恩,塔克条件是多元函数取得约束极值的,必要条件,，可用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。,对于目标函数和约束函数都是凸函数的情况，符合,K-T,条件的点一定是全局最优点。,这种情况,K-T,条件即为多元函数取得约束极值的,充分必要条件,。,62,例,库恩,塔克（,K-T,）条件应用举例,判断 是否为约束最优点？,K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。,63,解：,（,1,）当前点 为可行点，因满足约束条件,（,2,）在 起作用约束为 ，因,（,3,）求各函数梯度：,64,（,4,）求拉格朗日乘子,由于拉格朗日乘子均为非负，说明,是一个局部最优点，因为它满足,K-T,条件。,65,图13 应用库恩-塔克条件寻找约束极值点,66,END,67,