20112第二章 优化设计的数学基础new

第二章优化设计的数学基础220102201002120102011001,,lim,,lim2010xxxfxxxfxfxxxfxxxfxfxxxx01xxfdxxfxxxxfdfdx20102201100,,lim02.1多元函数的方向导数与梯度1、方向导数一个二元函数在处的偏导数定义为而和分别是函数在x0点处沿坐标轴x1和x2方向的变化率。因此函数在点处沿某一方向d的变化率如图2-1所示，其定义应为称其为该函数沿此方向的方向导数。据此，偏导数、也可以看成是该函数分别沿x1和x2方向的方向导数。所以方向导数是偏导数概念的推广，偏导数是方向导数特例。01xxf21,xxf20100,xxx01xxf21,xxf21,xxf20100,xxx02xxf01xxf02xxf220102201002120102011001,,lim,,lim2010xxxfxxxfxfxxxfxxxfxfxxxxdxxfxxxxfdfdx20102201100,,lim022112220110220110011201020110020102201100coscos,,lim,,lim,,lim000xxdddxxfxfdxxxxxfxxxxfdxxxxfxxxfdxxfxxxxfdf方向导数和偏导数之间的关系，从下述推导可知332211coscoscos0000xxxxxfxfxfdf类似的，一个三元函数在点处沿d方向的方向导数和偏导数的关系如下所示，见图2-2321,,xxxf30,20,100xxxx类似的，一个n元函数在点处沿d方向的方向导数n21,,xxxf，0xixniinxxxxxfxfxfxfdfcoscoscoscos000001n2211其中的cosi为d方向和坐标轴xi方向之间夹角的余弦。2、二元函数的梯度21212211coscoscoscos0000xxxxxfxfxfxfdfTxxxfxfxfxfxf002121021coscosddxfdfTx00令称其为函数f(x1,x2)在x0点的梯度。设为d方向的单位向量，则可得：`例2-1求二元函数在x0=[00]T处函数变化率最大的方向和数值。524,21222121xxxxxxf2422420021210xxxxxfxfxf52242222210xfxfxf解：由于函数变化率最大的方向是梯度方向，这里用单位向量p表示，函数变化率最大的数值是梯度的模f(x0)。求f(x1,x2)在x0点处的梯度方向和数值，计算如下5152522400xfxfp三、向多元函数的推广函数f(x1,x2，,xn)在x0(x1,x2，,xn)处的梯度可定义为函数f(x1,x2，,xn)在x0处沿d的方向导数可表示为d方向上的单位向量梯度f(x0)的模为梯度方向单位向量为，它与函数等值面f(x)=c相垂直，也就是和等值面上过x0的一切曲面相垂直，如图2-5所示。Txnxnxfxfxfxfxfxfxf0021210dfxfdxfxfdfTixniix,coscos00100ndcoscoscos21211200nixixfxf00xfxfp2.2多元函数的泰勒（Taylor)展开式多元函数的泰勒(Taylor)展开在优化方法中十分重要，许多方法及其收敛性证明都是从它出发的。2.3无约束优化问题的极值条件一、一元函数极值条件对于连续可微的一元函数f(x),如在x*点有极值，其必要条件为：f’(x*)=0若x*为有极小值点，其充分条件为：f”(x*)0若x*为有极大值点，其充分条件为：f”(x*)02.4凸集与凸函数与凸规划2.4.1凸集与非凸集2.5等式约束优化问题的极值条件对于等式约束优化问题：minf(x)s.t.hk(x)=0(k=1,2,m)需要导出极值存在的条件。数学上有两种处理方法：消元法（降维法）拉格朗日乘子法（升维法）一、消元法1）二元函数只有一个等式约束minf(x1，x2)s.t.h(x1，x2)=0处理方法：将x1表示为x1=(x2),并代入目标函数中消去x1,变成一元函数F(x2),则等式约束优化问题变为无约束优化问题。目标函数二维变一维,故称降维法。2）n维情况minf(x1，x2，，xn)s.t.hk(x1，x2，，xn)=0(k=1,2,l)由l个约束方程将n个变量中的前l个变量用其余n-l个变量表示，有x1=(xl+1,xl+2,,xn)x2=(xl+1,xl+2,,xn)xn=(xl+1,xl+2,,xn)将这些函数关系代入到目标函数中，得到只含有xl+1,xl+2,,xn共n-l个变量的函数F(xl+1,xl+2,,xn),从而利用无约束优化问题的极值条件求解。（因为将l个约束方程联立往往求不出解来，实际上难于求解）二、拉格朗日乘子法通过增加变量将等式约束优化问题变成无约束优化问题。对于minf(x)s.t.hk(x)=0(k=1,2,l)在极值点x*处有(k=1,2,l)令可通过其中的l个方程(a)来求解l个待定系数1，2，，l，使得l个变量的微分dx1,dx2,，dxl的系数全为零。于是得到00*1**1*dxxhdxxhxdhdxxfdxxfxdfTkiniikkTinii012211iniilliiidxxhxhxhxf02211illiiixhxhxhxf012211inliilliiidxxhxhxhxf则有(b)(j=l+1,l+2,,n)式（a),(b)及等式约束条件hk(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*=[x1*x2*xl*]T.02211jlljjjxhxhxhxf02211illiiixhxhxhxfxhxfxFklkk1,lkFnixFki,,2,10,,,2,10例2-4用拉格朗日乘子法计算极值点坐标f(x1，x2)=4x12+5x22s.t.h(x1，x2)=2x1+3x2-6=0解：F(x,)=4x12+5x22+(2x1+3x2-6)Fx1=8x1+2=0x1=-/4Fx2=10x2+3=0x2=-3/10F=2x1+3x2-6=0=-30/7所以得x1=1.071，x2=1.286此即为所求极值点x*.2.6不等式约束优化问题的极值条件不等式约束的多元函数极值的必要条件是库恩-塔克（Kuhn-Tucher)条件，是非线性理论的重要基础。一、一元函数在给定区间上的极值条件一元函数在给定区间[a,b]上的极值问题，可写成如下的不等式约束问题minf(x)s.t.g1(x)=a-x0g2(x)=x-b0采用拉格朗日乘子法，将上述两个不等式约束变为等式约束h1(x,a1)=g1(x)+a12=a-x+a12h2(x,b1)=g2(x)+b12=x-b+b12并得到拉格朗日函数F(x,a1,b1,1,2)=f(x)+1h1(x,a1)+2h2(x,b1)1,2为对应于不等式约束条件的拉格朗日乘子，10,20根据拉格朗日乘子法，此问题的极值条件是0,0,02020212122211111121111212211bxgbxhFaxgaxhFbbFaaFdxdfdxdgdxdgxfxF为起作用约束：不起作用：00,000,0011111111xaxgaxaxgaaaxxgaxxg,0,00,0111为起作用约束不起作用约束，分析即1，g1(x)二者必有一个等于0，因此可以写成1g1(x)=0。同样对于，2b1=0进行分析可得bxxgbxxg,0,00,0222为起作用约束不起作用约束，因此可以写成2g2(x)=0。于是，对于一元函数f(x)在给定区间上的极值条件，可以完整地表示为这样的分析方法可以推广到二元甚至多元函数不等式约束优化问题上去，从而给出著名的库恩一塔克条件。0,00)(,0)(02122112211xgxgdxdgdxdgdxdf(a)对于一元函数f(x)在给定区间[a,b]上的极值条件，式(a)中的第一式可简化为0212211dxdfdxdgdxdgdxdf分析极值点x*在区间[a,b]中的位置，可能出现3种情况，如图2-11所示。这和如图2-11所示的从几何概念分析的结果完全一致。0d*d,0dd0,0*30d*d,0dd0,0*2)0d*d0*)122112121xxfxfbxxxfxfaxxxfbxa即极值条件为，时，当）即极值条件为，时，当极值条件为，时，当由以上分析可知，对应于不起作用约束的拉格朗日乘子取零值。因此可以引入起作用约束的下标集合J(x)={j|gj(x)=0,j=1,2}。当ax*b时，两个约束均不起作用，故有J(x*)=,1=2=0。当x*=a时，第一个约束起作用，故有J(x*)={1},10，2=0。当x*=b时，第二个约束起作用，故有J(x*)={2},1=0，20。于是可将式(a)改写成如下形式：也就是说，在极值条件中只考虑起作用的约束及相应的拉格朗日乘子。00)(0jjjJjjJjxgdxdgdxdf二、库恩-塔克条件对于多元函数不等式约束优化问题minf(x)s.t.gj(x)0(j=1,2,m)同样可以应用拉格朗日乘子法推导出相应的极值条件。为此，需要引入m个松弛变量使不等式约束gj(x)0(j=1,2,m)变成等式约束gj(x)+xn+j2=0(j=1,2,m),从而组成相应的拉格朗日函数。其中，是对应于不等式约束的拉格朗日乘子向量=[12jm]T,并且满足非负要求，即0。根据无约束极值条件，