第二章优化设计的数学基础.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,方向导数和偏导数之间的关系，从下述推导可知,类似的，一个三元函数 在 点处沿,d,方向的方向导数和偏导数的关系如下所示，见图,2-2,类似的，一个,n,元函数 在 点处沿,d,方向的方向导数,其中的,cos,i,为,d,方向和坐标轴,x,i,方向之间夹角的余弦。,2,、二元函数的梯度,令,称其为函数,f,(,x,1,x,2,),在,x,0,点的梯度。,设,为,d,方向的单位向量，则可得：,例,2-1,求二元函数,在,x,0,=0 0,T,处函数变化率最大的方向和数值,。,解：由于函数变化率最大的方向是梯度方向，这里用单位向量,p,表示，函数变化率最大的数值是梯度的模,f,(,x,0,),。求,f,(,x,1,x,2,),在,x,0,点处的梯度方向和数值，计算 如下,三、向多元函数的推广,函数,f,(,x,1,x,2,，,x,n,),在,x,0,(,x,1,x,2,，,x,n,),处的梯度可定义为,函数,f,(,x,1,x,2,，,x,n,),在,x,0,处沿,d,的方向导数可表示为,d,方向上的单位向量,梯度,f,(,x,0,),的模为,梯度方向单位向量为 ，它与函数等值面,f,(,x,)=c,相垂直，也就是和等值面上过,x,0,的一切曲面相垂直，如图,2-5,所示。,2.2,多元函数的泰勒（,Taylor),展开式,多元函数的泰勒,(Taylor),展开在优化方法中十分重要，许多方法及其收敛性证明都是从它出发的。,2.3,无约束优化问题的极值条件,一、一元函数极值条件,对于连续可微的一元函数,f,(,x,),如在,x,*,点有极值，其必要条件为：,f,(,x,*,),=0,若,x,*,为有极小值点，其充分条件为：,f,”,(,x,*,),0,若,x,*,为有极大值点，其充分条件为：,f,”,(,x*,),0,2.4,凸集与凸函数与凸规划,2.4.1,凸集与非凸集,2.5,等式约束优化问题的极值条件,对于等式约束优化问题：,min,f,(,x,),s.t.,h,k,(,x,)=0(,k,=1,2,m,),需要导出极值存在的条件。,数学上有两种处理方法：,消元法（降维法）,拉格朗日乘子法（升维法）,一、消元法,1,）二元函数只有一个等式约束,min,f,(,x,1,，,x,2,),s.t.,h,(,x,1,，,x,2,)=0,处理方法：将,x,1,表示为,x,1,=,(,x,2,),并代入目标函数中消去,x,1,变成一元函数,F,(,x,2,),则等式约束优化问题变为无约束优化问题。目标函数二维变一维,故称降维法。,2,）,n,维情况,min,f,(,x,1,，,x,2,，,，,x,n,),s.t.,h,k,(,x,1,，,x,2,，,，,x,n,)=0(,k,=1,2,l,),由,l,个约束方程将,n,个变量中的前,l,个变量用其余,n-l,个变量表示，有,x,1,=,(,x,l,+1,x,l,+2,x,n,),x,2,=,(,x,l,+1,x,l,+2,x,n,),x,n,=,(,x,l,+1,x,l,+2,x,n,),将这些函数关系代入到目标函数中，得到只含有,x,l,+1,x,l,+2,x,n,共,n,-,l,个变量的函数,F,(,x,l,+1,x,l,+2,x,n,),从而利用无约束优化问题的极值条件求解。（,因为将,l,个约束方程联立往往求不出解来，,实际上难于求解）,二、拉格朗日乘子法,通过增加变量将等式约束优化问题变成无约束优化问题。,对于,min,f,(,x,),s.t.,h,k,(,x,)=0(,k,=1,2,l,),在极值点,x,*,处有,(,k,=1,2,l,),令,可通过其中的,l,个方程,(a),来求解,l,个待定系数,1,，,2,，,l,，,使得,l,个变量的微分,d,x,1,d,x,2,，,d,x,l,的系数全为零。于是得到,则有,(b),(,j,=,l,+1,l,+2,n,),式（,a),(b),及等式约束条件,h,k,(,x,)=0(,k,=1,2,l,),就是点,x,达到约束极值的必要条件。,式（,a),(b),可以合并写成,(,i,=1,2,n,),（,c,）,令,式中 待定系数,k,称为拉格朗日乘子，,F,(,x,),称为拉格朗日函数。本方法称为拉格朗日乘子法。,把,F,(,x,),作为一个新的无约束条件的目标函数来求解它的极值点，所得结果就是满足约束条件的原目标函数的极值点。自,F,(,x,),具有极值的必要条件：,可得,l,+,n,个方程。由这些方程组求得函数,f,(x),的极值点,x,*=,x,1,*,x,2,*,x,l,*,T.,例,2-4,用拉格朗日乘子法计算极值点坐标,f,(,x,1,，,x2,)=4,x,1,2,+5,x,2,2,s.t.,h,(,x,1,，,x,2)=2,x,1,+3,x,2,-6=0,解：,F,(,x,)=,4,x,1,2,+5,x,2,2,+,(2,x,1,+3,x,2,-6),F,x,1,=8x,1,+2,=0,x,1,=-,/4,F,x,2,=,10,x,2,+,3,=0,x,2,=-,3,/10,F,=,2,x,1,+3,x,2,-6=0,=-30/7,所以得,x,1,=,1.071,，,x,2,=,1.286,此即为所求极值点,x,*.,2.6,不等式约束优化问题的极值条件,不等式约束的多元函数极值的必要条件是库恩,-,塔克（,Kuhn-Tucher),条件，是非线性理论的重要基础。,一、一元函数在给定区间上的极值条件,一元函数在给定区间,a,b,上的极值问题，可写成如下的不等式约束问题,min,f,(,x,),s.t.g,1,(,x,)=,a,-,x,0,g,2,(,x,)=,x,-,b,0,采用拉格朗日乘子法，将上述两个不等式约束变为等式约束,h,1,(,x,a,1,)=,g,1,(,x,)+,a,1,2,=,a,-,x,+,a,1,2,h,2,(,x,b,1,)=,g,2,(,x,)+,b,1,2,=,x,-,b,+,b,1,2,并得到拉格朗日函数,F,(,x,a,1,b,1,1,2,)=,f,(,x,)+,1,h,1,(,x,a,1,)+,2,h,2,(,x,b,1,),1,2,为对应于不等式约束条件的拉格朗日乘子，,1,0,2,0,根据拉格朗日乘子法，此问题的极值条件是,分析,即,1,，,g,1,(,x,),二者必有一个等于,0,，因此可以写成,1,g,1,(,x,)=0,。,同样对于，,2,b,1,=0,进行分析可得,因此可以写成,2,g,2,(,x,)=0,。,于是，对于一元函数,f,(,x,),在给定区间上的极值条件，可以完整地表示为,这样的分析方法可以推广到二元甚至多元函数不等式约束优化问题上去，从而给出著名的库恩一塔克条件。,(a),对于一元函数,f,(,x,),在给定区间,a,b,上的极值条件，式,(a),中的第一式可简化为,分析极值点,x,*,在区间,a,b,中的位置，可能出现,3,种情况，如图,2-11,所示。,这和如图,2-11,所示的从几何概念分析的结果完全一致。,由以上分析可知，对应于不起作用约束的拉格朗日乘子取零值。因此可以引入起作用约束的下标集合,J,(,x,)=,j,|,g,j,(,x,)=0,j,=1,2,。,当,a,x,*0,2,0,。此为目标函数在两个起作用约束作用下使,x,*,成为条件极值点的必要条件。,对于同时具有等式和不等式约束的优化问题：,min,f,(,x,),s.t.,g,j,(,x,),0(,j,=1,2,m,),h,k,(,x,)=0(,k,=1,2,l,),库恩,-,塔克条件可以表示为,注意，对应于等式约束的拉格朗日乘子，没有非负要求。,例题,2.5,设约束优化问题,s.t.,它的当前迭代点为 ，,用,K-T,条件判别它是否为约束最优点。,