机械优化设计方法第三章.ppt

第三章 优化设计方法的数学基础3-1 优化设计问题的几何意义,一、目标函数的等值面(线)目标函数的值是评价设计方案优劣的指标。n维变量的目标函数，其函数图象只能在n+1维空间中描述出来。当给定一个设计方案，即给定一组x1,x2,xn的值时，目标函数f(X)=f(x1,x2,xn)必相应有一确定的函数值；若给定一个f(X)值,却有无限多组x1,x2,xn 值与之对应，也就是当f(X)=a时，X=x1,x2,xn T在设计空间中对应有一个点集。通常这个点集是一个曲面(二维是曲线，大于三维称超曲面)，称之为目标函数的等值面。当给定一系列的a值，即a=a1,a2,时，相应有f(X)=a=a1,a2,，这样可以得到一组超曲面族等值面族。等值面具有特性:即在一个待定的等值面上，尽管设计方案很多，但每一个设计方案的目标函数值都是相等的。,现以二维无约束最优化设计问题为例阐明其几何意义。如图，二维目标函数f(X)=f(x1,x2)在以x1,x2和f(X)为坐标的三维坐标系空间内是一个曲面。在二维设计平面x1ox2中，每一个点X=x1,x2T都有一个相应的目标函数值f(X)=f(x1,x2)，它在图中反映为沿f(X)轴方向的高度。,若将f(X)=f(x1,x2)曲面上具有相同高度的点投影到设计平面x1ox2上，则得f(X)=f(x1,x2)=a的平面曲线，这个曲线就是符合f(X)=f(x1,x2)=a的点集，称为目标函数的等值线,对于三维问题在设计空间中是等值面，高于三维的问题在设计空间中则是等值超曲面。,二、约束最优解和无约束最优解,n维目标函数f(X)=f(x1,x2,xn)，若在无约束条件下极小化，即在整个n维设计空间寻找X*=x1*,x2*,xn*T使满足min f(X)=f(X*)，X R n，其最优点X*、最优值f(X*)构成无约束最优解；若在约束条件限制下极小化，即在可行域D中寻找 X*=x1*,x2*,xn*T使满足min f(X)=f(X*)，其最优点X*、最优值f(X*)则构成约束最优解。约束最优解和无约束最优解，无论在数学模型还是几何意义上，两者均是不同的概念。,设已知目标函数,受约束于,求其最优解X*和f(X*)。,等值钱表示了目标函数值的变化情况，越向里边的代表目标函数值越小。显然其无约束最优解为目标函数等值线同心圆中心X*(1)=x1*(1)，x2*(1)T，f(X*(1)=0。而其约束最优解则需在由约束线g1(X)=0，g2(X)=0，g3(X)=0，g4(X)=0组成的可行域D（阴影线里侧）内寻找使目标函数值为最小的点由图可见约束曲线g4(X)=0与某等值线的一个切点X*(2)即为所求。X*(2)=x1*(2)，x2*(2)T=0.85，1.34 T，f(X*(2)=3.80，为其约束最优解。,图3-2（a）表示其目标函数和约束函数的立体图，图3-2(b)表示其平面图。显然其无约束最优解为目标函数等值线同心圆中心,二维问题关于约束最优解和无约束最优解几问意义的讨论，同样可推广到高维问题。n个设计变量X=x1,x2,xnT组成设计空间。在这个空间中的每一个点代表一个设计方案，此时n个变量具有确定的值。当给定目标函数某一定值时，就在n维设计空间内构成一个目标函数的等值超曲面。给定目标函数一系列数值时就获得一系列目标函数的等值超曲面。这些等值超曲面反映了目标函数变化情况。无约束最优点为这些等值超曲面的共同中心。对于约束最优化问题，每一个约束条件在n维设计空间是一个约束超曲面,全部约束超曲面在设计空间中构成可行域D，在其上寻找目标函数值最小的点即为约束最优点。这一点可以是目标函数等值超曲面与某个 约束超曲面的一个切点，也可以是目标函 数值较小的某些约束超曲面的交点(如图所 示的X*点)。,三、局部最优解和全域最优解,对无约束最优化问题，当目标函数不是单峰函数时，有多个极值点X*(1)，X*(2)，如图所示。此时X*(1)和f(X*(1)、X*(2)和f(X*(2)均称为局部最优解。如其中X*(1)的目标函数值f(X*(1)是全区域中所有局部最优解中的最小者，则称X*(1)和f(X*(1)和为全域最优解。,对于约束最优化问题，情况更为复杂。它不仅与目标函数的性质有关，而且还与约束条件及其函数性质有关。如图3-5所示，目标函数f(X)的等值线绘于图上，有两个不等式约束g1(X)0，g2(X)0，构成两个可行域D1和D2。X*(1)、X*(2)、X*(3)分别是可行域内在某一邻域目标函数值最小的点，都是局部极小点，亦即X*(1)、f(X*(1)，X*(2)、f(X*(2)，X*(3)、f(X*(3)均称局部最优解。可知X*(3)为全域极小点，亦即X*(3)和f(X*(3)为全域最优解。,优化设计总是期望得到全域最优解，但目前的优化方法只能求出局部最优解，并采取对各局部最优解的函数值加以比较、取其中最小的一个作为全域最优解。,3-2函数的方向导数和梯度,为了尽快找到目标函数f(X)的极小值点，研究函数在其定义空间中的变化规律是必须的。譬如说，若是已知在设计空间的某一点处函数的取值沿某一个方向下降得最快，于是我们就可以从该点出发，沿着这个方向去寻找函数的极小值点。为此，这里要引用函数的方向导数和梯度。,一、函数的方向导数,对一元函数而言，函数的导数是描述函数相对于自变量变化快慢程度的一个量。多元函数的偏导数是描述当只有一个自变量变化，而其余自变量保持不变的情况下，函数的变化率。具有n个自变量的函数 f(X)=f(x1,x2,xn）在X(0)x1(0),x2(0),xn(0)T点的一阶偏导数记为,，i=1，2，n,它是一个标量。,函数的偏导数仅仅描述了函数沿其自变量所在坐标轴的特定方向上的变化率在许多实际问题中，常常需要知道函数沿其它任一方向上的变化率。对这样的问题就要借助于函数的方向导数来描述。函数在某一点X(0)处沿某任意指定方向S上的方向导数就是函数在X(0)处沿S方向的变化率，记为,（S，xi），i=1，2，n为方向S 相对对于坐标轴xi正方向的方向角。,图示。函数f(X)在X(0)x1(0),x2(0)T点的偏导数,从同一点X(0)出发，沿不同方向的方向导数不相同。就象爬山一样，把目标函数值看做山的海拔高度，方向导数不同犹如沿不同的路线或方向山的坡度不一样。方向导数越大，表明沿这个方向或路线山的坡度越大。提出问题：从X(0)点出发，可以有无穷多个方向，那么究竟哪一个方向函数f(X)的变化率最大呢？这个问题要借助于函数的梯度来判定。,f(X)值在X(0)点处沿S方向是增加的；,f(X)值在X(0)点处沿S方向是减少的；,即方向S与f(X)的等值面相切，这时，f(X)在X(0)点处沿S方向不增也不减。,二、函数的梯度,可以对方向导数作如下变换：设S0为S方的的单位向量，则S0在坐标轴上的投影为cosi，i=1，2，n，这里i(S0,xi)，即,f(X)是一个矢量，其分量是f(X)沿各坐标轴的偏导数。该矢量与S0的方向无关，而完全由函数f(X)的性质所决定。矢量f(X)的方向就是函数f(X)变化率最大的方向，且其模f(X)恰好是这个最大变化率的数值。把f(X)矢量称为函数f(X)在给定点X(0)的梯度。也就是说，函数f(X)的梯度方向是函数值增大最快的方向：函数f(X)在某给定点X(0)处的梯度的模等于该给定点处函数值增大变化率的数值。,函数梯度的性质,(l)函数f(X)在其定义空间内某一点处的方向导数等于函数在该点处的梯度在这个方向上的投影；(2)梯度是矢量。函数在其定义空间中的某一点处，其梯度标志着函数值增加最快或最速上升的方向。注意，这仅是指f(X)在该点附近而言，函数在其定义空间中的每一个点处都对应着一个确定的梯度向量。负梯度方向必是函数值减小最快或最速下降的方向；(3)在目标函数等值线或等值面上的每一点处，函数的梯度f(X)指向函数等值线或等值面的外法向，亦即最速上升方向；函数在与其梯度正交的方向上变化率为零；（4）线性目标函数的梯度是一个常值向量，即在其定义空间中，其梯度处处相同；,几个常用函数的梯度公式,(1)若f(X)在X(0)点有极值，则必有f(X(0)0；若f(X(0)常数C，则有 f(X(0)C0(2)若f(X)X，则 f(X)(X)I（单位矩阵）(3)若f(X)BTX，则(BTX)B(4)若f(X)QX，Q为对称方阵，则(QX)Q(5)若f(X)XTX，则(XTX)2X(6)若Q为实对称方阵，则对f(X)XTQX 有(XTQX)2QX(7)若f(X)(1/2)XTQXBTXC，C为实对称方阵，则有f(X)QXB,3-3函数的Taylor展开式和Hessian矩阵,一、函数的Taylor展开式当一元函数f(x)在点的某个邻域N内有直到(n+l)阶导数存在并连续时，则可把f(x)展成为(x-x0)的n次Taylor多项式与一个余项Rn之和,xN，在x0与x之间取值,在式中若取其前二项，即,则为用直线来近似代替原函数f(x)。若取其前三项，即,则为用二次抛物线来近似代替原函数f(x)。,推广到n元函数的情形。令xixix0i，并取类似式（3-7）中的前三项，设f(X)f(x1,x2,xn)；Xx1,x2,xnT，且有，X(0)x1(0),x2(0),xn(0)T，则有f(X)f(X(0)+fx1(X(0)x1+fxn(X(0)xn+0.5 fx1 x1(X(0)x12+fx1 x2(X(0)x1x2+fx1 xn(X(0)x1xn+fx2 x1(X(0)x1x2+fx2 x2(X(0)x22+fx2 xn(X(0)x2xn+fxnx1(X(0)xnx1+fxnx2(X(0)xnx2+fxnxn(X(0)xn2,用矩阵表示,式中 XXX(0)x1,x2,xnT,二、Hessian矩阵,由式所表达的矩阵称为函数f(X)的Hessian矩阵。它是函数f(X)关于变量的二阶导数矩阵，亦即Taylor展开式中的二次项系数矩阵，常记为,3-4二次函数及其二次项系数矩阵,在目标函数中，除了线性函数以外，最简单但又是最重要的一类是二次函数。数学上已经证明，一般目标函数在其极小值点附近，其等值面近似呈现为椭球面族。因此，在求一般目标函数的极小值点时，在其极小值点附近常可用二次函数作近似地替代，然后求其极小值点。,一、二次函数,二次函数的一般形式为,qij、bi均为实常数，且qijqji；C为常数。,或用矩阵表示,Xx1,x2,xnT,标准型二次函数（或称二次型）为,这里的二次项系数矩阵Q是n阶对称矩阵。,二、二次函数的二次项系数矩阵,若二次函数是Taylor展开获得的，则其二次项系数矩阵Q就是Hassian矩阵。优化设计中，二次项系数矩阵Q是非常有用的。可以依据它的正定性质很方便地判定目标函数f(X)的极小值点是否存在，并求出该极小值点。即如果Q是正定的，则目标函数的等值面是同心椭球面族 且其中心点为 X*=Q1B矩阵Q是否正定，可用判定定理：一个nn阶对称矩阵Q是否正定的必要充分条件为其对应行列式的各阶主子式都取正值，即,；,3-5无约束目标函数的极值点存在条件,一、函数的极值与极值点 现以一元函数为例说明函数的极值与极值点。图3-6所示为定义在区间a,b上的一元函数f(x),图上有两个特殊点：x(1)与x(2)。在x(1)附近，函数f(x)的值以f(x(1)为最大，在x(2)附近，函数值以f(x(2)为最小。因此x(1)与x(2)，即为函数的极大点与极小点，统称为函数f(x)的极值点。f(x(1)与f(x(2)相应地为函数的极大值与极小值，统称为函数f(x)的极值。需要注意，这里所谓极值是相对于一点的附近邻域各点而言的，仅具有局部的性质，所以这种极值又称为局部极值。而函数的最大值与最小值是指整个区间而言的。如图3-6中函数的最大值为f(b)，函数的最小值为f(a)。函数的极值并不一定是最大值或最小值。,二、极值点存在的条件,(一)一元函数(即单变量函数)的情况(1)极值点存在的必要条件如果函数f(x)的一阶导数f(x)存在的话，则欲使x*为极值点的必要条件为：f(x*)=0 但使f(x*)=0的点并不一定部是极值点。使函数f(x)的一阶导数f(x)=0的点称为函数f(x)的驻点。极值点(对存在导数的函数)必为驻点，但驻点不一定是极值点。至于驻点是否为极值点可以通过二阶导数f(x)=0来判断。,(2)极值点存在的充分条件,若在驻点附近 f”(x)0，则该点为极小点。在图3-6中的x(3)附近，其右侧f”(x)0，因此它不是一个极值点。可见函数二阶导数的符号成为判断极值点的充分条件。,(二)多元函数(即多变量函数)的情况,设f(X)为定义在 中的n元函数。向量X的分量x1,x2,xn就是函数的自变量。设X(k)为定义域内的一个点，且在该点有连续的n+1阶偏导数，则在该点附近可用泰勒级数展开，如取到二次项：,如果用向量定阵形式表示则上式可写为：,可简写为,f(X(k)是函数f(X)在X(k)点的一阶偏导数矩阵，称为函数在该点的梯度。,梯度f(X(k)是一个向量，其方向是函数f(X)在X(k)点数值增长最快的方向，亦即负梯度-f(X(k)方向是函数f(X)在X(k)点数值下降最快的方向，梯度的模,但需注意，函数f(X)在某点X(k)的梯度向量f(X(k)仅反映f(X)在X(k)点附近极小邻域的性质，因而是一种局部性质。函数在定义域内的各点都各自对应着一个确定的梯度。此外，函数f(X)在点X(k)的梯度向量f(X(k)正是函数等值线或等值超曲面在该点的法向量。,图3-7表示二元函数f(X)在X(1)、X(2)点的梯度f(X(1)、f(X(2)和负梯度-f(X(1)、-f(X(2)。2f(X(k)是函数f(X)在X(k)点的二阶偏导数组成的nn阶对称矩阵，或称为f(X(k)的赫森(Hessian)矩阵，记作H(X(k)。,(1)极值点存在的必要条件,n元函数在定义域内极值点X*存在的必要条件为,即对每一个变量的一阶偏导数值必须为零，或者说梯度为零(n维零向量)。和一元函数对应，满足式(3-9)只是多元函数极值点存在的必要条件，而并非充分条件；满足f(X*)=0的点X*称为驻点，至于驻点是否为极值点，尚须通过二阶偏导数矩阵来判断。,(2)极值点存在的充分条件,如何判断多元函数的一个驻点是否为极值点呢?将多元函数f(X)在驻点X*附近用泰勒公式的二次式近似地表示，则由式,因X*为驻点，f(X*)=0，于是有,在X*点附近的邻域内，若对一切的X恒有f(X)-f(X*)0亦即,则X*为极小点；否则，当恒有,时，则X*为极大点。,亦即驻点赫森矩阵H(X*)必须为正定；同理知极大点的充分条件为：,根据矩阵理论知，由式,得极小点的充分条件为：,亦即驻点赫森矩阵H(X*)必须为负定。而,亦即驻点赫森矩阵既非正定，又非负定，而是不定，f(X)在X*处无极值。,至于对称矩阵正定、负定的检验，由线性代数可知：对称矩阵,正定的条件是它的行列式|A|的顺序主子式全部大于零，即,，,负定的条件是它的行列式|A|中一串主子式为相间的一负一正的，即,，,例题3-l 求解,的极值点和极值。,解：,的极值点必须满足,解此联立方程得：x1=1,x2=1,x3=-2，即点X*=1,1,-2T为一驻点。再利用赫森矩阵H(X*)的性质来判断此驻点是否为极值点。,对各变量求二阶偏导数，写出驻点的赫森矩阵,将H(X*)记作,则,因此,赫森矩阵H(X*)是正定的故驻点X*=1，1，-2T为极小点。对应于该极小点的函数极小值为H(X*)=212+512+(-2)2+21(-2)+2(-2)1-61+3=0,3-6 函数的凸性,由前述讨论可知，函数的最优值与极值是有区别的。前者是指全域而言，而后者仅为局部的性质。一般来说，在函数定义的区域内部，最优点必是极值点，反之却不一定。如果能得到两者等同条件，就可以用求极值的方法来求最优值，因此对于函数的最优值与极值之间的关系需作进一步的讨论。目标函数的凸性与所需讨论的问题有密切的关系。,我们可以先用一元函数来说明函数的凸性。如图3-8所示，图(a)在x(1)、x(2)区间曲线为下凸的，图(b)的曲线是上凸的，它们的极值点(极小点或极大点)在区间内部是唯一的。这详的函数称为具有凸性的函数，或称为单峰函数。,一、凸集与非凸集,为了考虑多元函数的凸性，首先要说明函数定义域应具有的性态。设D为n维欧氏空间中设计点X的一个集合，若其中任意两点X(1)和X(2)的连线都在集合D中，则称这种集合是n维欧氏空间的一个凸集。二维函数的情况如图3-9所示，其中图(a)为凸集，图(b)为非凸集。,在n维空间中，若对某集合D内的任意两点X(1)与X(2)作连线，使连线上的各个内点对任何实数(01)恒有,则称D为凸集。图3-10是对于二维问题、式(3-17)对应的向量图解。n维无约束最优化问题整个设计空间Rn是凸集。,(3-17),二、凸函数的定义,设f(X)为定义在n维欧氏空间中一个凸集D上的函数，若对任何实数(01)及D域中任意两点X(1)与X(2)存在如下关系：,（3-18）,则称函数f(X)是定义在凸集D上的一个凸函数。现用图3-11所示定义于区间a，b的单变量函数来说明这一概念。若连接函数曲线上任意两点的直线段，某一点X(k)的函数值恒低于此直线段上相应的纵坐标值时，这种函数就是凸函数，也就是单峰函数。,若将式(3-18)中的符号“”改为“”，则称函数f(X)为严格凸函数。若将式(3-18)中的符号“”为“”，则如图3-8(b)所示，函数曲线上凸(有极大点)，通常称为凹函数。显然，若f(X)为凸函数，则-f(X)为凹函数。,（3-18）,三、凸函数的基本性质,1)若函数f1(X)和f2(X)为凸集D上的两个凸函数，对任意正数a和b，函数f(X)=a f1(X)+b f2(X)，仍为D集上的凸函数。2)若X(1)与X(2)为凸函数f(X)中的两个最小点，则其连线上的一切点也都是f(X)的最小点。证明略。,四、凸函数的判定,判别法1：若函数f(X)在D1上具有连续一阶导数，而D为D1内部的一个凸集，则f(X)为D上的凸函数的充分必要条件为:对任意的X(1)、X(2)D，恒有,判别法2：若函数f(X)在凸集D上存在二阶导数并且连续时，对f(X)在D上为凸函数的充分必要条件为：对于任意的XD，f(X)的赫森矩阵H(X)处处是正半定矩阵。若赫森矩阵H(X)对一切XD都是正定的，则f(X)是D上的严格凸函数，反之不一定成立。,（3-19）,例题3-2 判别函数,在,上是否为凸函数。,解：利用赫森矩阵来判别：,令,，,因为赫森矩阵是正定的，故f(X)为严格凸函数。,五、函数的凸性与局部极值及全域最优值之间的关系,设f(X)为定义在凸集D上的一个函数，一般来说，f(X)的极值点不一定是它的最优点。但是，若f(X)为凸集D上的一个凸函数，则f(X)的任何极值点，同时也是它的最优点。若f(X)还是严格凸函数，则它有唯一的最优点。,3-7 约束极值点存在条件,在约束条件下求得的函数极值点，称为约束极值点。在优化实用计算中常需判断和检查某个可行点是否约束极值点，这通常借助于库恩-塔克(Kuhn-Tucker)条件(简称K-T条件)来进行。K-T条件可阐述为：如果X(k)是一个局部极小点，则该点的目标函数梯度f(X(k)可表示成该点诸约束面梯度为gu(X(k)、hv(X(k)的如下线性组合：,式中：q在X(k)点的不等式约束面数；j在X(k)点的等式约束面数；u(u=1,2,q)、v(v=1,2,j)非负值的乘子，亦称拉格朗日乘子。如无等式约束，而全部是不等式约束，则式(320)中j0，第三项全部为零。,（3-20）,也可以对K-T条件用图形来说明。式(3-20)表明，如果X(k)，是一个局部极小点，则该点的目标函数梯度f(X(k)应落在该点诸约束面梯度gu(X(k)、hv(X(k)在设计空间所组成的锥角范围内。如图3-12所示，图(a)中设计点X(k)不是约束极值点，图(b)的设计点X(k)是约束极值点。,用二维情况为例，将更形象地表朋K-T条件。,图3-13为在设计点X(k)处有两个约束，图(a)表示X(k)点处目标函数梯度f(X(k)在该点两个约束函数梯度g1(X(k)、g2(X(k)组成的锥角T以外，这样在X(k)点邻近的可行城内存在目标函数值比f(X(k)更小的设计点，故X(k)点不能成为约束极值点；而图(b)X(k)点处f(X(k)落在锥角T以内，则在该点附近邻域内任何目标函数值比f(X(k)更小的设计点都在可行域以外，因而X(k)是约束极值点，它满足式(3-20)K-T条件,，,，,而图(b)中由于f(X(k)和g(X(k)方向重合，则f(X(k)-g(X(k)=0，0，此即当X(k)点处约束面数q1时的K-T条件，显然X(k)点附近邻域内任何目标函数值比f(X(k)更小的设计点都在可行域以外，X(k)点是约束极值点。,图3-14为在设计点X(k)处只有一个约束，图(a)表示f(X(k)和g(X(k)方向不重合，在X(k)邻近的可行城内存在目标函数值比f(X(k)更小的设计点，故X(k)不能成为约束极值点；,必须指出，K-T条件用于检验设计点是否为约束极值点，对于“凸规划”问题，即对于目标函数f(X)为凸函数、可行域为凸集的优化问题，局部极值点与全域最优点相重合，如图3-13(b)、图3-14(b)皆为凸规划问题，X(k)点符合K-T条件，必为全域最优点；,但对于非凸规划问题则不然。图3-15(a)是目标函数为非凸函数、约束可行域为凸集，图3-15(b)是目标函数为凸函数、约束可行域为非凸集，这两种情况在可行域中均可能出现两个或更多的局部极小点，它们必须都满足K-T条件；但其中只有一个函数值最小的点X*是约束最优点。在工程优化设计问题中，函数在全域上的凸性不一定存在，在许多情况下，凸性的判断亦难进行。因此判断符合K-T条件的约束极值点是全域最优点还是局部极值点目前仍属优化研究的一个重大课题。但凸集、凸函数、K-T条件等在优化理论和实践中仍具重要意义。,亦须指出，用K-T条件检验约束极值点是指具有起作用约束的可行点。如图3-16所示，无约束极值点X*处gu(X*)均大于零(ul，2，3，4)，这一组约束条件对X*都不起作用，X*亦是约束极值点，但却不属K-T条件的范围。,例题33 用K-T条件检验点X(k)=2,0T是否为目标函数,在不等式约束：,、,、,解（1)计算X(k)点的诸约束函数值,X(k)点是可行点，该点起作用的约束函数是g1(X)和g2(X)。,条件下的约束最优点。,(2)求X(k)点的有关诸梯度,(3)代入式(3-20)，求拉格朗日乘子,写成线性方程组,解得：1=2=0.5乘子均为非负，故满足K-T条件，即X(k)=2,0T点为约束极值点。参看图3-17，亦得到证实。而且f(X)是凸函数，可行域为凸集，所以点X(k)也是约束最优点,3-8共轭方向,一般目标函数的等值面在极小值点附近近似呈椭球族。一般二次函数只要其二次项系数矩阵是正定的，则其等值面族一定是一同心椭球面族。数学上可以证明，同心椭球面族有一个重要的特性：过椭球中心作任意直线，它与各等值椭球面相交交点处的切平面彼此平行。或者说，过任意两椭球面作平行切面，其切点的连线必通过椭球中心。,下面以二维问题为例来说明这一事实。如图所示，此时椭球面族成为椭圆族。现将椭圆中心目标函数的极小值点X*选作坐标原点，于是椭圆族方程为f(x1,x2)=a x12+2h x1 x2+b x22+C,过原点0的任意直线AB，设其方程为 x2=k x1 直线AB交任意两个椭圆于X(1)、X(2)。通过该二点的两个椭圆方程为,a x1(1)2+2h x1(1)x2(1)+b x2(1)2+C=C 1a x1(2)2+2h x1(2)x2(2)+b x2(2)2+C=C 2,椭圆上任一点的斜率可由隐函式对x1求导数来求得,即,设直线AB与二椭圆C1、C2的交点X(1)、X(2)处二椭圆斜率分别为k1、k2，则考虑式x2=k x1有,3-9 最优化设计的数值计算迭代方法,非线性无约束最优化问题解法大致分为两类：解析法和数值计算迭代方法。解析法是采用导数寻求函数极值的方法，其特点是以数学分析为工具，古典的微分法就属于这一类。仅适用于求解目标函数具有简单而明确的数学形式的非线性规划问题。而对于目标函数比较复杂或甚至无明确的数学表达式的情况，这种方法显得求解效率极低或无能为力。这时应采用数值计算迭代方法。,数值计算迭代方法是直接从目标函数f(X)出发，构造一种使目标函数值逐次下降逼近，利用电子计算机进行迭代，一步步搜索、调优并最后逼近到函数极值点或达到最优点。根据确定搜索方向和步长的方法不同，数值计算寻优可有许多方法，但其共同点是：1）要具有简单的逻辑结构并能进行同一迭代格式的反复的运算；2)这种计算方法所取得的结果不是理论精确解而是近似解，但其精度是可以根据需要加以控制的。,一、迭代法的基本思想及其格式,基本思想是：在设计空间从一个出始设计点X(0)开始，应用某一规定的算法，沿某一方向S(0)和步长(0)产生改进设计的新点X(1)，使得f(X(1)f(X(0)，然后再从X(1)点开始，仍应用同一算法，沿某一方向S(1)和步长(1)，产生又有改进的设计新点X(2)，使得f(X(2)f(X(1)，这样一 步一步地搜索下去，使目标 函数值步步下降，直至得到 满足所规定精度要求的、逼 近理论极小点的X*点为止。这种寻找最优点的反复过程 称为数值迭代过程。图3-18 为二维无约束最优化迭代过 程示意图。,无约束最优化算法，每次迭代都按一选定方向S和一合适的步长向前搜索，可以写出迭代过程逐次搜索新点的向量方程式 X(1)=X(0)+(0)S(0)X(2)=X(1)+(1)S(1)迭代过程的每一步向量方程式，都可写成如下的迭代格式 X(k+1)=X(k)+(k)S(k)(k=0,1,2,)（3-21）,S(k)是向量，代表第k步迭代的前进方向(或称搜索方向）(k)是标量，代表第k步沿S(k)方向的迭代步长(或称步长因子)。,在一系列的迭代计算k0，l，2，过程中，产生一系列的迭代点(点列)X(0)，X(1)，X(k)，X(k+1)，。为实现极小化，目标函数f(X)的值应一次比一次减小，即 f(X(0)f(X(1)f(X(2)f(X(k)f(X(k+1)（3-22）直至迭代计算满足一定的精度时，则认为目标函数值近似收敛于其理论极小值。,二、迭代计算的终止准则,对无约束最优化问题常用的迭代过程终止准则一般有以下几种。,1)点距准则 当相邻两迭代点X(k)，X(k+1)之间的距离已达到充分小时，即小于或等于规定的某一很小正数时，迭代终止。一般用两个迭代点向量差的模来表示，即,用X(k+1)和X(k)在各坐标轴上的分量差来表示，即,2)函数下降量准则 当相邻两迭代点X(k)，X(k+1)的目标函数值的下降量已达到充分小时。即小于或等于规定的莱一很小正数时，迭代终止。一般用目标函数值下降量的绝对值来表示，即,（当,或用目标函数值下降量的相对值来表示，即,（当,3)梯度准则 当目标函数在迭代点X(k+1)的梯度已达到充分小时，即小于或等于规定的某一很小正数时，迭代终止。一般用梯度向量的模来表示，即,以上各式中的根据不同的优化方法和具体设计问题对精度的要求而定。一般来说，这几个迭代过程终止准则都分别在某种意义上反映了逼近极值点的程度，满足其中任一个迭代终止准则，都可以认为目标函数f(X(k+1)收敛于函数f(X)的极小值，对凸规划问题即为近似最优解：X*=X(k+1)和f(X*)=f(X(k+1)，从而可以结束选代计算。迭代过程中每一步迭代得一新点，一般都要以终止准则判别是否收敛，如不满足，则应再进行下一步迭代，直到满足迭代终止准则为止。,上列几种迭代终止淮则。除式(3-27)所示梯度准则仅用于那些需要计算目标函数梯度的最优化方法中外，其余并无持别规定必须选用哪一种。有时为了防止函数变化剧烈时式(3-23)所示点距准则失效(见图3-19(a)，或当函数变化缓慢时式(3-25)所示函数下降量准则失效(见图3-19(b)，这时往往将点距准则和函数下降量准则结合起来，使同时成立。最后尚须指出，迭代终止准则并不限于上列几种，这将在讲述采用其他终止准则的优化方法时再作介绍。,（3-23）,（3-27）,（3-25）,