机械优化设计方法第五章 多变量无约束优化方法

第五章多变量无约束优化方法5-1概述无约束最优化问题是：求n维设计变量X=[x1,x2,…,xn]T使目标函数为minf(X)，而对X没有任何限制；如果存在X*,使minf(X)=f(X*)分别称X*为最优点，f(X*)为最优值。无约束最优化方法归纳起来可分为两大类。一类是只需要进行函数值的计算与比较来确定迭代方向和步长的直接搜索法，简称直接法；另一类则是要利用函数的一阶或二阶偏导数矩阵来确定迭代方向和步长的间接法。直接搜索法与间接法相比，收敛速度较慢，但它不要求函数具有好的解析性质,适用范围较广。属直接法的有变量（坐标）轮换法、单纯形法、共轭方向法和鲍威尔(Powell)法等属间接法的梯度法、共轭梯度法、牛顿法和变尺度法等。无约束优化方法虽然种类很多，但一般由以下四个部分组成。(1)选择一个初始点X(0),这一点越靠近局部极小点X*越好。(2)如已取得某设计点X(k)(k＝0，1，2，…)，并且该点还不是近似极小点，则在X(k)点根据函数f(X)的性质，选择一个方向S(k)，沿此方向搜索函数值应是下降的，称S(k)为下降方向。(3)当搜索方向S(k)确定以后，由X(k)点出发，沿S(k)方向进行搜索，定出步长因子α(k)，得新设计点X(k+1)=X(k)+α(k)S(k)并满足f(X(k+1))＜f(X(k))。具有这种性质的算法称为下降算法。α(k)可以是一维搜索方法确定的最优步长因子，亦可用其他方法确定。(4)若新点X(k+1)满足迭代计算终止条件，则停止迭代，X(k+1)点就作为近似局部极小点X*；否则，又从X(k+1)点出发，返回第(2)步继续进行搜索迭代。如何产生这些搜索方向——成为各种无约束优化方法的主要特征。5-2变量轮换法一、变量轮换法的原理与计算方法变量轮换法又称坐标轮换法，它是把一个n维无约束最优化问题转化为依次沿相应的n个坐标轴方向的一维最优化问题，并反复进行若干轮循环选代来求解的直接搜索方法。设二元目标函数f(X)=f(x1,x2)。其等值线示于图中。对该二维问题，经过沿e1、e2两次一维搜索称为完成了一轮迭代。第二轮迭代则是以第一轮迭代的末点X2(1)作为第二轮迭代的起始点。X1(2)=X0(2)+α1(2)e1X2(2)=X1(2)+α2(2)e2最后的迭代点必将逼近该二维目标函数的最优点。X1(1)=X0(1)+α1(1)e1X2(1)=X1(1)+α2(1)e2任选一个初始点X(0)作为第一轮的始点X0(1)二、迭代过程及算法框图根据上述原理，对于第k轮计算，变量轮换法迭代公式为Xi(k)=Xi-1(k)+αi(k)Si(k)(i=1,2,…,n)式中Si(k)----搜索方向；αi(k)----步长因子。Si(k)轮流取n维空间各坐标轴的单位向量ei(i=1,2,…,n)，即010ikieS1、加速步长法加速步长法是以成倍数增加的试验步长来寻找新点的方法。2、最优步长法。每次沿一个坐标轴方向搜索时，利用一维搜索法确定最优步长αi(k)，即在第k轮的第i次迭代中，其最优步长αi(k)使minf(Xi-1(k)+α(k)Si(k))=f(Xi-1(k)+αi(k)Si(k))αi(k)取正值或负值均可,但必须使f(Xi(k))＜f(Xi-1(k))，步长因子的选取：搜索步长或步长因子通常有如下两种取法：变量轮换法的具体迭代步骤如下：(1)给定初始点X(0)∈Rn，迭代精度ε，维数n，Si(1)=ei(i=1,2,…,n)。(2)置1→k。(3)置1→i。(4)置X(0)→Xi-1(k)。(5)从Xi-1(k)点出发，沿Si(k)方向进行关于α(k)的一维搜索，求出最优步长α(k)，使f(Xi-1(k)+αi(k)Si(k))=minf(Xi-1(k)+α(k)Si(k))置Xi-1(k)+αi(k)Si(k))→Xi(k)。(6)判别是否满足i＝n?若满足则进行步骤(7)；否则置i+1→i返回步骤(5)。(7)检验是否满足迭代终止条件‖Xn(k)-X0(k)‖≤ε?若满足，迭代停止，得到Xn(k)为最优点，输出Xn(k)→X*，f(Xn(k))→f(X*)；否则置Si(k)→Si(k+1)(i=1,2,…,n)，Xn(k)→X(0)，k+1→k，返回步骤(3)。变量轮换法的算法框图如图5-2所示。1、用变量轮换法寻优就像是沿两个垂直的个固定方向前进，虽然目标函数值是步步降低，但所走的“路”太曲折，所以该方法收敛速度较慢。2、变量轮换法的效能与目标函数的维数有关，当维数增加时效率下降，一般适用于n＜10的低维优化问题。3、这种方法的效能在很大程度上还取决于目标函数的性质。5-3原始共轭方向法一、共轭方向的基本概念关于搜索方向S(k)的选择问题，是最优化方法中所讨论的重要问题之一。以二维正定二次函数为例，采用变量轮换法，其搜索方向是沿两个垂直的固定方向前进，达到极小点要多次变换方向搜索，道路曲折，收敛速度较慢。希望选择的搜索方向尽可能指向目标函数f(X)的极小点。如图5-5所示二维正定二次函数、其等值线是一族同心椭圆，在X(k)点构造的搜索方向最好是通过极小点X*。显然，最理想的方向是S2(k)方向这就是将要介绍的有关“共轭方向”。(二)共轭方向在最优化问题中的应用二维正定二次函数具有两个重要特点1)二维正定二次函数的等值线是同心的椭圆族，且椭圆中心就是以正定二元二次函数为目标函数的极小点X*(图5-6)(一)共轭方向的定义设A为n×n阶实对称正定矩阵，如果有两个n维向量S1和S2满足S1TAS2=0则称向量S1与S2对于矩阵A共轭。共轭向量的方向称为共轭方向。2)过同心椭圆族中心X*作任意直线。此直线与诸椭圆交点处的切线相互平行(图(a))也可以说，如果对同心椭圆族有两条平行的(如图(b)中平行于给定向量X1的方向)任意方向切线l1，l2,其切点X(1)，X(2)的连线方向S2必通过椭圆族的共同中心X*。1.可以推出对于n维正定二次函数，共轭方向的一个十分重要的极为有用的性质：从任意初始点X(0)出发，依次沿n个线性无关的与A共扼的方向S1，S2，…,Sn各进行一维搜索，那么总能在第n步或n步之前就能达到n维正定二次函数的极小点；并且这个性质与所有的n个方向的次序无关。因而说共轭方向法具有有限步收敛的特性。通常称具有这种性质的算法为二次收敛算法。2.理论与实践证明，将二次收敛算法用于非二次的目标函数，亦有很好的效果，但迭代次数不一定保证有限次，即对非二次n维目标函数经n步共轭方向一维搜索不一定就能达到极小点。3.对于非二次的目标函数寻优的另一种处理方法是循环迭代法，即当达n步迭代终点X(n)时还未收敛，此时可将X(n)作为新的初始点，再重新开始迭代，实践证明，这样做要比一直迭代下去具有更好的效果。4.即便对于正定二次函数，在数值计算中，由于数据的舍入以及计算误差的累积，往往破坏了这种共轭性质。二、共轭方向的原始构成三维二次目标函数f(X)的无约束优化问题为例，来说明共扼方向的原始构成。见图5-8对于n维二次目标函数原始共轭方向的构成方法可类同上述步骤进行。现概括为：有一组线性无关的初始基本方向组Si(k)(i＝1，2，…，n)，依次沿Si(k)进行一维最优化搜索，并且以初始点和搜索终点连线作为新的方向，记作Sn+1(k)，再沿Sn+1(k)一维搜索，得完成一环搜索的末点Xn+1(k)。以后每环的初始点总是取上一环的搜索末点，即Xn+1(k)→X0(k+1)，基本方向组Xn+1(k)为将上环的基本方向组去掉第一个方向S1(k)，并以上环的新生方向Sn+1(k)补入本环最后而构成，即Sn+1(k)→Sn(k+1)，再产生该环的新生方向Sn+1(k+1)＝Xn(k+1)−X0(k+1)。对n维目标函数这样的迭代进行n环称为完成一轮迭代。Sn+1(1)，Sn+1(2)，…，Sn+1(n)，这些新方向之间应该构成n个共轭方向。对于正定二次函来说，经n个共轭方向完成—轮迭代的终点Xn+1(n)应为理论极小点。三、迭代过程及算法框图迭代步骤:(1)给定初始点X(0)，迭代精度ε，维数n，迭n线性无关的向量Si(1)＝ei(i＝1,2,…,n)作为初始搜索方向。(2)置1→k。(3)置1→i。(4)置X(0)→Xi−1(k)。(5)从Xi−1(k)点出发，沿Si(k)方向进行关于α(k)的一维搜索，求出最优步长αi(k)，置Xi−1(k)+αi(k)Si(k)→Xi(k)。(6)判别是否满足i＝n?若满足则进行步骤(7);否则置i+1→i返回步骤(5)。(7)计算共轭方向Xn(k)−X0(k)→Sn+1(k)。(8)从X0(k)点出发，沿新方向Sn+1(k)进行关于α(k)的一维搜索，求出最优步长αn+1(k)，置Xn(k)+αn+1(k)Sn+1(k)→Xn+1(k)，获得了一个新方向Sn+1(k)及其Sn+1(k)方向上的极小点Xn+1(k)。(9)判别是否满足k＝n?若不满足则进行步骤(10),否则转向步骤(11)。(10)构成下一循环搜索的搜索方向。去掉前一循环搜索方向组中的第一个方向S1(k),将新搜索方向Sn+1(k)排在Sn(k)之后，构成下一循环搜索的搜索方向，即Si+1(k)→Si(k+1)(i＝1,2,…,n)，Xn+1(k)→X(0)，k+1→k，返回步骤(3)。(11)检验是否满足迭代终止条件║Xn+1(k)−X0(k)║≤ε?若满足，迭代停止，得到Xn+1(k)为最优点，输出Xn+1(k)→X*，f(Xn+1(k))→f(X*)；否则，置Xn+1(k)→X(0)，返回第(2)步开始新的一轮迭代运算)。原始共轭方向法的算法框图如图5-9所示。图5-10显示了二维正定二次函数用原始共轭方向法求极小点的搜索路线，清楚地看出使用两个共轭方向S3(1)和S3(2)后就能达到极小点。从几何意义上将其推广到n维正定二次函数，使用n个共轭方向后理论上亦能达到极小点。说明：1、n维问题共轭方向法的要点是：在每一循环迭代中都有一个初始点X0(k)和n个线性无关的搜索方向Si(k)，i=l，2，…n。从预先给定的初始点X0(k)出发，用坐标轮换法依次沿n个方向进行一维搜索得终点Xn(k)，由始点X0(k)和终点Xn(k)连线得一新的方向Sn+1(k)，用这方向替换原n个方向中的一个，形成下一循环的搜索方向组Si(k+1)（i=l，2，…n）。替换的原则是：去掉原方向组中的第一个方向S1(k)，而将新方向Sn+1(k)排在最后，形成下一循环搜索的搜索方向组Si(k+1)＝Si+1(k)（i=l，2，…n）：并规定从该K循环的搜索终点Xn(k)出发，沿新方向Si(k+1)进行一维搜索得到的极小点Xn+1(k)，作为下一循环迭代的始点，即X0(k+1)＝Xn+1(k)。这样进行n循环迭代后，原方向组中的n个方向便完全由新产生的一组共轭方向所代替。当目标函数是n维正定二次函数时，从理论上讲，经过这样n个循环迭代后，就可以收敛到最优点。2、该算法可能出现的问题上述算法仅具有理论意义，因为在迭代中的n个搜索方向，有可能出现线性相关或接近线性相关，导致搜索过程在降维的空间进行，无法获得函数的极小点，使计算失败。5-4鲍威尔法一、基本愿理鲍威尔(M.J.D.Powell)提出了对原始共轭方向法的改进方法-鲍威尔共轭方向法。这个改进方法与原始共轭方向法的关键区别是在构成第k+1环基本方向组Si(k+1)(i＝1,2,…,n)时,不再总是不管好坏—律去掉前一环的第一个方向S1(k)，并再将前一环的新生方向Sn+1(k)补于最后，而是首先判断前一环的基本方向组Si(k)(i＝1,2,…,n)是否需要更换；如需更换，还要进一步判断前一环原基本方向组中沿某一个方向Sm(k)(1≤m≤n)作一维搜索函数值下降量最大，去掉该方向再将新生方向Sn+1(k)补入最后构成第k+1环的基本方向组以避免线性相关并最接近共轭。判别前一环基