机械优化设计 第4章 无约束优化方法

1、第四章 无约束优化方法,4-1 最速下降法（梯度法） 4-2* 牛顿类方法 4-3* 变尺度法 4-4* 共轭方向法 4-5* 鲍威尔方法 4-6 其它方法（如坐标轮换法、单纯形法）,第1章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。 为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。,（4）对于

2、多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。,目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。,（1）间接法要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。 （2）直接法不使用导数信息，如坐标轮换法、鲍威尔法、单纯形法等。,无约束优化问题是：,求n维设计变量,使目标函数,搜索方向的构成问题乃是无约束优化方法的关键。,用直接法寻找极小点时，不必求函数的导数，只要计算目

3、标函数值。这类方法较适用于解决变量个数较少的（n 20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。,4-1 梯度法,基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。,搜索方向s取该点的负梯度方向 (最速下降方向) ，使函数值在该点附近的范围内下降最快 。,为了使目标函数值沿搜索方向 能够获得最大的下降值，其步长因子 应取一维搜索的最佳步长。即有,根据一元函数极值的必要条件和多元复合函数求导公式，得,在最速下降法中，

4、相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。,图4-2 最速下降法的搜索路径,方法特点 （1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。 （2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。,sk,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,例41 求目标

5、函数 的极小点。 解 取初始点 则初始点处函数值及梯度分别为,算出一维搜索最佳步长,第一次迭代设计点位置和函数值,继续作下去，经10次迭代后，得到最优解,这个问题的目标函数的等值线为一簇椭圆,迭代点从 走的是一段锯齿形路线，见图4-3。,将上例中目标函数 引入变换,其等值线由椭圆变成一簇同心圆。,仍从 即 出发进行最速下降法寻优。此时：,沿负梯度方向进行一维搜索：,则函数f(X)变为：,y1=x1, y2=5x2,由,从而算得一步计算后设计点的位置及其目标函数：,经变换后，只需一次迭代，就可找到最优解。,这是因为经过尺度变换：,等值线由椭圆变成圆。,梯度法的特点,（1）理论明确，程序简单，对初

6、始点要求不严格。 （2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。 （3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。 （4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。,前面介绍的许多优化方法，除鲍威尔（Powell）法外，都需要计算目标函数的导数，而在实际工程的最优化问题中，目标函数的导数往往很难求出或者根本无法求出。下面所介绍的方法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念也比较清

7、晰，属于直接法的无约束最优化方法。这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。,4-6 其它方法（如坐标轮换法、单纯形法）,坐标轮换法,坐标轮换法的基本思想：是将一个n维优化问题转化为依次沿n个坐标方向反复进行一维搜索问题。这种方法的实质是把n维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程。每次一维搜索时，只允许n个变量的一次改动，其余(n-1)个变量固定不变。故坐标轮换法也常称单变量法或变量交错法。,坐标轮换法,此法的效能在很大程度上取决于目标函数的性质。,（1）计算量少，程序简单，不需要求函数导数的直接探索目标函数最优解的方法； （2

8、）探索路线较长，问题的维数愈多求解的效率愈低。当维数n10时，则不应采用此法。仅适用于n较少（n 0，模矢加速搜索的加速步长因子为a1（通常取a=2），迭代终止准则为 ( 为预先确定的正数）。,（1）,（2）,否则转（6）,否则，令,（6）,（5）,单纯形方法,一、基本思想 单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。,定义：单纯形 n维空间中的恰好有n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。 根据定义，可知，一维空间中的单纯形是线段，

9、二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。 在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这4个操作来实现。下面以二维问题为例来对4种操作进行说明（参见下图）。,（1）反射设除了最劣点X1以外的基余顶点的中心为X4，作X1关于点X4的对称点X5，称X5为X1的反射点。求反射点的过程称之为反射。,（2）扩张在得到反射点X5之后，如果X5优于原单纯形的最劣点（即有 ），表明反射方向（X5X1）是有利方向，反射成功。若进一步有 ，可沿反射方向前进适当的距离到点X6。X6称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点X6优于反射点X5，

10、则扩张成功，以X6取代X1，得新单纯形X6,X2,X3；否则，扩张失败，舍弃扩张点，以反射X5点取代X1，得新单纯形X5,X2,X3。,设当前的单纯形的顶点为X1，X2，X3，且有,如果出现 。表示反射完全失败，应退回到介于X4与X1之间的某个点X8。,（3）收缩在得到反射点X5之后，如果有,表示反射部分成功，方向（X5X1）虽然是有利方向，但X5前进过远，应收缩到介于X4与X5之间的某个点X7。,上述两种从反射点向X1方向后退的过程都称之为收缩。如果收缩点优于原来的最劣点X1，称收缩成功，并以收缩点取代原最劣点，构成新单纯形X7,X2,X3或X8,X2,X3；否则，称之为收缩失败，舍弃收缩点

11、。,（4）缩边若收缩失败，则应压缩当前单纯形的边长：令最优点X3不动，而其余顶点向X3方向压缩，使边长缩短（通常缩短一半），以产生新单纯形。如下图所示，点X1压缩到点X9，点X2压缩到点X10，得新单纯形X9,X10,X3，这一过程称之为缩边。,二、单纯形替换算法 设初始点为X0，初始边长h，ei为坐标轴方向的单位向量 ，预定正数,（2）比较各项点Xi的函数值，挑出其中的最优点，记为XL；最劣点，记XH；次差点，记为Xw； （3）求反射中心,其中，a0，通常取a=1；,输出XL，为原问题近似极小点；否则，转（2）。,（5）如果满足,表1 无约束优化方法搜索方向之间的相互联系 间接法,（海赛矩阵的逆阵）,无约束优化方法 间接法总结,1、梯度法 方向 负梯度 用到一阶导数 适合于精度不高或用于复杂函数寻找一个好的初始点 2、牛顿法 用到一阶导数和海色矩阵，具有二次收敛性 要求海色矩阵奇异，且维数不宜太高 3、共轭梯度法 用到一阶导数，具有二次收敛性 4、变尺度法 收敛快，效果好，被认为是目前最有效的无约束优化方法。适用于维数较高，具有一阶偏导数的目标函数,1、坐标轮换法 计算效率较低 适合维数较低，目标函数无导数或导数较难求得 2、步长加速法 同坐标轮换法，对目标函数的性态的适应性更好 3、