第四章 无约束优化方法.doc

《第四章 无约束优化方法.doc》由会员分享，可在线阅读，更多相关《第四章 无约束优化方法.doc（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 无约束优化方法在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。无约束优化问题的一般形式可描述为：求n维设计变量使目标函数 （4.1)对于上述无约束优化问题的求解，可以利用第二章讲述的无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方程的解。也就是求使其满足解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。但上式是一个含有个未知量，个

2、方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，要用数值计算的方法。由第二章的讲述我们知道，优化问题的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用数值迭代的方法直接求解无约束极值问题。数值迭代法的基本思想是从一个初始点出发，按照一个可行的搜索方向搜索，确定最佳的步长使函数值沿方向下降最大，得到点。依此一步一步地重复数值计算，最终达到最优点。优化计算所采用的基本迭代公式为 （4.2）由上面的迭代公式可以看出，采用数值法进行迭代求优时，需要确定初始点、搜索方向和迭代步长，称为优化方法迭代算法的三要素。第三章我们已经讨论了如何在搜索方向上确定最优步长的方法，本

3、章我们将讨论如何确定搜索方向。一个算法的搜索方向是该优化方法的基本标志，它从根本上决定着一个算法的成败和收敛速率的快慢。因此，分析、确定搜索方向是研究优化方法的最根本的任务之一。各种无约束优化方法也是在确定搜索方向上显示出各自的特点。无约束优化方法可以分为两类。一类是通过计算目标函数的一阶或二阶导数值确定搜索方向的方法，称为间接法，如最速下降法、牛顿法、变尺度法和共轭梯度法。另一类是直接利用目标函数值确定搜索方向的方法，称为直接法，如坐标轮换法、鲍威尔法和单形替换法。本章将分别讨论上述这两类无约束优化方法。41最速下降法4.1.1最速下降法的基本原理由第二章优化设计的数学基础可知，梯度方向是函

4、数增加最快的方向，负梯度方向是函数下降最快的方向，所以最速下降法以负梯度方向为搜索方向，每次迭代都沿着负梯度方向进行一维搜索，直到满足精度要求为止。因此，最速下降法又称为梯度法。由公式（4.2）可知，若某次选代中己取得点，从该点出发，取负梯度方向为搜索方向。则最速下降法的迭代公式为 （4.3）当第次的迭代初始点和搜索方向已经确定的情况下，原目标函数成为关于步长的一维函数。即最优步长可以利用一维搜索的方法求得根据一元函数极值的必要条件和多元复合函数的求导公式，得或写成 由此可知，在最速下降法中相邻两个搜索方向互相正交。也就是说在用最速下降法迭代求优的过程中，走的是一条曲折的路线，该次搜索方向与前

5、一次搜索方向垂直，形成“之”字形的锯齿现象，如图4.1所示。最速下降法刚开始搜索步长比较大，愈靠近极值点其步长愈小，收敛速度愈来愈慢。特别是对于二维二次目标函数的等值线是较扁的椭圆时，这种缺陷更加明显。因此所谓最速下降是指目标函数在迭代点附近出现的局部性质，从迭代过程的全局来看，负梯度方向并非是目标函数的最快搜索方向。 图4.1最速下降法的搜索路径此外，最速下降法的迭代公式也可以写成下面的形式 （4.4）将其与式4.3相比较，可知，此处等于4.3式中步长除以函数在点导数的模，而此时的搜索方向也不再是个单位向量。4.1.2最速下降法的迭代过程） 给定初始点，收敛精度，并令计算次数；） 计算点的梯

6、度及梯度的模，并令） 判断是否满足精度指标；若满足，为最优点，迭代停止，输出最优解和，否则进行下一步计算；） 以为出发点，沿进行一维搜索，求能使函数值下降最多的步长，即） 令，转到步骤2)。最速下降法的程序框图如图4.2所示。开始输入，计算及搜索方向一维搜索求最优步长结束4.2最速下降法的程序框图例题4.1 用最速下降法求目标函数的极小值，设初始点，计算精度。解 （）计算初始点处目标函数的梯度和梯度的模（）由于，不满足精度指标，转下一步计算。（）确定搜索方向（）计算新的迭代点由公式（4.2）可得代入目标函数 沿方向进行一维搜索（或对求导，并令其为零）令，求得最优步长。（）计算新迭代点（）计算新

