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

1、1,第三章 优化设计的某些基本概念和处理,3.1 目标函数与约束函数的某些基本性质 3.2约束函数的集合及其性质 3.3 优化设计问题的最优解及其最优性条件 3.4优化设计问题的数值解法及收敛条件,2,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, 等

2、值时，就获得一族曲面族，称为等值面族。,当f(x)是二维时，获得一族等值线族； 当f(x)是三维时，获得一族等值面族； 当f(x)大于三维时，获得一族超等值面族。,3,3.1.1函数的等值面（或线） ：,等值线的“心” （以二维为例）,一个“心”：是单峰函数的极（小）值点，是全局极（小）值点。 没有“心”：例，线性函数的等值线是平行的，无“心”，认为极值点在无穷远处。,多个“心”：不是单峰函数，每个极（小）值点只是局部极（小）值点，必须通过比较各个极值点和“鞍点”（须正确判别）的值，才能确定极（小）值点。,4,3.1.1函数的等值面（或线） ：,等值线的形状： 同心圆族、椭圆族，近似椭圆族；,

3、等值线的疏密： 沿等值线密的方向，函数值变化快； 沿等值线疏的方向，函数值变化慢。 等值线的疏密定性反应函数值变化率。,严重非线性函数病态函数的等值线族是严重偏心和扭曲、分布疏密严重不一的曲线族。,5,3.1.2 函数的最速下降方向,方向导数： 二维问题中，f (x1,x2 ) 在 X(0) 点沿方向 s的方向导数为：,其中：,是 X(0)点的梯度。,S 为s方向的单位向量， 。,为 S 的方向角,方向导数,为方向余弦。,为梯度,在方向 s 上的投影。,6,3.1.2 函数的最速下降方向,梯度的性质：, 梯度是 X(0)点处最大的方向导数； 梯度的方向是过点的等值线的法线方向； 梯度是X(0)

4、 点处的局部性质； 梯度指向函数变化率最大的方向； 正梯度方向是函数值最速上升的方向， 负梯度方向是函数值最速下降的方向。,对于 n 维问题的梯度,7,3.1.3函数局部近似的表达式和平方函数,n 维函数 f(x) 在 x(k) 点的台劳展开式:,二阶近似式：,其中：增量, X (k) =x1 (k) , x2 (k) , xn (k) T,梯度,Hesse 矩阵,Hesse 矩阵与正定,8,3.1.3函数局部近似的表达式和平方函数,Hesse 矩阵的特性：是实对称矩阵。,矩阵正定的充要条件：,主子式 det(ait)0,当主子式 det(ait)0 时，矩阵半正定 det(ait)0时，矩阵

5、负定 det(ait)0时，矩阵半负定,Hesse 矩阵的正定性：,H(x*)正定， 是 x* 为全局极小值点的充分条件； H(x*)半正定, 是 x* 为局部极小值点的充分条件； H(x*)负定， 是 x* 为全局极大值点的充分条件； H(x*)半负定, 是 x* 为局部极大值点的充分条件。,正定的二次函数：曲面为椭圆抛物面； 等值线族为椭圆曲线族，椭圆中心为极小值点。,9,3.1.4函数的凸性,凸集： 设 D为欧氏空间Rn 中X的集合，即 DRn, XD，若D域内任意两个点x(1)，x(2)的连线上的各点都属于 D域，则集合 D称为 Rn 内的一个凸集。否则，为非凸集。,凸函数：,f(x)

