第三章优化设计的某些基本概念和理论301ppt课件

.,第三章优化设计的某些基本概念和处理,3.1目标函数与约束函数的某些基本性质3.2约束函数的集合及其性质3.3优化设计问题的最优解及其最优性条件3.4优化设计问题的数值解法及收敛条件,.,3.1目标函数与约束函数的某些基本性质,3.1.1函数的等值面（或线）：,对于可计算的函数f(x)，给定一个设计点X(k)(x1(k),x2(k),xn(k)，f(x)总有一个定值c与之对应；而当f(x)取定值c时，则有无限多个设计点X(i)(x1(i),x2(i),xn(i)（i=1,2,）与之对应，这些点集构成一个曲面，称为等值面。,当c取c1,c2,等值时，就获得一族曲面族，称为等值面族。,当f(x)是二维时，获得一族等值线族；当f(x)是三维时，获得一族等值面族；当f(x)大于三维时，获得一族超等值面族。,.,3.1.1函数的等值面（或线）：,等值线的“心”（以二维为例）,一个“心”：是单峰函数的极（小）值点，是全局极（小）值点。没有“心”：例，线性函数的等值线是平行的，无“心”，认为极值点在无穷远处。,多个“心”：不是单峰函数，每个极（小）值点只是局部极（小）值点，必须通过比较各个极值点和“鞍点”（须正确判别）的值，才能确定极（小）值点。,.,3.1.1函数的等值面（或线）：,等值线的形状：同心圆族、椭圆族，近似椭圆族；,等值线的疏密：沿等值线密的方向，函数值变化快；沿等值线疏的方向，函数值变化慢。等值线的疏密定性反应函数值变化率。,严重非线性函数病态函数的等值线族是严重偏心和扭曲、分布疏密严重不一的曲线族。,.,3.1.2函数的最速下降方向,方向导数：二维问题中，f(x1,x2)在X(0)点沿方向s的方向导数为：,其中：,是X(0)点的梯度。,S为s方向的单位向量，。,为S的方向角,方向导数,为方向余弦。,为梯度,在方向s上的投影。,.,3.1.2函数的最速下降方向,梯度的性质：,梯度是X(0)点处最大的方向导数；梯度的方向是过点的等值线的法线方向；梯度是X(0)点处的局部性质；梯度指向函数变化率最大的方向；正梯度方向是函数值最速上升的方向，负梯度方向是函数值最速下降的方向。,对于n维问题的梯度,.,3.1.3函数局部近似的表达式和平方函数,n维函数f(x)在x(k)点的台劳展开式:,二阶近似式：,其中：增量,X(k)=x1(k),x2(k),xn(k)T,梯度,Hesse矩阵,Hesse矩阵与正定,.,3.1.3函数局部近似的表达式和平方函数,Hesse矩阵的特性：是实对称矩阵。,矩阵正定的充要条件：,主子式det(ait)0,当主子式det(ait)0时，矩阵半正定det(ait)0时，矩阵负定det(ait)0时，矩阵半负定,Hesse矩阵的正定性：,H(x*)正定，是x*为全局极小值点的充分条件；H(x*)半正定,是x*为局部极小值点的充分条件；H(x*)负定，是x*为全局极大值点的充分条件；H(x*)半负定,是x*为局部极大值点的充分条件。,正定的二次函数：曲面为椭圆抛物面；等值线族为椭圆曲线族，椭圆中心为极小值点。,.,3.1.4函数的凸性,凸集：设D为欧氏空间Rn中X的集合，即DRn,XD，若D域内任意两个点x(1)，x(2)的连线上的各点都属于D域，则集合D称为Rn内的一个凸集。否则，为非凸集。,凸函数：,f(x)是定义在n维欧氏空间中，凸集上的函数，同时x(1)D，x(2)D，0,1，当下式成立时，,则称f(x)为定义在凸集D上的凸函数。,fx(1)+(1-)x(2)f(x(1)+(1-)f(x(2),当上式中的为时，f(x)是严格凸函数。,.,3.1.4函数的凸性,判别函数为凸函数的凸性条件：,按梯度判断凸性：设f(x)是定义在凸集D上具有连续一阶导数的函数，则f(x)在D上为凸函数的充要条件是：对于任意的x(1),x(2)D都有成立。,按二阶偏导数判断凸性：设f(x)是定义在凸集D上具有连续二阶导数的函数，则f(x)在D上为凸函数的充要条件是：f(x)的Hesse矩阵处处半正定。若Hesse矩阵处处正定，则f(x)为严格凸函数。,凸函数的基本性质：,若f(x)是定义在凸集D上的严格凸函数，则f(x)在D上的一个极小点，也就是全局最小点。凸函数的线性组合仍然为凸函数。设x(1),x(2)为凸函数f(x)上的两个最小点，则其连线上的任意点也都是最小点。,.,3.2约束函数的集合及其性质,3.2.1约束集合和可行域,约束集合：是指所有不等式约束和等式约束的交集,即：,由于该集合内所有设计点x都满足全部的约束条件，所以设计可行域可以表示为：,其中假设函数gu(x)和h(x)都是连续的。这样，对于一个约束的优化设计问题，由于约束面的存在而把设计空间划分为两个区域：设计可行域和非可行域。可行域内的各点都满足所有的约束条件，因而最优解或可接受设计解只能从这些点中产生。,.,3.2.1约束集合和可行域,若在可行域内不存在设计点，则认为此可行集合是个空集，此时也就没有可接受的设计解。关于约束交集或是可行域D是否为一个凸集，在凸规划理论中证明了：若各个不等约束函数gu(x)(u1，2，m)是凸函数和等式约束hv(x)(vl，2，p)是线性函数，则G或D是凸集。但是只要等式约束是非线性的，那么集合G或D一定是个非凸集。,关于约束函数集合的几何概念是很清楚的。例如，对于一个二维问题，当其约束条件为：,.,3.2.1约束集合和可行域,由图310(a)可见，它是一个在第一象限内的凸集D。当约束条件g3(x)改为,由图310(b)可见，是一个在第一象限内的非凸集D,因为g3(x)函数是一凹函数。,.,3.2.1约束集合和可行域,当约束条件g3(x)取为等式约束,由图310(c)可见，也是一个非凸集D，此时这个集合是在x10和x20(第一象限内)上h(x)0的一段曲线。,值得注意的是，一个约束函数经过变换，虽然表示形式不同，而且也未改变其约束的条件，但有时却会影响约束函数的凸性。,例如，对于x10和x20，且a和b为正常数，其原约束条件形式为,可以等价地变换为下面形式(由于x1和x2均取正值，故不等式的意义没有改变),.,由此，约柬函数通过形式上的变换，结果可能丢失了函数的凸性(或者相反)，这也就影响可行域的约束集合的凸性条件。,式中，为正定短阵；为不定短阵。,结果是g1(x)是凸函数，变换为g2(x)则是非凸函数，因为他们的Hessian矩阵分别为,3.2.1约束集合和可行域,当不等式约束都是线性函数时，其约束集合D必为一个凸集。,.,3.2.2起作用约束和松弛约束,对于一个不等式约束g(x)0来说，如果所讨论的设计点x(k)使该约束g(x(k)=0(或者说x(k)当时正处在该约束的边界上)时，则称这个约束是x(k)点的一个起作用约束或紧约束。而其他满足g(x)0的约束称为松弛约束。如图所示，对点x(k)来说，g1和g2是起作用约束，而g3和g4为松弛约束。,当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为,其意义是对x(k)点此时所有起作用约束下标的集合。以上图为例，其I(x(k)1,2。,.,3.2.3冗余约束,如果一个不等式约束条件的约束面(即g=0)对可行域的大小不发生影响，或是约束面不与可行域D相交，即此约束称为冗余约束。,一个约束条件对优化设计模型是否是冗余的，可以根据下面的优势定理来确定；,对于一切的设计点x，若g2(x)f(x(k)，则称x(k)为该目标函数在D上的局部最优点；若一切的x(k+1)(XD)，满足f(x(k+1)f(x(k)，则称x(k)为D上的全局最优点。,3.3.2局部最优点和全局最优点,因此，只有当日标函数在约束可行域D内是单蜂函数和约束集合D是凸集时，所计算得的局部最优解可以断定它也就是问题的全域最优解。,.,3.3.3无约束问题最优解的最优性条件,无约束优化设计问题最优解：,约束优化设计问题最优解：,不受约束条件限制，使目标函数达到最小值的一组设计变量，即最优点x*=x1*,x2*,xn*和最优值f(x*)构成无约束问题最优解。,满足约束条件，使目标函数达到最小值的一组设计变量，即最优点x*=x1*,x2*,xn*和最优值f(x*)构成约束问题最优解。,.,3.3.3无约束问题最优解的最优性条件,X*为无约束极小点即最优点的充要条件：(1);(2)Hessian矩阵H(x*)是正定。,Hessian矩阵H(x*)是否为正定，可用它的各阶主子式来确定。,其中：,若k1，2，n，均有dk(x*)0，则对一切非零向量zx-x*，二次型zTH(x*)z均为大于零，从而Hessian矩阵H(x*)是正定矩阵，x*必为极小点。若对于有(1)k的符号，即dk(x*)是交替的负值和正值，则对于一切非零向量z，二次型zTH(x*)z为小于零，从而Hessian短阵是负定矩阵，x*为极大点。否则，H(x*)是不定矩阵，x*即为鞍点。,.,3.3.3无约束问题最优解的最优性条件,例：求下面函数的无约束最优解,解：按最优解的必要条件,于是可得x1=250 x2代入（b）式可得，x2*4x1*1000为问题的稳定点。,.,用式（a）和（b）可求得f(x)的Hessian矩阵,由于x10和x20，其H(x1，x2)为正定矩阵。因此x*=1000，4T是f(x)函数的局部极小点，由于Hessian矩阵对于一切x10和x20均为正定，函数f(x)是凸函数，所以x*也是全域最小点，其f(x)函数等值线的图形见上图。,3.3.3无约束问题最优解的最优性条件,.,有适时约束目标函数是凸函数,可行域是凸集，则目标函数等值线与适时约束曲面的切点为最优点，而且是全局最优点。,无适时约束目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约束问题的最优点。,x(k)为最优点x*的条件：必要条件：充分条件：Hesse矩阵H(x(k)是正定矩阵,X*,f(x),x*,3.3.4约束问题最优解的最优性条件,.,有适时约束目标函数是非凸函数（图a），或可行域是非凸集（图b）：,则目标函数等值线与适时约束曲面可能存在多个切点，是局部极值点，其中只有一个点是全局最优点。,p,Q,Q,p,3.3.4约束问题最优解的最优性条件,.,目标函数是非凸函数,可行域是非凸集（图c）,图c,3.3.4约束问题最优解的最优性条件,.,K-T(Kuhn-Tucker库恩-塔克)条件有适时约束时获得最优解的条件,1.有一个适时约束时：,与x(k)点目标函数的负梯度方向成锐角，即沿S方向目标函数值下降；与x(k)点约束函数的梯度方向成钝角，即保证S方向上各点在可行域内。此时，获得最优解x(k)为最优点x*，f(x(k)为最优值f(x*)。,从数学上定义，当从x(k)点出发不存在一个S方向能同时满足：;，即，则获得最优解：x(k)为最优点x*，f(x(k)为最优值f(x*)。,从几何上看，当从x(k)点出发不存在一个S方向能同时满足：,3.3.4约束问题最优解的最优性条件,.,相反，当从x(k)点出发，存在一个S方向能同时满足：和时，则x(k)不是最优点。,从几何上看，当从x(k)点出发存在一个S方向能同时满足：与x(k)点目标函数的负梯度方向成锐角，即沿S方向目标函数值下降；与x(k)点约束函数的梯度方向成钝角，即保证S方向上各点在可行域内。此时，x(k)不是最优点x*。,1.有一个适时约束时：,3.3.4约束问题最优解的最优性条件,.,2.有二个适时约束时：,x(k)成为约束最优点x*的必要条件为:,。,几何上位于和所张的扇形子空间内。,即不存在一个S方向能同时满足：,3.3.4约束问题最优解的最优性条件,K-T(Kuhn-Tucker库恩-塔克)条件有适时约束时获得最优解的条件,.,相反，不符合以上条件：,几何上不位于和所张的扇形子空间内。则x(k)点不是最优点。,不能表达成和的线性组合。,即存在一个S方向能同时满足：,2.有二个适时约束时：,3.3.4约束问题最优解的最优性条件,.,3.K-T条件（扩展至m个适时约束）：,设某个设计点x(k)，其适时约束集为，,几何上，x(k)成为约束最优点（极小点）x*时，目标函数的负梯度向量位于m适时约束梯度向量所张成的子空间内。,且为线性独立，则x(k)成为约束最优点的必要条件是目标函数的负梯度向量可表示为适时约束梯度向量的线性组合，即。,其中，。,3.3.4约束问题最优解的最优性条件,.,K-T条件的作用：判别边界设计点x(k)为最优点的依据，见参考书作为约束优化的收敛条件。,问题：K-T条件是否为充分必要条件？若是，说明理由；若不是，则说明什么情况下，可成为充要条件？有等式约束时，K-T条件是否还能适用？,3.3.4约束问题最优解的最优性条件,.,解：起作用约束为I(x(k)=2,3。在x(k)点的各向量为,例3.6试判断x(*)=1,0T是否为下列约束优化问题的最优点：,左图表示了问题的可行域D和目标函数的一些等值线。,解得：,解得2=1和3=1，为非负乘子，满足K-T条件。由于在x(k)点起作用约束为g2(x(k)=g3(x(k)=