7、迭代点的梯度及梯度的模因已满足精度要求，停止迭代，得最优解为，可见，对于目标函数的等值线为圆的情况，只要一次迭代就能达到极小值点。这是因为圆周上任意一点的负梯度方向总是指向圆心的，如图4.3所示。图4.3例题4.1目标函数极小值的搜索过程例题4.2用最速下降法求目标函数的极小值，设初始点，计算精度。解（）计算初始点处目标函数的梯度和梯度的模（）由于，不满足精度指标，转下一步计算。（）确定搜索方向（）计算新的迭代点由公式（4.2）可得代入目标函数并沿方向进行一维搜索，求得最优步长。（）计算新迭代点（）计算新迭代点的梯度及梯度的模继续进行第二次迭代。以下各次迭代的结果列于表4.1。到第五次迭代结束

8、时有故迭代终止，最优解为图4.4给出了本例题的搜索过程。表4.1 例题4.2各次迭代结果x1x2022104100.0811.-0.3.3.20.0.0.3.30.-0.000110.0.40.0.0.0.50.-0.90.0.图4.4 例题4.2 目标函数极小值的搜索过程例题4.3 用最速下降法求目标函数的极小值，计算精度。解 （）取初始点，计算初始点处的目标函数、梯度及其模（）求搜索方向（）计算新的迭代点代入目标函数，并沿方向进行一维搜索，求得最优步长于是新迭代点（）计算新迭代点处的目标函数、梯度及其模未达到精度要求，应继续迭代，各轮计算结果如表4.2所示。表4.2 例题4.3各次迭代结果

9、x1x20006010.7703317.3.15.736845.26.5.9.1.37.5.8.0.47.5.8.0.57.5.8.0.67.5.8.0.77.5.8.0.87.996085.997068.0.经过8轮的迭代，满足精度要求，迭代终止。输出最优解为，其函数值为。搜索过程如图4.5所示。图4.5 例题4.3 目标函数极小值的搜索过程通过上面的分析可知最速下降法具有以下特点：（1）理论明确，程序简单，对初始点要求不严格，每次迭代所需的计算量和存储量也较小，适用于计算机计算。（2）对一般函数而言，最速下降法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。（3）最速下降法相

10、邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。（4）最速下降法的收敛速度与目标函数的性质以及初始点的选择密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。若目标函数为二次函数，等值线为椭圆，当初始点选在长轴或短轴上时，一次搜索也可达到极小值点。42牛顿法牛顿法是根据目标函数的等值线在极值点附近为同心椭圆族的特点，在极值点邻域内用一个二次函数来近似代替原目标函数，并将的极小值点作为对目标函数求优的下一个迭代点，经多次迭代，使之逼近原目标函数的极小值点。4.2.1牛顿法的基本原理设目标函数是连续二阶可

11、微的，将函数在点按泰勒级数展开，并保留到二次项，得此式是个二次函数，设为的极小值点，则即 （4.5）这就是多元函数求极值的牛顿法迭代公式。式中取称为牛顿方向，为常数。式中没有步长，或者可以看成步长恒等于1，所以牛顿法是一种定步长的迭代。例题4.4 用牛顿法求目标函数的极小值。解 （）取初始点（）计算梯度、二阶偏导数矩阵及其逆矩阵（）计算新的迭代点经过一次迭代即可求得极小值点，函数极小值。例题4.5 用牛顿法求目标函数的极小值，计算精度。解 （）取初始点，（）计算梯度、二阶偏导数矩阵及其逆矩阵（）计算新的迭代点经过一次迭代即可求得极小值点，函数极小值。例题4.6 用牛顿法求目标函数的极小值，计算

