优化设计第八次课

第五章约束优化方法第三节复合形法复合形法是约束优化设计问题的另外一种重要的直接解法，它来源于用于求解无约束优化设计问题的单纯形法，实际上是单纯形法在约束优化设计问题中的发展。由于复合形法的形状不必保持规则的图形，在迭代过程中也不必计算目标函数的一、二阶导数，同时无需进行一维搜索，因此，对目标函数和约束函数的性态无特殊要求，程序较简单。所以，该方法的适应性强，在机械优化设计中得到广泛应用，但随着设计变量和约束条件的增多，其计算效率显著降低。一、复合形法的基本思想复合形法的基本思想如下图所示，在可行域内构造一个具有个顶点的初始复合形，对初始复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点(称最差点)，然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最差点，构成新的复合形，复合形的形状每改变一次，就向最优点移动一步，直至逼近最优点。(12)knkn二、初始复合形的建立复合形是由个顶点组成的一个多面体，每个顶点都必须满足所有的约束条件，例如当时，即在可行域内构成一个三角形或四边形，如下图所示。k2nD生成初始复合形的方法有以下几种。(1)由设计者试选个可行点，构成初始复合形。当设计变量较多或约束函数较复杂时，由设计者决定个可行点常常很困难。只有在设计变量少，约束函数较简单的情况下，这种方法才被使用。kk()()(2,3,...,;1,2,...,)jjiiiiixaqbajkin(2)由设计者在可行城内先选定复合形的一个初始顶点，其余的个顶点用随机方法产生，即(1)X(1)k()(2,3,...,)jXjk——(0，1)区间内均匀分布的伪随机数。式中——复合形顶点的标号；——设计变量的标号，表示点的坐标分量；、——第个设计变量的下限值和上限值；jiiaib()jiqi这样产生的个顶点虽然能满足设计变量的边界约束条件，但不一定就能满足性能约束条件，因此，就要设法将非可行点移到可行域内。具体采用的方法是，首先求出已经在可行域内的P个顶点的形心点，即(1)k()11pjciXXp后将非可行点向中心点移动，即(1)(1)()()()()ppcckkccXXXXXXXX只要形心点为可行点，且系数选择得当(一般取)，总可以使新点满足全部约束条件，即满足cX0.5(1)()()0(1,2,...,)()0(1,2,...,)pjkjgXjmgXjm事实上，只要可行域为凸集，其中心点必为可行点．用此方法可以成功地在可行城内构成初始复合形。如果可行域为非凸集，如下图所示，中心点不一定在可行域之内，则此方法可能失败，这时可以通过改变设计变量的下限值和上限值，重新产生各项点。经过多次试算，有可能在可行域内生成初始复合形。通过对随机产生的各个顶点进行这种处理后，最后可取得个初始可行顶点，从而构成初始复合形。k(3)由计算机自动生成初始复合形的全部顶点。其方法是首先随机产生一个可行点，然后按上述第二种方法产生其余个可行点。这种方法对设计者来说最为简单，但因初始复合形在可行域内的位置不能控制，可能会给以后的计算带来困难。1k三、复合形法的寻优过程现以二维约束优化问题为例来说明复合形法的寻优过程。如下图所示，取二维问题的复合形为三角形，计算其三个顶点的目标函数值并进行比较，则可确定目标函数值最大的点(最差点)，目标函数值次大的点(次差点)和目标函数值最小的点(最好点)，并大致判断目标函数值的变化趋势。()hX()gX()lX若为除去以外个顶点的中心点，在下图中是和连线的中心，则通常是由最差点指向中心点的方向，为目标函数值下降的方向。故在和连线的延长线上取一点，这一步称为反射，称为最差点的反射点，即cX()hX1k()gX()lX()hXcX()hXcX()rX()rX()hX()()()rhccXXXX式中——反射系数，一般取，可取。11.3检查反射点是否为可行点，若在可行城内，且()rX()rX()()()()rhfXfX时，则用反射点替换最差点，并组成新的复合形，完成一次迭代；否则，如果或不在可行域内，则将反射系数减半甚至减至很小，一旦成为可行点，并且满足时，就用()rX()rX()rX()hX()()()()rhfXfX()()()()rhfXfX反射点替换最差点构成新的复合形，完成一次迭代。()rX()hX综上所述，反射成功的条件为()()()()0(1,2,...,)()()rjrhgXjmfXfX但当反射系数减至很小(例如，当)时，仍达不到上式的要求，则可用次差点代替进行反射，组成新的迭代过程。510()gX()hX基本的复合形法(只含反射)的计算步骤如下。四、复合形法的计算步骤(1)选择复合形的顶点个数，按所选生成初始复合形的方法构成具有个顶点的初始复合形。kk(2)计算复合形个顶点的目标函数值，选出其中的最差点，即k()hX()()()max()(1,2,...,)hjfXfXjk()()()max()(1,2,...,,)gjfXfXjkjh次差点，即()gX最好点，即()lX()()()min()(1,2,...,)ljfXfXjk(3)计算除去最差点外其余个顶点的中心点，即()hX1kcX()111kjcjjhXXk检验中心点是否在可行域内。若在可行域内，则继续进行第(4)步；否则，转到第(5)步。cXcX()()()rhccXXXX(4)如果中心点在可行域内，则在和连线的延长线上取反射点，即cX()hXcX一般取反射系数。若超出可行域，为非可行点，则将其退回，即将反射系数减半，令，重新计算反射点，直至反射点成为可行点为止，如下图所示。1.3()rX0.5()rX()rX(5)如果中心点不在可行域内，则可行域可能是一个非凸集，如下图所示。按上式计算的反射点不可能是可行点，此时利用中心点和最好点重新确定一个区间，在此区间内重新按所选生成初始复合形的方法构成具有个顶点的复合形。新的区间如下图中虚线所示，此时设计变量的下限值与上限值为：cX()rXcXk若，则取(1,2,...,)licixxin(1,2,...,)liiiciaxinbx若，则取(1,2,...,)licixxin(1,2,...,)iciliiaxinbx重新构成复合形后再重复第(2)、(3)步，直至成为可行点为止。cX()lX(6)计算反射点的函数值。如果，则用反射点替换最差点，构成新的复合形，完成一次迭代计算，返回第(2)步；否则继续进行下一步。()hX()rX()()()()rhfXfX()()rfX()rX(8)若收敛条件122()()11()()1kjljjlfXfXk(7)如果，则将反射系数减半，令，重新计算反射点。若反射点既为可行点，又满足,用反射点替换最差点，完成本次迭代。否则继续将减半，直到值小于一个预先给定的很小数时，如果目标函数仍无改进，改用次差点来代替前次的最差点，返回第(3)步。()()()()rhfXfX0.5()rX()rX()()()()rhfXfX()rX()hX()gX()hX得到满足，计算终止，此时约束最优解为：，；否则返回第(2)步。*()lXX*()()()lfXfX例：用复合形法求约束优化问题的最优解。T2122212121211221314252min()10460s.t.()110()0()60()0()80XxxRfXxxxxxxgXxxgXxgXxgXxgXx复合形法的特点:1）不用计算目标函数一阶、二阶导数;2）不用一维最优化方法;3）对目标函数和约束函数性态无特殊要求;4）程序简单，适用面比较广;5）当维数n较多时，效率较低;6）复合形（多面体）会退化（降维）,为防止退化，顶点数k可取多一点。已知约束优化问题试以为复合形的初始顶点，用复合形法进行两次迭代计算。课堂练习212221122132min()412s.t.()250()0()0fxxxgxxxgxxgxxTTT(0)(0)(0)12321,41,33,XXX第四节可行方向法可行方向法是用梯度去求解约束优化设计问题的一种有代表性的直接搜索方法，也是求解大型约束优化设计问题的主要方法之一。其收敛速度快，效果较好，适用于大中型约束优化设计问题的求解，但程序比较复杂。一、可行方向法的基本思想可行方向法的基本思想是在可行域内选择一个初始点，当确定了一个可行方向和适当的步长后，按下式(0)X()kSk(1)()()(0,1,2,...)kkkkXXSk进行迭代计算。在不断调整可行方向的过程中，使迭代点逐步逼近约束最优点。二、可行方向法的基本搜索过程在可行方向法的搜索过程中，第一步迭代总是从可行的初始点出发，沿点的负梯度方向，将初始点移至某一个约束面(只有一个起作用的约束时)上或几个约束面的交集(几个约束同时起作用时)上，以后的搜索策略依据约束函数和目标函数的不同性质而有所不同。(0)X(0)(0)()SfX(0)X第一种情况如图(a)所示，在约束面上的迭代点处，产生一个可行方向，沿此方向进行一维搜索，得到的新点在可行域内，即令迭代点，再沿点的负梯度方向继续进行搜索。()kS()kXX(1)kXX(1)kX(1)(1)()kkSfX第二种情况如图(b)所示，沿可行方向进行一维搜索，得到的新点在可行域外，则设法将新点移至约束面上，即取和约束面的交点作为新的迭代点。()kSXX(1)kX()kS第三种情况是沿约束面搜索，这种搜索方法特别适用于只具有线性约束条件的非线性规划问题，如图(c)所示。从点出发，沿某一约束面移动至另一约束面的交线上。在有限步数内即可搜索到约束最优点。()kX对于具有非线性约束函数的非线性规划问题，沿约束面的切线方向进行搜索时，新点又将进入非可行域，如下图所示，此时，须将进入非可行域的新点设法调整到约束面上，然后才能进行下一次迭代。解决这个问题的办法是先规定允许进入非可行域的“深度”，即建立约束容差的边界，然后沿目标函数的梯度方向或起作用约束函数的负梯度方向，将新点返回到约束面上，其计算公式为XX()fX()gX(1)()ktXXfX(1)()ktXXgX式中——调整步长因子，可用试探法决定，或用下式估算tT()()()tgXgXgX尽管可行方向法有几种不同的搜索策略，但其基本的是以下两个决策。(1)产生一个可行方向；()kS(2)沿可行方向确定一个不会越出可行域外的，甚至刚好移动到约束面上的适合步长因子。()kS0三、可行方向法产生可行方向的条件可行方向是指沿该方向做微小移动后，所得到的新点是可行点，且目标函数值有所下降，显然，可行方向应满足可行和下降两个条件。1．可行条件方向的可行条件是指沿该方向做微小移动后，所得到的新点是可行点。如下图(a)所示，若点在一个约束面上，过点作约束面的切线，显然，如果方向满足可行条件，则方向与起作用约束函数在点的梯度的夹角应大于或等于，其向量关系式为()kX()kX()0gX()kS()kS()kX()()kgX090T()()()0kkgXS若在J个起作用约束面的交集上，如下图(b)所示，要求和J个起作用约束函数在点的梯度的夹角均应大于或等于，其向量关系式为()kX()kX()kS090()()kjgX(1,2,...,)jJT()()()0(1,2,...,)kkjgXSjJ2．下降条件方向的下降条件是指沿该方向做微小移动后，所得到的新点目标函数值是下降的。如下图所示，满足下降条件的方向应和目标函数在点的梯度的夹角大于，其向量关系式为()kX()kS090()()kfXT()()(