6、是定义在 n 维欧氏空间中，凸集上的函数，同时x(1)D，x(2)D，0,1，当下式成立时，,则称f(x)为定义在凸集D上的凸函数。,f x(1) +(1-)x(2) f(x(1) +(1-) f( x(2) ),当上式中的为时，f(x)是严格凸函数。,10,3.1.4函数的凸性,判别函数为凸函数的凸性条件：,按梯度判断凸性：设f(x)是定义在凸集 D上具有连续一阶导数的函数，则f(x)在D上为凸函数的充要条件是：对于任意的 x(1),x(2)D 都有 成立。,按二阶偏导数判断凸性：设 f(x) 是定义在凸集D上具有连续二阶导数的函数，则f(x)在D上为凸函数的充要条件是：f(x)的Hesse

7、矩阵处处半正定。若Hesse矩阵处处正定，则f(x)为严格凸函数。,凸函数的基本性质：,若f(x)是定义在凸集D上的严格凸函数，则f(x)在D上的一个极小点，也就是全局最小点。 凸函数的线性组合仍然为凸函数。 设x(1), x(2)为凸函数 f(x)上的两个最小点，则其连线上的任意点也都是最小点。,11,3.2约束函数的集合及其性质,3.2.1约束集合和可行域,约束集合：是指所有不等式约束和等式约束的交集,即：,由于该集合内所有设计点x都满足全部的约束条件，所以设计可行域可以表示为：,其中假设函数gu(x)和h(x)都是连续的。这样，对于一个约束的优化设计问题，由于约束面的存在而把设计空间划分

8、为两个区域：设计可行域和非可行域。可行域内的各点都满足所有的约束条件，因而最优解或可接受设计解只能从这些点中产生。,12,3.2.1约束集合和可行域,若在可行域内不存在设计点，则认为此可行集合是个空集，此时也就没有可接受的设计解。 关于约束交集或是可行域D是否为一个凸集，在凸规划理论中证明了：若各个不等约束函数gu(x)(u1，2，m)是凸函数和等式约束hv(x)(vl，2，p)是线性函数，则G或D是凸集。但是只要等式约束是非线性的，那么集合G或D一定是个非凸集。,关于约束函数集合的几何概念是很清楚的。例如，对于一个二维问题，当其约束条件为：,13,3.2.1约束集合和可行域,由图310(a)

9、可见，它是一个在第一象限内的凸集D。 当约束条件g3(x)改为,由图310(b)可见，是一个在第一象限内的非凸集D,因为g3(x)函数是一凹函数。,14,3.2.1约束集合和可行域,当约束条件g3(x)取为等式约束,由图310(c)可见，也是一个非凸集D，此时这个集合是在x10和x20(第一象限内)上h(x)0的一段曲线。,值得注意的是，一个约束函数经过变换，虽然表示形式不同，而且也未改变其约束的条件，但有时却会影响约束函数的凸性。,例如，对于x10和x20，且a和b为正常数，其原约束条件形式为,可以等价地变换为下面形式(由于x1和x2均取正值，故不等式的意义没有改变),15,由此，约柬函数通

10、过形式上的变换，结果可能丢失了函数的凸性(或者相反)，这也就影响可行域的约束集合的凸性条件。,式中， 为正定短阵； 为不定短阵。,结果是g1(x)是凸函数，变换为g2(x)则是非凸函数，因为他们的Hessian矩阵分别为,3.2.1约束集合和可行域,当不等式约束都是线性函数时，其约束集合D必为一个凸集。,16,3.2.2起作用约束和松弛约束,对于一个不等式约束g(x)0来说，如果所讨论的设计点x(k)使该约束g(x(k)=0(或者说x(k)当时正处在该约束的边界上)时，则称这个约束是x(k)点的一个起作用约束或紧约束。而其他满足g(x)0的约束称为松弛约束。如图所示，对点x(k)来说，g1和g

11、2是起作用约束，而g3和g4为松弛约束。,当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为,其意义是对x (k)点此时所有起作用约束下标的集合。以上图为例，其I(x(k)1,2。,17,3.2.3冗余约束,如果一个不等式约束条件的约束面(即g=0)对可行域的大小不发生影响，或是约束面不与可行域D相交，即此约束称为冗余约束。,一个约束条件对优化设计模型是否是冗余的，可以根据下面的优势定理来确定；,对于一切的设计点x，若g2(x)g1(x)0，则当约束g1(x)得到满足时，其约束g2(x)也会自动获得满足。而约束g1(x)对g2(x)从整体上是占主导或优势的，这时约束g2(x)则为冗余

12、约束。,18,3.2.3冗余约束,x1,由于g3和g4中的参数值发生变化，g3的约束面向下移，g4的约束面向上移，结果原为冗余的约束g4变为起支配作用，而原起支配作用的g3变为冗余。,（a）g4为冗余（b）g3为冗余,19,3.2.4可行方向,一个设计点x(k)在可行域内是一个自由点，在各个方向上都可以作出移动得到新点，如图所示，但一旦当设计点x(k)处于起作用约束上时，它的移动就会受到可行性的限制。此时x(k)点的可行方向s必满足条件：,上式的极限情况是取等号，这时有：,即可行方向s与该点的约束梯度向量 垂直，夹角为，也就是说，该点的可行方向就是该点约束面的切线方向tt。当式(3-25)小于

13、零时，可行方向s与约束梯度向量 的夹角大于 。,20,3.2.4可行方向,当某个设计点x同时有几个约束起作用时(如上图中的x点是约束g10和约束g20约束面的交点)，其可行方向集合,即图中的阴影线内的任一方向都是可行方向。同理，即有不等约束的起作用约束集合和等式约束集合，其x点的可行方向集合为,21,优化设计是求n个设计变量在满足约束条件下使目标函数达到最小值，即：,3.3 优化设计问题的最优解及其最优性条件,3.3.1 优化设计问题的最优解,我们称x*为最优点，称f(x*)为最优值。最优点x*和最优值f(x*)即构成了一个约束最优解。 如果一组设计变量x1*,x2*, ,xn* 仅使目标函数

14、取最小值，而不受任何约束条件的限制，即,则称x*和f(x*)为无约束最优解。,22,3.3.1 优化设计问题的最优解,例题：求下面问题的最优解,解：如图所示，其中x*4，3T和f(x*)21是约束最优解，是约束边界与目标函数等值线的切点；而x*=8，6T和f(x*)=8是无约束最优解，是目标函数等值线的中心。,其约束最优点一般都应该处于一个或几个起作用约束的集合上，因此有时又称它为边界最优点；显然，起作用约束边界的变动，将改变最优点的位置或优化解的结果。,对于一般有约束的优化问题,23,设x为所有解的集合，D为x上的可行域，f(x)为目标函数，若一切的x(k+1)(N(x(k)D)，满足f(x

15、(k+1)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是凸集时，所计算得的局部最优解可以断定它也就是问题的全域最优解。,24,3.3.3无约束问题最优解的最优性条件,无约束优化设计问题最优解：,约束优化设计问题最优解：,不受约束条件限制，使目标函数达到最小值的一组设计变量，即最优点 x*=x1*,x2*,x n* 和最优值 f(x*)构成无约束问题最优解。,满足约束条件，使目标函数达到

16、最小值的一组设计变量， 即最优点 x*=x1*,x2*,x n* 和最优值 f(x*)构成约束问题最优解。,25,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为小于零，

17、从而Hessian短阵是负定矩阵，x*为极大点。否则， H(x*)是不定矩阵，x*即为鞍点。,26,3.3.3无约束问题最优解的最优性条件,例：求下面函数的无约束最优解,解：按最优解的必要条件,于是可得 x1=250 x2 代入（b）式可得，x2*4 x1*1000为问题的稳定点。,27,用式（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无约束

18、问题最优解的最优性条件,28,有适时约束 目标函数是凸函数,可行域是凸集，则目标函数等值线与适时约束曲面的切点为最优点，而且是全局最优点。,无适时约束 目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约束问题的最优点。,x (k) 为最优点x*的条件： 必要条件： 充分条件： Hesse矩阵 H(x(k) 是正定矩阵,X*,f (x), x*,3.3.4约束问题最优解的最优性条件,29,有适时约束 目标函数是非凸函数（图 a），或可行域是非凸集（图 b）：,则目标函数等值线与适时约束曲面可能存在多个切点，是局部极值点，其中只有一个点是全局最优点。,p,Q,Q,p,3.3.4约束问题最优

19、解的最优性条件,30,目标函数是非凸函数,可行域是非凸集（图 c）,图 c,3.3.4约束问题最优解的最优性条件,31,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

20、(x*)。,从几何上看，当从 x (k)点出发不存在一个 S 方向能同时满足：,3.3.4约束问题最优解的最优性条件,32,相反，当从 x(k)点出发，存在一个 S 方向能同时满足： 和 时，则 x(k) 不是最优点。,从几何上看，当从 x(k)点出发存在一个 S 方向能同时满足： 与x(k)点目标函数的负梯度方向成锐角，即沿 S 方向目标函数值下降； 与x(k)点约束函数的梯度方向成钝角，即保证 S方向上各点在可行域内。 此时，x(k)不是最优点 x*。,1. 有一个适时约束时：,3.3.4约束问题最优解的最优性条件,33,2. 有二个适时约束时：,x(k)成为约束最优点 x* 的必要条件为

21、:,。,几何上 位于 和 所张的扇形子空间内。,即不存在一个 S 方向能同时满足：,3.3.4约束问题最优解的最优性条件,K-T ( Kuhn-Tucker 库恩-塔克) 条件 有适时约束时获得最优解的条件,34,相反，不符合以上条件：,几何上 不位于 和 所张的扇形子空间内。则 x(k) 点不是最优点。,不能表达成 和 的线性组合。,即存在一个 S 方向能同时满足：,2. 有二个适时约束时：,3.3.4约束问题最优解的最优性条件,35,3. K-T 条件（扩展至 m 个适时约束）：,设某个设计点 x(k)，其适时约束集为 ，,几何上，x(k)成为约束最优点（极小点）x*时，目标函数的负梯度向

22、量位于 m 适时约束梯度向量所张成的子空间内。,且 为线性独立，则 x(k)成为约束最优点的必要条件是目标函数的负梯度向量可表示为适时约束梯度向量的线性组合，即 。,其中， 。,3.3.4约束问题最优解的最优性条件,36,K-T条件的作用： 判别边界设计点 x(k) 为最优点的依据，见参考书 作为约束优化的收敛条件。,问题： K-T条件是否为充分必要条件？若是，说明理由；若不是，则说明什么情况下，可成为充要条件？ 有等式约束时，K-T条件是否还能适用？,3.3.4约束问题最优解的最优性条件,37,解：起作用约束为I(x(k)=2,3。在x(k)点的各向量为,例3.6试判断x(*)=1,0T是否为下列约束优化问题