12、精度。解 （）取初始点。（）计算梯度、二阶偏导数矩阵及其逆矩阵（）计算新的迭代点（）计算新迭代点的梯度及梯度的模继续进行第二次迭代。以下各次迭代的结果列于表4.3。到第四次迭代结束时有 故迭代终止，最优解为表4.3 例题4.6各次迭代结果x1x200046.1-2.5-0.2541.062566.2-1.854841.4.16.3-1.347491.0.4.4-1.117221.03897-0.490440.5-1.056871.-0.513320.6-1.052761.-0.513410.目标函数的等值线如图4.6所示。用解析的方法可知，目标函数有三个驻点：，。由函数取得极值的充分条件可知，

13、是极小值点，是鞍点，而则是局部极小值点。因此，初始点的选择对于问题的求解至关重要。若初始点取为，函数收敛到。若初始点取为，函数收敛到鞍点。 图4.6 例题4.6 目标函数的等值线4.2.2 阻尼牛顿法由以上的两个例题可以看出，对于二次函数，用牛顿法迭代一次即可得到最优点；对于非二次函数，若函数的迭代点已进入极小点的邻域，则其收敛速度也是很快的。但是从牛顿法迭代公式的推导可以看出，迭代点是由近似二次函数的极值条件确定的，该点可能是极小值点，也可能是的极大值点。因此在用牛顿法迭代时，可能会出现函数上升的现象，即，使迭代不能收敛于最优点。例如上例中若取初始点，第一次迭代点的函数值就增大。这表明牛顿法

14、不能保证函数值稳定地下降，在严重的情况下甚至不能收敛而导致计算失败。可见，牛顿法对初始点的要求是比较苛刻的，所选取的初始点离极小值点不能太远。而在极小值点位置未知的情况下，上述要求很难达到。为了消除牛顿法的上述这些弊病，需要对其做一些修改。将牛顿法定步长的迭代，改为变步长的迭代，引入步长，在的牛顿方向进行一维搜索，保证每次迭代点的函数值都是下降的。这种方法称为阻尼牛顿法，其迭代公式为 （4.6）式中，为牛顿方向的最优步长。这种方法对初始点的选取不再苛刻，从而提高了牛顿法的可靠度。但采用阻尼牛顿法，每次迭代都要进行一维搜索，使收敛速度大大降低。例如，对于例4.6所示的目标函数，取同样的初始点，采

15、用阻尼牛顿法进行迭代，达到同样的精度，要经过25次的迭代，越靠近极小值点收敛速度越慢，使牛顿法收敛速度快的优势损失殆尽。阻尼牛顿法的迭代过程阻尼牛顿法的计算步骤如下：）给定初始点，收敛精度，并令计算次数；）计算点的梯度和梯度的模；）判断是否满足精度指标；若满足，为最优点，迭代停止，输出最优解和，否则进行下一步计算；5）计算点的牛顿方向6）以为出发点，沿进行一维搜索，求能使函数值下降最多的步长，即令，转到步骤2)。阻尼牛顿法的程序框图如图4.7所示。牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的最大优点是收敛速度快。也就是说，它的迭代次数相对其他方法来说少得多。特别是对于一些性态较好的目标函数，

16、例如二次函数，只需保证求梯度和二阶偏导数矩阵时的精度，不管初始点在何处，均可一步就找出最优点。可是这类方法也有很大的缺点。首先，在每次迭代决定牛顿方向时，都要计算目标函数的一阶导数和二阶导数矩阵及其逆矩阵。这就使计算较为复杂，增加了每次迭代的计算工作量和计算机的存储量。开始输入，计算及其一维搜索求最优步长结束计算点的牛顿方向图表 Error! No text of specified style in document.1图4.6阻尼牛顿法的程序框图4.7阻尼牛顿法的程序框图3共轭梯度法431 共轭方向由4.1节的讨论可知，最速下降法具有计算简单，对初始点的选择要求低，最初几步迭代速度快的优点

