《第三章优化设计的某些基本概念和理论301PPT课件》由会员分享,可在线阅读,更多相关《第三章优化设计的某些基本概念和理论301PPT课件(41页珍藏版)》请在金锄头文库上搜索。
1、第三章第三章 优化设计的某些基本概念和处理优化设计的某些基本概念和处理3.1 3.1 目标函数与约束函数的某些基本性质目标函数与约束函数的某些基本性质3.23.2约束函数的集合及其性质约束函数的集合及其性质3.3 3.3 优化设计问题的最优解及其最优性条件优化设计问题的最优解及其最优性条件3.43.4优化设计问题的数值解法及收敛条件优化设计问题的数值解法及收敛条件13.13.1目标函数与约束函数的某些基本性质目标函数与约束函数的某些基本性质3.1.1函数的函数的等值面等值面(或线)(或线) : 对于可计算的函数对于可计算的函数 f(x) f(x),给定一个设计点,给定一个设计点 X X(k)(
2、k)(x(x1 1(k)(k),x,x2 2(k)(k), ,x, ,xn n (k)(k) ),f(x)f(x)总有一个定值总有一个定值c c 与之对应;而当与之对应;而当f(x)f(x)取定值取定值 c c 时,则有无限多时,则有无限多个设计点个设计点X X(i)(i)(x(x1 1(i)(i), x, x2 2(i)(i), ,x, ,xn n(i)(i) ) ) (i=1,2, i=1,2, )与之对应,这些点)与之对应,这些点集构成一个曲面,称为集构成一个曲面,称为等值面等值面。 当当 c c 取取c c1 1,c,c2 2, , 等等值时,就获得一族曲面值时,就获得一族曲面族,称为
3、族,称为等值面族等值面族。 当当f(x)f(x)是二维时,是二维时,获得一族等值线族;获得一族等值线族; 当当f(x)f(x)是三维时,是三维时,获得一族等值面族;获得一族等值面族; 当当f(x)f(x)大于三维时,大于三维时,获得一族超等值面族。获得一族超等值面族。23.1.13.1.1函数的等值面(或线)函数的等值面(或线) :等值线的等值线的“心心” ” (以二维为例) 一个一个“心心”:是单峰函数的:是单峰函数的极(小)值点极(小)值点,是全局极(小)值点。,是全局极(小)值点。 没有没有“心心”:例,线性函数的等值线是平行的,无:例,线性函数的等值线是平行的,无“心心”,认为,认为极
4、值点在无穷远处。极值点在无穷远处。 多个多个“心心”:不是单峰函数,每个极(小)值点只是局部极(小):不是单峰函数,每个极(小)值点只是局部极(小)值点,必须通过比较各个极值点和值点,必须通过比较各个极值点和“鞍点鞍点”(须正确判别)的值,才(须正确判别)的值,才能确定极(小)值点。能确定极(小)值点。33.1.13.1.1函数的等值面(或线)函数的等值面(或线) :等值线的形状等值线的形状: 同心圆族、椭圆族,近似椭圆族;同心圆族、椭圆族,近似椭圆族;等值线的疏密等值线的疏密: 沿等值线密的方向,函数值变化快;沿等值线密的方向,函数值变化快; 沿等值线疏的方向,函数值变化慢。沿等值线疏的方向
5、,函数值变化慢。 等值线的疏密定性反应函数值变化率。等值线的疏密定性反应函数值变化率。 严重非线性函数严重非线性函数病态函数的等病态函数的等值线族是严重偏心和扭曲、分布疏密值线族是严重偏心和扭曲、分布疏密严重不一的曲线族。严重不一的曲线族。43.1.23.1.2 函数的最速下降方向函数的最速下降方向方向导数方向导数: 二维问题中,二维问题中,f (xf (x1 1,x,x2 2 ) ) 在在 X X(0) (0) 点沿点沿方向方向 s s的方向导数为:的方向导数为:其中:其中:是是 X X(0)(0)点的梯度。点的梯度。S S 为为s s方向的单位向量,方向的单位向量, 。 为为 S S 的方
6、向角的方向角, ,方向导数方向导数为方向余弦。为方向余弦。为梯度为梯度在方向在方向 s s 上的投影。上的投影。53.1.2 3.1.2 函数的最速下降方向函数的最速下降方向梯度的性质:梯度的性质: 梯度是梯度是 X X(0)(0)点处最大的方向导数;点处最大的方向导数; 梯度的方向是过点的等值线的法线方向;梯度的方向是过点的等值线的法线方向; 梯度是梯度是X X(0)(0) 点处的局部性质;点处的局部性质; 梯度指向函数变化率最大的方向;梯度指向函数变化率最大的方向; 正梯度方向是函数值最速上升的方向,正梯度方向是函数值最速上升的方向, 负梯度方向是负梯度方向是函数值最速下降的方向。函数值最
7、速下降的方向。 对于对于 n n 维问题的梯度维问题的梯度63.1.33.1.3函数局部近似的表达式和平方函数函数局部近似的表达式和平方函数n n 维函数维函数 f(x) f(x) 在在 x x(k)(k) 点的台劳展开式点的台劳展开式: :二阶近似式:二阶近似式:其中:增量其中:增量 X (k) =x1 (k) , x2 (k) , xn (k) T梯度梯度 Hesse Hesse 矩阵矩阵 Hesse Hesse 矩阵与正定矩阵与正定73.1.33.1.3函数局部近似的表达式和平方函数函数局部近似的表达式和平方函数Hesse Hesse 矩阵的特性:是实对称矩阵。矩阵的特性:是实对称矩阵。
8、 矩阵正定的充要条件:矩阵正定的充要条件:主子式主子式 det(ait) det(ait)0 0当主子式当主子式 det(ait)0 det(ait)0 时,矩阵半正定时,矩阵半正定 det(ait) det(ait)0 0时,矩阵负定时,矩阵负定 det(ait)0 det(ait)0时,矩阵半负定时,矩阵半负定Hesse Hesse 矩阵的正定性:矩阵的正定性:H(x*)H(x*)正定,正定, 是是 x* x* 为全局极小值点的充分条件为全局极小值点的充分条件;H(x*)H(x*)半正定半正定, , 是是 x* x* 为局部极小值点的充分条件;为局部极小值点的充分条件;H(x*)H(x*)
9、负定,负定, 是是 x* x* 为全局极大值点的充分条件;为全局极大值点的充分条件;H(x*)H(x*)半负定半负定, , 是是 x* x* 为局部极大值点的充分条件。为局部极大值点的充分条件。正定的二次函数:曲面为椭圆抛物面;正定的二次函数:曲面为椭圆抛物面; 等值线族为椭圆曲线族,椭圆中心为极小值点。等值线族为椭圆曲线族,椭圆中心为极小值点。83.1.43.1.4函数的凸性函数的凸性凸集:凸集: 设设 D D为欧氏空间为欧氏空间R Rn n 中中X X的集合,即的集合,即 DR DRn n, , XDXD,若,若D D域内任意两个点域内任意两个点x x(1)(1),x x(2)(2)的连线
10、的连线上的各点都属于上的各点都属于 D D域,则集合域,则集合 D D称为称为 R Rn n 内的内的一个凸集。否则,为非凸集。一个凸集。否则,为非凸集。 凸函数:凸函数: f(x)f(x)是定义在是定义在 n n 维欧氏空间中,凸集维欧氏空间中,凸集上的函数,同时上的函数,同时x x(1)(1)DD,x x(2)(2)DD,0,10,1,当下式成立时,当下式成立时,则称则称f(x)f(x)为定义在凸集为定义在凸集D D上的凸函数。上的凸函数。f x(1) +(1-)x(2) f(x(1) +(1-) f( x(2) ) 当上式中的当上式中的为时,为时,f(x)f(x)是严格凸函数。是严格凸函
11、数。93.1.43.1.4函数的凸性函数的凸性判别函数为凸函数的凸性条件判别函数为凸函数的凸性条件:l 按梯度判断凸性:设按梯度判断凸性:设f(xf(x) )是定义在凸集是定义在凸集 D D上具有连续一阶导数的函数,上具有连续一阶导数的函数,则则f(xf(x) )在在D D上为凸函数的充要条件是:对于任意的上为凸函数的充要条件是:对于任意的 x x(1)(1),x,x(2)(2)D D 都有都有 成立。成立。l 按二阶偏导数判断凸性:设按二阶偏导数判断凸性:设 f(x)f(x) 是定义在凸集是定义在凸集D D上具有连续二阶上具有连续二阶导数的函数,则导数的函数,则f(x)f(x)在在D D上为
12、凸函数的充要条件是:上为凸函数的充要条件是:f(x)f(x)的的HesseHesse矩矩阵处处半正定。若阵处处半正定。若HesseHesse矩阵处处正定,则矩阵处处正定,则f(x)f(x)为严格凸函数。为严格凸函数。凸函数的基本性质凸函数的基本性质:l 若若f(x)f(x)是定义在凸集是定义在凸集D D上的严格凸函数,则上的严格凸函数,则f(x)f(x)在在D D上的一个极小点,上的一个极小点,也就是全局最小点。也就是全局最小点。l 凸函数的线性组合仍然为凸函数。凸函数的线性组合仍然为凸函数。l 设设x x(1)(1), x, x(2)(2)为凸函数为凸函数 f(x)f(x)上的两个最小点,则
13、其连线上的任意点也上的两个最小点,则其连线上的任意点也都是最小点。都是最小点。103.23.2约束函数的集合及其性质约束函数的集合及其性质3.2.13.2.1约束集合和可行域约束集合和可行域约束集合:是指所有不等式约束和等式约束的交集即:由于该集合内所有设计点由于该集合内所有设计点x x都满足全部的约束条件,都满足全部的约束条件,所以所以设计可行域设计可行域可以表示为:可以表示为:其中假设函数其中假设函数g gu u(x)(x)和和h(x)h(x)都是连续的。这样,对于一个都是连续的。这样,对于一个约束的优化设计问题,由于约束面的存在而把设计空间划分为约束的优化设计问题,由于约束面的存在而把设
14、计空间划分为两个区域:两个区域:设计可行域设计可行域和和非可行域非可行域。可行域内的各点都满足所。可行域内的各点都满足所有的约束条件,因而最优解或可接受设计解只能从这些点中产有的约束条件,因而最优解或可接受设计解只能从这些点中产生。生。113.2.13.2.1约束集合和可行域约束集合和可行域 若在可行域内不存在设计点,则认为此可行集合是个若在可行域内不存在设计点,则认为此可行集合是个空空集集,此时也就没有可接受的设计解。,此时也就没有可接受的设计解。 关于约束交集或是可行域关于约束交集或是可行域D D是否为一个凸集,在凸规划是否为一个凸集,在凸规划理论中证明了:理论中证明了:若各个不等约束函数
15、若各个不等约束函数g gu u(x)(u(x)(u1 1,2 2,m)m)是凸函数和等式约束是凸函数和等式约束h hv v(x)(v(x)(vl l,2 2,p)p)是线性函数,则是线性函数,则G G或或D D是凸集。但是只要等式约束是非线性的,那么集合是凸集。但是只要等式约束是非线性的,那么集合G G或或D D一定是个非凸集。一定是个非凸集。关于约束函数集合的几何概念是很清楚的。例如,关于约束函数集合的几何概念是很清楚的。例如,对于一个二维问题,当其约束条件为:对于一个二维问题,当其约束条件为:123.2.13.2.1约束集合和可行域约束集合和可行域由图由图3 310(a)10(a)可见,它
16、是一个在第一象限内的凸集可见,它是一个在第一象限内的凸集D D。当约束条件当约束条件g g3 3(x)(x)改为改为由图由图3 310(b)10(b)可见,是一个在第一象限内的非凸集可见,是一个在第一象限内的非凸集D,D,因为因为g g3 3(x)(x)函数是一凹函数。函数是一凹函数。133.2.13.2.1约束集合和可行域约束集合和可行域当约束条件当约束条件g g3 3(x)(x)取为等式约束取为等式约束由图由图3 310(c)10(c)可见,也是一个非凸集可见,也是一个非凸集D D,此时这个集合,此时这个集合是在是在x x1 100和和x x2 20(0(第一象限内第一象限内) )上上h(
17、x)h(x)0 0的一段曲线。的一段曲线。值得注意的是,一个约束函数经过变换,虽然表示值得注意的是,一个约束函数经过变换,虽然表示形式不同,而且也未改变其约束的条件,但有时却会影形式不同,而且也未改变其约束的条件,但有时却会影响约束函数的凸性。响约束函数的凸性。例如,对于例如,对于x x1 100和和x x2 200,且,且a a和和b b为正常数,其为正常数,其原约束条件形式为原约束条件形式为 可以等价地变换为下面形式可以等价地变换为下面形式( (由于由于x x1 1和和x x2 2均取正值,故均取正值,故不等式的意义没有改变不等式的意义没有改变) )14由此,约柬函数通过形式上的变换,结果
18、可能由此,约柬函数通过形式上的变换,结果可能丢失了函数的凸性丢失了函数的凸性( (或者相反或者相反) ),这也就影响可行域,这也就影响可行域的约束集合的凸性条件。的约束集合的凸性条件。式中,式中, 为正定短阵;为正定短阵; 为不定短阵。为不定短阵。 结果是结果是g g1 1(x)(x)是凸函数,变换为是凸函数,变换为g g2 2(x)(x)则是非凸则是非凸函数,因为他们的函数,因为他们的HessianHessian矩阵分别为矩阵分别为3.2.13.2.1约束集合和可行域约束集合和可行域当不等式约束都是线性函数时,其约束集合当不等式约束都是线性函数时,其约束集合D D必为一个凸集。必为一个凸集。
19、153.2.23.2.2起作用约束和松弛约束起作用约束和松弛约束对于一个不等式约束对于一个不等式约束g(x)0g(x)0来说,如果所讨论的设计来说,如果所讨论的设计点点x x(k)(k)使该约束使该约束g(xg(x(k)(k)=0()=0(或者说或者说x x(k)(k)当时正处在该约束的边界上当时正处在该约束的边界上) )时,时,则称这个约束是则称这个约束是x x(k)(k)点的一个点的一个起作起作用约束用约束或或紧约束紧约束。而其他满足。而其他满足g(x)0g(x)0的约束称为的约束称为松弛约束松弛约束。如。如图所示,对点图所示,对点x x(k)(k)来说,来说,g g1 1和和g g2 2
20、是起是起作用约束,而作用约束,而g g3 3和和g g4 4为松弛约束。为松弛约束。当一个设计点同时有几个约束起作用时,即可定义起当一个设计点同时有几个约束起作用时,即可定义起作用约束集合为作用约束集合为其意义是对其意义是对x x (k)(k)点此时所有起作用约束下标的集合。以上图点此时所有起作用约束下标的集合。以上图为例,其为例,其I I(x(x(k)(k) )1,21,2。163.2.33.2.3冗余约束冗余约束 如果一个不等式约束条件的约束面如果一个不等式约束条件的约束面( (即即g=0)g=0)对可行域对可行域的大小不发生影响,或是约束面不与可行域的大小不发生影响,或是约束面不与可行域
21、D D相交,即此相交,即此约束称为约束称为冗余约束冗余约束。 一个约束条件对优化设计模型是否是冗余的,可以根据一个约束条件对优化设计模型是否是冗余的,可以根据下面的下面的优势定理优势定理来确定;来确定; 对于一切的设计点对于一切的设计点x x,若,若g g2 2(x)g(x)f(x)f(x(k)(k) ),则称,则称x x(k)(k)为该目标函数在为该目标函数在D D上的上的局局部最优点部最优点;若一切的;若一切的x x(k+1)(k+1)(XD) (XD) ,满足,满足f(xf(x(k+1)(k+1)f)f(x(x(k)(k) ) ,则称,则称x x (k)(k)为为D D上的上的全局最优点
22、全局最优点。3.3.2 3.3.2 局部最优点和全局最优点局部最优点和全局最优点因此,只有当日标函数在约束可行域因此,只有当日标函数在约束可行域D D内是内是单蜂函数和约束集合单蜂函数和约束集合D D是凸集时,所计算得的局是凸集时,所计算得的局部最优解可以断定它也就是问题的全域最优解。部最优解可以断定它也就是问题的全域最优解。233.3.33.3.3无约束问题最优解的最优性条件无约束问题最优解的最优性条件无约束优化设计问题最优解:无约束优化设计问题最优解:约束优化设计问题最优解约束优化设计问题最优解: 不受约束条件限制,使目标函数达到最小值的一组设计变量,即最不受约束条件限制,使目标函数达到最
23、小值的一组设计变量,即最优点优点 x*=x x*=x1 1*,x*,x2 2*,x*,x n n* * 和最优值和最优值 f(x*) f(x*)构成无约束问题最优解。构成无约束问题最优解。 满足约束条件,使目标函数满足约束条件,使目标函数达到最小值的一组设计变量,达到最小值的一组设计变量, 即最优点即最优点 x*=x x*=x1 1*,x*,x2 2*,x*,x n n* * 和最优值和最优值 f(x*) f(x*)构成约束问题最构成约束问题最优解。优解。243.3.33.3.3无约束问题最优解的最优性条件无约束问题最优解的最优性条件X X* *为无约束极小点即最优点的充要条件:为无约束极小点
24、即最优点的充要条件: (1) ; (1) ; (2)Hessian (2)Hessian矩阵矩阵H(xH(x* *) )是正定。是正定。HessianHessian矩阵矩阵H(x*)H(x*)是否为正定,可用它的各阶主子式来确定。是否为正定,可用它的各阶主子式来确定。其中:其中:若若k k1 1,2 2,n n,均有,均有d dk k(x(x* *)0)0,则对一切非零向量,则对一切非零向量z zx-xx-x* *,二次型二次型z zT TH H(x(x* *) z) z均为大于零,从而均为大于零,从而HessianHessian矩阵矩阵H(xH(x* *) )是正定矩阵,是正定矩阵,x x*
25、 *必为必为极小点极小点。若对于有。若对于有(1)(1)k k的符号,即的符号,即dk(xdk(x* *) )是交替的负值和正是交替的负值和正值,则对于一切非零向量值,则对于一切非零向量z z,二次型,二次型z zT TH H(x(x* *) z) z为小于零,从而为小于零,从而HessianHessian短阵是负定矩阵,短阵是负定矩阵,x x* *为为极大点极大点。否则,。否则, H(x H(x* *) )是不定矩阵,是不定矩阵,x x* *即为即为鞍点鞍点。253.3.33.3.3无约束问题最优解的最优性条件无约束问题最优解的最优性条件例:求下面函数的无约束最优解例:求下面函数的无约束最优
26、解解:按最优解的必要条件解:按最优解的必要条件于是可得于是可得 x x1 1=250x=250x2 2 代入(代入(b b)式可得,)式可得,x x2 2* *4 4x x1 1* *10001000为问题的稳定点。为问题的稳定点。26用式(用式(a a)和()和(b b)可求得)可求得f(x)f(x)的的HessianHessian矩阵矩阵由于由于x x1 10 0和和x x2 20 0,其,其H(xH(x1 1,x x2 2) ) 为正为正定矩阵。因此定矩阵。因此x x* *=1000=1000,44T T是是f(x)f(x)函数的局函数的局部极小点,由于部极小点,由于HessianHes
27、sian矩阵对于一切矩阵对于一切x x1 100和和x x2 200均为正定,函数均为正定,函数f(x)f(x)是凸函数,所以是凸函数,所以x x* *也是全域最小点,其也是全域最小点,其f(x)f(x)函数等值线的图函数等值线的图形见上图。形见上图。3.3.33.3.3无约束问题最优解的最优性条件无约束问题最优解的最优性条件272.2.有适时约束有适时约束3.3. 目标函数是凸函数目标函数是凸函数, ,可行域是可行域是凸集,则目标函数等值线与适时凸集,则目标函数等值线与适时约束曲面的切点为最优点,而且约束曲面的切点为最优点,而且是全局最优点。是全局最优点。1.无适时约束无适时约束2. 目标函
28、数是凸函数,可行域是目标函数是凸函数,可行域是凸集,则最优点是内点。相当于无凸集,则最优点是内点。相当于无约束问题的最优点。约束问题的最优点。x x (k)(k) 为最优点为最优点x*x*的条件:的条件:必要条件:必要条件:充分条件:充分条件: Hesse Hesse矩阵矩阵 H(x H(x(k)(k) ) 是正定矩阵是正定矩阵X*f (x) x*3.3.43.3.4约束问题最优解的最优性条件约束问题最优解的最优性条件283.3.有适时约束有适时约束4.4. 目标函数是非凸函数(图目标函数是非凸函数(图 a a),),或可行域是非凸集(图或可行域是非凸集(图 b b):): 则目标函数等值线与
29、适时约束曲面可能存在多个切点,是则目标函数等值线与适时约束曲面可能存在多个切点,是局部极值点,其中只有一个点是全局最优点。局部极值点,其中只有一个点是全局最优点。pQQp3.3.43.3.4约束问题最优解的最优性条件约束问题最优解的最优性条件29目标函数是非凸函数目标函数是非凸函数, ,可行域是非凸集(图可行域是非凸集(图 c c)图图 c c3.3.43.3.4约束问题最优解的最优性条件约束问题最优解的最优性条件30 K-T K-T ( Kuhn-Tucker ( Kuhn-Tucker 库恩库恩- -塔克塔克) ) 条件条件 有适时约束时获得最优解的条件有适时约束时获得最优解的条件1. 1
30、. 有一个适时约束时:有一个适时约束时: 与与x x(k)(k)点目标函数的负梯度方向成锐角,点目标函数的负梯度方向成锐角,即沿即沿 S S 方向目标函数值下降;方向目标函数值下降; 与与x x(k)(k)点约束函数的梯度方向成钝角,即点约束函数的梯度方向成钝角,即保证保证 S S方向上各点在可行域内。方向上各点在可行域内。 此时,获得最优解此时,获得最优解 x x(k)(k) 为最优点为最优点 x* x*,f(xf(x(k)(k) )为最优值为最优值 f(x*) f(x*)。 从数学上定义,当从从数学上定义,当从 x x(k)(k)点出发点出发不存在不存在一个一个 S S 方向能同时满足:方
31、向能同时满足: ; ;,即,即 , 则获得最优解:则获得最优解:x x(k)(k)为最优点为最优点 x* x*,f(xf(x(k)(k) )为最优值为最优值 f(x*) f(x*)。从几何上看,当从从几何上看,当从 x (k) x (k)点出发不存在一个点出发不存在一个 S S 方向能同时满足方向能同时满足:3.3.43.3.4约束问题最优解的最优性条件约束问题最优解的最优性条件31 相反,当从相反,当从 x x(k)(k)点出发,点出发,存在存在一个一个 S S 方方向能同时满足:向能同时满足: 和和 时,则时,则 x x(k)(k) 不是最优点。不是最优点。 从几何上看,当从从几何上看,当
32、从 x x(k)(k)点出发存在一个点出发存在一个 S S 方向能同时满足:方向能同时满足: 与与x x(k)(k)点目标函数的负梯度方向成锐角,点目标函数的负梯度方向成锐角,即沿即沿 S S 方向目标函数值下降;方向目标函数值下降; 与与x x(k)(k)点约束函数的梯度方向成钝角,即点约束函数的梯度方向成钝角,即保证保证 S S方向上各点在可行域内。方向上各点在可行域内。 此时,此时,x x(k)(k)不是最优点不是最优点 x* x*。1. 1. 有一个适时约束时:有一个适时约束时:3.3.43.3.4约束问题最优解的最优性条件约束问题最优解的最优性条件322. 2. 有二个适时约束时:有
33、二个适时约束时: x x(k)(k)成为约束最优点成为约束最优点 x* x* 的必要条件为的必要条件为: :。 几何上几何上 位于位于和和 所张的扇形子空间内。所张的扇形子空间内。即不存在一个即不存在一个 S S 方向能同时满足:方向能同时满足:3.3.43.3.4约束问题最优解的最优性条件约束问题最优解的最优性条件 K-T K-T ( Kuhn-Tucker ( Kuhn-Tucker 库恩库恩- -塔克塔克) ) 条件条件 有适时约束时获得最优解的条件有适时约束时获得最优解的条件33相反,不符合以上条件:相反,不符合以上条件: 几何上几何上 不位于不位于 和和 所张的扇形子空间内。则所张的
34、扇形子空间内。则 x x(k)(k) 点不点不是最优点。是最优点。不能表达成不能表达成 和和 的线性组合。的线性组合。即存在一个即存在一个 S S 方向能同时满足:方向能同时满足:2. 2. 有二个适时约束时:有二个适时约束时:3.3.43.3.4约束问题最优解的最优性条件约束问题最优解的最优性条件343. K-T 3. K-T 条件(扩展至条件(扩展至 m m 个适时约束):个适时约束): 设某个设计点设某个设计点 x x(k)(k),其适时约束集为,其适时约束集为 , 几何上,几何上,x x(k)(k)成为约束最优成为约束最优点(极小点)点(极小点)x*x*时,目标函数时,目标函数的负梯度
35、向量位于的负梯度向量位于 m m 适时约束适时约束梯度向量所张成的子空间内。梯度向量所张成的子空间内。且且 为线性独立,则为线性独立,则 x x(k)(k)成为约束最优点的必要条件是成为约束最优点的必要条件是目标目标函数的负梯度向量可表示为适时约束梯度向量的线性组合,即函数的负梯度向量可表示为适时约束梯度向量的线性组合,即 。 其中,其中, 。3.3.43.3.4约束问题最优解的最优性条件约束问题最优解的最优性条件35K-TK-T条件的作用:条件的作用:l 判别边界设计点判别边界设计点 x x(k(k) ) 为最优点的依据,见参考书为最优点的依据,见参考书l 作为约束优化的收敛条件。作为约束优
36、化的收敛条件。问题:问题:l K-TK-T条件是否为充分必要条件?若是,说明理由;若不是,条件是否为充分必要条件?若是,说明理由;若不是,则说明什么情况下,可成为充要条件?则说明什么情况下,可成为充要条件?l 有等式约束时,有等式约束时,K-TK-T条件是否还能适用?条件是否还能适用?3.3.43.3.4约束问题最优解的最优性条件约束问题最优解的最优性条件36解:起作用约束为解:起作用约束为I I(x(x(k)(k)=2,3)=2,3。在在x x(k)(k)点的各向量为点的各向量为例例3.63.6试判断试判断x x(*)(*)=1,0=1,0T T是否为下列约束优化问题的最是否为下列约束优化问
37、题的最优点:优点: 左图表示了问题的可行域左图表示了问题的可行域D D和目标函数的一些等值线。和目标函数的一些等值线。解得:解得:解得解得2 2=1=1和和3 3=1=1,为非负乘子,满,为非负乘子,满足足K-TK-T条件。由于在条件。由于在x(k)x(k)点起作用约束为点起作用约束为g g2 2(x(x(k)(k)=g)=g3 3(x(x(k)(k)=0)=0,而,而2 2=3 3=1=1,对非,对非起作用约束起作用约束g g1 1(x(x(k)(k)0,)0,而而1 1=0=0,所以这,所以这些些值满足下式值满足下式因此因此,x,x(k)(k)点为该问题的约束最优点点为该问题的约束最优点x
38、*x*。37例例3.73.7试判断试判断x x(*)(*)=1,0=1,0T T是否为下列约束优化问题的最是否为下列约束优化问题的最优点:优点:解:解: x x(k)(k)点的起作用约束集合为点的起作用约束集合为I I(x(x(k)(k)=2,3)=2,3。 这个方程组无解,因两个起作用约束的梯度向量是这个方程组无解,因两个起作用约束的梯度向量是线性相关的,所以不存在满足式线性相关的,所以不存在满足式(3-36)(3-36)的的2 2和和3 3值。值。 左图表示了问题的可行域左图表示了问题的可行域D D和目标函数的一些等值线。和目标函数的一些等值线。因此,因此,x x(k)(k)点不是该点不是
39、该问题的约束最优点。问题的约束最优点。383.4 3.4 优化设计问题的数值解法及收敛条件优化设计问题的数值解法及收敛条件3.4.13.4.1数值计算迭代法的基本思想和迭代格式:数值计算迭代法的基本思想和迭代格式:基本思想基本思想: 从设计点从设计点 x x(k)(k)出发,根据函数在该点的某些(局部)性质,出发,根据函数在该点的某些(局部)性质,确定本次搜索的方向确定本次搜索的方向 S S(k) (k) 和步长因子和步长因子(k)(k) ,从而达到一个新点,从而达到一个新点 x x(k+1)(k+1),逐步调优,最终达到或逼近目标函数的最优点。逐步调优,最终达到或逼近目标函数的最优点。 迭代
40、公式迭代公式: x x(k+1)(k+1) = x = x(k)(k) + +(k)(k) S S(k)(k) 迭代条件迭代条件: 保证得到的新点保证得到的新点 在可行域内;在可行域内; 目标函数值步步下降。目标函数值步步下降。393.4.13.4.1数值计算迭代法的基本思想和迭代格式:数值计算迭代法的基本思想和迭代格式:迭代步骤迭代步骤: 选择合适的初始点;选择合适的初始点; 寻找可行的搜索方向;寻找可行的搜索方向; 确定步长因子;确定步长因子; 获得新点后,判断其是否在可行域内、获得新点后,判断其是否在可行域内、目标函数值是否下降;目标函数值是否下降; 检验是否收敛。检验是否收敛。403.
41、4.23.4.2无约束优化迭代计算的终止准则无约束优化迭代计算的终止准则1.1.当当 时,时, 。2.2. 依据:判断无约束优化问题最优点的必要条件:依据:判断无约束优化问题最优点的必要条件:3.3. 局限性:可能迭代终止在鞍点上。局限性:可能迭代终止在鞍点上。 2.2.当当 时,或当时,或当 时时 。3.3. 依据:柯西准则依据:柯西准则序列极限存在的判别法;序列极限存在的判别法;4.4. 局限性:遇到陡坡,迭代过早结束。局限性:遇到陡坡,迭代过早结束。3.3.当当 4.4. 时,时, 。5.5. 局限性:局限性:目标函数值变目标函数值变化过缓时,过早结束;化过缓时,过早结束; 6.6. 当当 f(xf(x(k-1)(k-1) )0 )0 时不时不可用。可用。41