17、，但是越接近极值点时效果越差，在搜索过程中呈锯齿状的搜索路径，如图4.1所示。设想在搜索过程中，如果能如图4.9所示，截弯取直在沿搜索到点后，不再沿的负梯度方向搜索，而改沿的方向进行搜索，前已述及，任意形式的目标函数在极值点附近都近似于一个二次函数，希望对二次函数一次搜索到达极小值点X*。即有 （4.8）那么这样的方向应该满足什么条件呢？ 在点的梯度为 （4.9）因为为极小值点，应满足存在极值的必要条件，故有由式（4.8）及式（4.9）可得将等式两边同时左乘。因为与正交，。则有这就是使直指极小点所必须满足的条件。两个向量和称为G的共轭向量，或称和对是共轭方向。可见，沿方向搜索得到后，再沿的共轭

18、方向搜索就可以到达极小值点。下面给出共轭方向的定义：设为阶的正定矩阵，若有两个维向量和满足 （4.10）则两个向量和称为矩阵的共轭向量，和对矩阵是共轭方向。显然，当（单位矩阵）时，式（4.10）变为即，向量和互相正交。由此可见，共轭概念是正交概念的推广，正交是共轭的特例。432 共轭方向的性质性质 若非零向量系是对共轭的，则这n个向量是线性无关的。性质2 在n维空间中互相共轭的非零向量的个数不超过n。性质3 从任意初始点出发，顺次沿n个的共轭方向进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)的极小值点。上述三条性质是采用共轭方向进行迭代的重要理论依据。用共轭方向法进行迭代的关键是如

19、何获得新的共轭方向。提供共轭向量系的方法有许多种，从而形成了各种具体的共轭方向法，如共轭梯度法、鲍维尔法等。433 共轭梯度法的基本原理1、 正定二元二次函数的等值线是椭圆线簇，椭圆线簇的中心就是目标函数的极值点；2、 过同心椭圆线簇中心作任意直线，此直线方向与椭圆交点处的切线方向是对A共轭的。下面进行反证：对二次函数：由于任意形式的目标函数在极值点附近的特性，都近似于一个二次函数，其等值线在极值点附近为近似的同心椭圆族。同心椭圆族有一个特性，就是任意两根平行线与椭圆族切点的连线必通过椭圆的中心。共轭梯度方向的构造：基本思想就是希望利用前面已知的方向信息和梯度信息，434 共轭梯度法的迭代过程

20、共轭梯度法的迭代步骤如下：） 取初始点，计算精度；） 令，；） 从出发沿方向一维搜索到；） 计算梯度，检验是否满足。若满足则迭代停止，点为极小值点。否则进行5）；） 判断是否成立，若，则令，返回2）；否则计算令，返回3）；共轭梯度法的程序框图如图（4.12）所示。例题4.8 用共轭梯度法求目标函数的极小值，计算精度。解 （）取初始点， （）计算初始点处的梯度及其模以及搜索方向（）计算新的迭代点代入目标函数，并沿方向进行一维搜索（或对求导，并令其为零），求得最优步长。于是新迭代点（）计算新迭代点处的梯度及其模（）计算系数，及共轭方向（）计算新的迭代点代入目标函数，并沿方向进行一维搜索，求得最优步

21、长。于是新迭代点（）计算新迭代点处的梯度及其模则目标函数的极小值开始输入，结束一维搜索求最优步长图4.12共轭梯度法的程序框图应用以上各节所介绍的几种无约束最优化的方法，均需计算目标函数的阶或二阶偏导数。在实际机械优化问题中，目标函数有时很复杂，并且也未必都能满足正定、连续可微等条件，其偏导数或难以求得，或根本就不存在。这时如仍用前面介绍的方法就行不通了，只能用直接法来解决问题。直接法不需要求目标函数的一阶或二阶偏导数，仅仅需要计算各迭代点的目标函数值，并通过分析比较，逐步逼近最优点。工程上常用的直接法有坐标轮换法、鲍威尔法和单形替换法。44变尺度法（也称拟牛顿法）经过前面的讨论可以看出，最速

22、下降法收敛速度太慢，牛顿法虽然收敛速度很快，但要求计算二阶导数及其逆矩阵，其计算量和存储量都很大，二者都有致命的弱点。有什么办法可以既不用计算函数的二阶导数及其逆矩阵，又保持较快的收敛速度呢？变尺度法就是这样的一种方法，它是基于牛顿法，并对其进行了重大改进的一种方法。4.4.1变尺度法的基本原理考察例题4.2中讨论过的目标函数，用最速下降法求极小值，满足精度要经过5次迭代。但是若进行变换，令就可以将等值线为椭圆的目标函数变换成等值线为圆的函数，消除了函数的偏心，用最速下降法只需一次迭代即可求得极小值点。这种变换称为尺度变换。采用尺度变换的方法，通过放大或缩小各个坐标，可以把函数的偏心程度降到最

23、低，从而改进了函数的收敛性质。对于一般的二次函数，用梯度法求解时迭代收敛的速度取决于矩阵G的性质，如为正定矩阵。可进行尺度变换在新的坐标系中，函数的二次项变为因为G是正定的，总存在矩阵Q，使得用矩阵右乘等式两边，得用矩阵左乘等式两边，得再用矩阵右乘等式两边，得上式说明：二次函数矩阵的逆矩阵可以通过尺度变换矩阵来求得。对于非二次函数，也可以用类似的思想方法，通过尺度变换，使函数的性态逐步变好。比较梯度法与牛顿法对于梯度法迭代公式 上式也可以看做 对于修正牛顿迭代公式 牛顿法对二次函数很有效，但要计算海赛矩阵的逆矩阵，将两种方法合并发现，构造一个矩阵，只要从单位矩阵I出发，最后趋向海赛矩阵的逆矩阵

24、，就可以实现从梯度法到牛顿法搜索的转变。该构造矩阵是一个不断变化的矩阵，称作变尺度矩阵。变尺度法的迭代式为： （4.7） 按这种方法迭代，不用计算二阶导数矩阵及其逆矩阵，又能沿牛顿方向搜索，因此具有较快的收敛速度。关键是如何构造尺度矩阵。理论证明，取（单位矩阵）。经过对矩阵的不断修正，在迭代中逐步逼近于。为了使变尺度矩阵Ak逼近海赛矩阵的逆矩阵，并具有容易计算的特点，必须对构造附加某些条件。1) 保证迭代公式具有下降性质要求构造矩阵Ak是对称正定的。因为若要求搜索方向为下降方向，要求搜索方向与该点负梯度方向之间的夹角小于90,即，即K应为对称正定。 2) 要求AK具有简单的迭代形式。显然 为最

25、简单的形式，其中AK为校正矩阵。上式称作校正公式， 3) 要求构造矩阵必须满足拟牛顿条件。 拟牛顿条件：对目标函数f（x）在点x(k)作二阶泰勒展开：上式就是海赛矩阵G应满足的关系式，若要构造矩阵，构造的矩阵也应满足这个关系式： 这是按牛顿法推出来的条件，成为DFP条件。构造修正矩阵的方法不同，就演变出不同的变尺度法。如DFP法和BFGS法。DFP变尺度法是由W.C.Davidon提出并经R.Fletcher和M.J.D.Powell修改的构造的方法。式中4.4.2 变尺度法的迭代过程变尺度法的计算步骤如下：)取初始点；计算精度；）令，（单位矩阵）；）计算点的梯度及其模；）判断是否满足精度指标

26、；若满足，为最优点，迭代停止，输出最优解和，否则进行下一步计算；）构造搜索方向进行一维搜索，求最优步长，并求出新点）按变尺度公式计算及；）置。转步骤（）。变尺度法的程序框图如图4.8所示。开始输入，计算及其一维搜索求最优步长结束计算点的搜索方向计算及4.8变尺度法的程序框图例题4.7 用变尺度法求目标函数的极小值，计算精度。解 （）取初始点，尺度矩阵（）计算初始点处的目标函数、梯度及其模（）求搜索方向（）计算新的迭代点代入目标函数，并沿方向进行一维搜索，求得最优步长于是新迭代点（）计算新迭代点处的目标函数、梯度及其模（）构造尺度矩阵计算计算尺度矩阵（）重新建立搜索方向，重新计算新的迭代点代入目

27、标函数，并沿方向进行一维搜索，求得最优步长于是新迭代点计算新迭代点处目标函数的梯度及其模故迭代终止，最优解为 可见，对于二次函数应用DFP法两次迭代后即可达到最优点。比应用牛顿法多迭代一次，但是不用计算目标函数的二阶导数及其逆。这种算法用于高维问题（如20个变量以上），收敛速度快、效果好，成为无约束优化问题最有效的算法之一。在本例中二次迭代的结果与真解相比略有偏差，主要是由于一维搜索的不精确产生的。由于舍入误差和一维搜索的不精确，在大量的计算中可能会使某个尺度矩阵不能保持正定或变为奇异而影响数值的稳定性，使计算失败。Broyden、Fletcher、Goldfarb、和Shanno提出了一种更

28、为稳定的构造尺度矩阵的迭代公式，称为BFGS变尺度法。BFGS公式可以看成是对DFP公式的补充和修正。BFGS法的修正矩阵为BFGS法的计算步骤与DFP法相同。 坐标轮换法坐标轮换法是将多维问题转化为一系列一维问题的求解方法，它将多变量的优化问题轮流转化为单变量的优化问题，因此又称为变量轮换法。这种方法在搜索过程中只需要目标函数的信息，而不需要求解目标函数的导数，因此，比于前面介绍的几种优化方法更加简单明了。451 坐标轮换法的基本原理坐标轮换法轮流沿坐标方向搜索，每次只允许一个变量变化，其余变量保持不变。以二元函数为例，说明坐标轮换法的迭代过程。如图4.13所示，选定的初始点作为第一轮的始点

29、，保持不变而沿方向作一维搜索，确定其最优步长，即可获得第一轮的第一个迭代点。然后以为新起点，改沿方向作一维搜索，确定其最优步长，可得第一轮的第二个迭代点。这个二维问题经过沿和方向的两次一维搜索完成了第一轮迭代。接着的第二轮迭代则是，。按照同样的方式进行第三轮、第四轮、迭代。随着迭代的进行，目标函数值不断下降，最后的迭代点必将逼近该二维目标函数的最优点。迭代的终止准则可以采用点距准则，即在一轮迭代后，终点与始点的距离小于收敛精度，则迭代停止。图4.13坐标轮换法的搜索过程对n维优化问题，先将个变量固定不动，只对第一个变量进行一维搜索得到最优点。然后，再对第二个变量进行一维搜索到点等等。总之，每次

30、都固定个变量不变，只对目标函数的一个变量进行一维搜索，当n个变量依此进行过一轮搜索之后，即完成一轮迭代计算。若未收敛，则又从前一轮的最末点开始，作下一轮迭代计算，如此继续下去，直至收敛到最优点为止。对于第k轮第i维搜索的计算公式为 （4.13）式中，表示第k轮第i维搜索的初始点；表示第k轮第i维搜索的搜索方向，轮流取n个坐标的单位向量，即 （4.14）其中，第i个单位坐标方向为1，其余为0；表示第k轮第i维搜索迭代的步长，可以采用一维搜索的方法确定。若，则迭代停止，得到最优解；否则,进行下一轮搜索直到满足精度要求为止。45 坐标轮换法的迭代过程） 取初始点，计算精度；取搜索方向为n个坐标的单位

31、向量。） 按公式进行迭代计算。其中可通过一维搜索的方法确定。） 判断是否满足若满足，迭代终止，输出最优解；否则,返回步骤）。坐标轮换法的程序框图如图（4.14）所示。开始输入，n结束沿方向一维搜索求最优步长图4.14坐标轮换法的程序框图例题4.9 用坐标轮换法求目标函数的极小值，计算精度。解 （）取初始点，作第一轮迭代计算，沿方向进行一维搜索，即其中，为第一轮的起始点，取代入目标函数可得对进行一维搜索，使目标函数极小，即，可得。这里暂且借用微分学求导解出，令其一阶导数为零，则可得 以为新起点，沿方向进行一维搜索，即代入目标函数，并对进行一维搜索，使目标函数极小，即可得 则 对第一轮按中止准则检

32、验继续进行第二轮迭代计算。以下各轮的计算结果列于表4.4。表4.4例4.9各轮计算结果kx1x2f(X1)x1x2f(X2)000601503554.514.756.27.254.59.68757.255.6258.2.37.81255.6258.7.81255.906258.0.47.5.906258.7.5.8.0.57.5.8.7.5.8.0.67.997075.8.7.997075.8.0.计算6轮共12次一维搜索后有。故近似最优解为搜索过程如图4.15所示。图4.15 例4.9目标函数极小值的搜索过程坐标轮换法具有算法简单，易于程序实现的优点。但是采用坐标轮换法，只能轮流沿坐标方向搜

33、索，尽管它具有步步下降的特点，但路程迂回曲折，要多次变换方向，才有可能求得无约束极值点，尤其在极值点附近，每次搜索的步长更小，因此，收敛很慢。此外，坐标轮换法的收敛效率在很大程度上取决于目标函数的形态。如图4.16(a)所示，若目标函数的等值线为长短轴都平行于坐标轴的椭圆形，则这种搜索方法很有效，两次就可达到极值点。但当目标函数的等值线近似于椭圆，且长短轴倾斜时，如图4.16(b)所示，用这种搜索方法，必须多次迭代才能曲折地达到最优点。当目标函数的等值线出现脊线时，如图4.16(c)所示，这种搜索方法完全无效。因为，每次的搜索方向总是平行于某一坐标轴，不会斜向前进，所以一旦遇到了等值线的脊线，

34、就不能找到更好的点了。 (a)搜索有效 (b)搜索低效 (c)搜索无效图4.16坐标轮换法的搜索效能因此，坐标轮换法称不上是一种很好的搜索方法。但是，在坐标轮换法的基础上可以构造出更好的搜索方法，鲍维尔法就是这样一种方法。 鲍维尔法鲍维尔法是直接利用函数值构造共轭方向进行搜索的方法。因此，也属于共轭方向法，但与共轭梯度法相比，不需要对函数求导数，而是在迭代中逐次构造出用于搜索的共轭方向。461 鲍维尔法的基本原理我们以正定二次函数为例说明鲍维尔法中共轭方向的形成过程。如图4.17所示，和为从不同点出发沿相同方向搜索到的两个点，为和的连线方向。由4.4节的论述可知，和对矩阵是共轭方向。对于二维问

35、题，函数的等值线为一椭圆族，沿此共轭方向进行一维搜索就可以找到极小值点。图4.17通过一维搜索确定共轭方向462 鲍维尔法的迭代过程对于二维无约束优化问题，采用鲍维尔法求解的迭代过程如图4.18所示。4.18二维情况下鲍维尔法的迭代过程）任选一初始点，令，按照坐标轮换法，选择两个单位向量和依次作为搜索方向进行第一轮搜索得到点。）用和的连线方向构成新的搜索方向。从点出发，沿方向一维搜索得到点。令，作为下一轮搜索的初始点。）从出发，依次沿和方向进行一维搜索，得到点和点。）用和的连线方向构成新的搜索方向。和是从两个不同点出发沿相同的方向搜索得到的，因此，与和的连线方向互为共轭方向。从点出发，沿方向一

36、维搜索得到点。因为是从点出发依次沿两个互为共轭的方向和进行两次一维搜索得到的，所以就是该二维二次函数的极小值点。将上述二维优化的问题扩展到n维的情况，得到鲍维尔法的基本迭代过程：从初始点出发依次沿n个线性无关的方向组进行一维搜索得到一个终点。沿初始点和终点的连线方向一维搜索得到下一轮迭代的初始点。并以这个方向作为下一轮迭代方向组中的最后一个方向，同时去掉第一个方向，组成的新方向组进行新一轮迭代。若目标函数是个n维的正定二次函数，则经过这样的n轮迭代以后，就可以收敛到最优点。遗憾的是鲍维尔法有一个缺陷：用这种方法产生的n个新方向，有可能出现线性相关或近似线性相关的情况。因为，新方向，倘若在迭代中

37、出现了的情况，就可以表示为的线性组合。由于在新组成的方向组中恰好换掉了，即，方向组就成为线性相关的一组向量。以后各轮迭代计算将在维数下降了的空间内进行，从而导致算法收敛不到真正的最优点上。这种现象称为鲍维尔法的“退化”。以一个三维问题为例，如图4.19所示，首先由初始点出发，沿，进行第一轮搜索，得到点，连接始点和终点，形成搜索方向。在这一轮中和是不共面的一组向量，可表示为图4.19三维问题的鲍维尔法示意图如果在某种情况下，如图4.20所示，即在方向上没有进展，此时，则与共面，成为线性相关的一组向量。随后迭代得到的各轮方向组中的向量必在由和所决定的平面内，使以后的搜索局限在二维平面内进行。显然，

38、这种降维后的搜索将无法获得三维目标函数的最优点。图4.20三维问题的鲍维尔法降维示意图463 改进的鲍维尔法针对上述退化现象，对鲍维尔法进行了改进，在每轮获得新方向之后，在组成新的方向组时，不一定换掉方向，而是有选择地换掉其中某一个方向，以避免新方向组中的各方向出现线性相关的情形，保证新方向组比前一方向组具有更好的共轭性质。为此，导出是否用方向代替来组成新的搜索方向组的判别条件：设：， 其中最大者 。若 和 同时成立，则用方向换掉方向，否则仍用原来的n个搜索方向。改进的鲍维尔法在计算上虽然稍微复杂一些，但它保证了对于非线性函数计算时收敛的可靠性。理论和实践都证明了，这种方法对于正定二次型函数具

39、有较高的收敛速度，对于机械优化设计中多种多样的目标函数来说是很有效的。464改进的鲍维尔法的迭代过程） 取初始点，计算精度；依次沿n个线性无关的方向进行一维搜索（当时，取）。得到） 计算第k轮迭代中每相邻二点目标函数值的下降量，并找出下降量最大者及其相应的方向 ） 沿共轭方向计算反射点4）检验判别条件令，若同时满足和 则由出发沿方向进行一维搜索，求出该方向的极小点，并以作为轮迭代的初始点，即令；然后进行第轮迭代，其搜索方向去掉，并令，即） 若上述替换条件不满足，则进入第轮迭代时，其n个方向全部用第k轮的搜索方向，而初始点则取和中函数值较小的点。） 判断是否满足收敛准则若满足，迭代终止，输出最优

40、解；否则,返回步骤）。改进的鲍维尔法的程序框图如图4.22所示。例题4.10 用鲍维尔法求目标函数的极小值，计算精度。解 （）取初始点，。第一轮迭代的搜索方向取两个坐标的单位向量和其中，为第一轮的起始点，取，沿方向进行一维搜索得最优步长。由此得最优点以为新起点，沿方向进行一维搜索得最优步长。由此得最优点（2）计算相邻二点函数值的下降量，（3）计算第n+1个方向，及该方向上的反射点（）检验判别条件，故成立。（）因为，故由出发沿方向进行一维搜索得最优步长。由此得最优点（）令，进行第2轮迭代，其搜索方向去掉，并令，。计算结果列于表4.5。表4.5例4.各轮计算结果x1x2x1x2x1x2x1x210

41、05054.57.4726.72527.47256.72537.47255.73637.90716.127586本例题的精确解即为，达到精度要求总共进行了两轮6次一维搜索。搜索过程如图4.21所示。图4.21 例4.10目标函数极小值的搜索过程开始输入X(0),，n结束沿方向一维搜索求最优步长i=n?判别条件是否满足？沿方向一维搜索求最优步长f2f3 ?图4.22鲍维尔法的程序框图 单形替换法单形替换法是一种不需要求目标函数的导数，仅需要计算n维设计空间中的几何图形顶点的目标函数值，并通过分析比较，不断向好点移动逼近最优点的直接算法。471 单形替换法的基本原理所谓单纯形是指在n维空间中具有n+1个顶点的多面体。如图4.23所示，在一维空间中由两个点构成的线段；在二维空间中由不在一条直线上的三个点构成的三角形；在三维空间中由不在一个平面上的四个点构成的四面体等。图4.23 单纯型示例无约束优化问题的单形替换法是根据问题的维数n，选取由n