机械优化设计ppt课件第四章 无约束优化的直接搜索法

1、机械优化设计机械优化设计 太原科技大学 张学良 第四章 无约束优化的直接搜索法 各种无约束优化方法的区别就在于确定其搜索方向各种无约束优化方法的区别就在于确定其搜索方向S(k)的方法不同，所以搜索的方法不同，所以搜索 方向的构成问题是无约束优化方法的关键。根据构造搜索方向所使用的信息性质的方向的构成问题是无约束优化方法的关键。根据构造搜索方向所使用的信息性质的 不同，无约束优化方法可以分为两类：不同，无约束优化方法可以分为两类： X (k+1)=X (k) + (k) S(k) (k =0 , 1 , 2 , ) 一类是只利用目标函数值信息的无约束优化方法，如坐标轮换法、鲍威尔法，一类是只利用

2、目标函数值信息的无约束优化方法，如坐标轮换法、鲍威尔法， 称为直接搜索法；另一类是利用目标函数的一阶或二阶导数信息的无约束优化方法，称为直接搜索法；另一类是利用目标函数的一阶或二阶导数信息的无约束优化方法， 如梯度法、牛顿法、共轭梯度法、变尺度法，称为间接搜索法。如梯度法、牛顿法、共轭梯度法、变尺度法，称为间接搜索法。 基本思想基本思想 4.1 坐标轮换法坐标轮换法（变量轮换法、交替法、降维法）（变量轮换法、交替法、降维法） 将将n维无约束优化问题转化为维无约束优化问题转化为n个沿坐标轴方向个沿坐标轴方向ei (i=1, 2, , n)的一维优化的一维优化 问题来求解，并记完成问题来求解，并记

3、完成n次一维搜索为一轮。若一轮搜索后未得到满足精度要求次一维搜索为一轮。若一轮搜索后未得到满足精度要求 的最优点，则继续下一轮迭代搜索。如此反复，直至得到满足精度要求的最优点的最优点，则继续下一轮迭代搜索。如此反复，直至得到满足精度要求的最优点 为止。在每一轮搜索中，每次迭代仅对为止。在每一轮搜索中，每次迭代仅对n元函数的一个变量沿其坐标轴方向进行元函数的一个变量沿其坐标轴方向进行 一维搜索，其余一维搜索，其余n-1个变量均保持不变，再依次轮换进行一维搜索的坐标轴，直个变量均保持不变，再依次轮换进行一维搜索的坐标轴，直 至完成沿至完成沿n个沿坐标轴方向的个沿坐标轴方向的n次一维搜索。次一维搜索

4、。 x1 x2 X0(1) X1(1) X2(1) 取初始点取初始点X(0)=X0(1)， x1坐标轴方向的单位向量坐标轴方向的单位向量S1(1)=e1=1 0T， x2坐标轴方向的坐标轴方向的 单位向量单位向量S2(1)= e2=0 1T。 X1(1) =X0(1)+1(1)S1(1)， X2(1) =X1(1)+2(1)S2(1) 判断是否满足迭代收敛准则：判断是否满足迭代收敛准则： | X2(1) X0(1) | ？ X1(1) =X0(1)+1(1)e1(1) = x1(0) x2(0)T + 1(1)1 0T X2(1) =X1(1)+2(1)e2(1) = x1(1) x2(1)T

5、 + 2(1)0 1T 第一轮迭代搜索：第一轮迭代搜索： 若满足，则输出最优解，否则，继续下一轮迭代搜索。若满足，则输出最优解，否则，继续下一轮迭代搜索。 Xi(k) =Xi-1(k)+i(k)ei(k) ( k迭代轮次，迭代轮次，i k轮迭代的第轮迭代的第i次一维搜索次一维搜索 i(k) 一维搜索求得的最优步长）一维搜索求得的最优步长） | Xn(k) X0(k) | ？ 计算步骤与算法框图计算步骤与算法框图 1）任选初始点）任选初始点X(0)=X0(1) = x1(0) x2(0) xn(0) T ，给定迭代收敛精度，给定迭代收敛精度 ，i = 1，k = 1。 2）置）置n个坐标轴方向向

6、量为单位向量，即个坐标轴方向向量为单位向量，即e1=1 0 0 T， e2=0 1 0 0 T ， ， en=0 0 1T。 3）按如下迭代计算公式进行迭代计算）按如下迭代计算公式进行迭代计算 Xi(k) =Xi-1(k)+i(k)ei(k) ( k迭代轮次，迭代轮次，i k轮迭代的第轮迭代的第i次一维搜索次一维搜索 i =1，2， ，n） 4）判断是否满足迭代收敛准则）判断是否满足迭代收敛准则 | Xn(k) X0(k) | ？ 若满足，则输出最优解若满足，则输出最优解: X * = Xn(k) ，f * = f (X * ) 否则，令否则，令X0(k+1) = Xn(k) ，k k+1，返

7、回，返回3）。）。 举例：举例： 用坐标轮换法求目标函数用坐标轮换法求目标函数 f (X) = x12 + x22 x1x2 4x1 10 x2+ 60 的无约束最优解。初始点的无约束最优解。初始点X(0)= 0 0 T ，迭代收敛精度，迭代收敛精度 =0.1。 坐标轮换法搜索过程和收敛情况讨论坐标轮换法搜索过程和收敛情况讨论 X0(1) X * X1(1) X0(1) X * X1(1) x1 x2 X0(1) X1(1) X2(1) X * 等值线出现脊线的情况（等值线出现脊线的情况（4M14图）图） 4.2 鲍威尔（鲍威尔（Powell）法）法 基本思想基本思想 它是直接利用函数值来构造

8、共轭搜索方向的一种共轭搜索方向法，又称鲍威它是直接利用函数值来构造共轭搜索方向的一种共轭搜索方向法，又称鲍威 尔共轭方向法或方向加速法。由于对于尔共轭方向法或方向加速法。由于对于n维正定二次函数，共轭搜索方向具有维正定二次函数，共轭搜索方向具有n次次 收敛的特性，所以鲍威尔法是直接搜索法中十分有效的一种算法，一般认为对于收敛的特性，所以鲍威尔法是直接搜索法中十分有效的一种算法，一般认为对于 维数维数n 20的目标函数它是成功的。鲍威尔法是在研究具有正定对称矩阵的目标函数它是成功的。鲍威尔法是在研究具有正定对称矩阵H的二的二 次函数的极小化问题时形成的，其基本思想是在不用函数导数信息的前提下，在

9、次函数的极小化问题时形成的，其基本思想是在不用函数导数信息的前提下，在 迭代过程中逐次构造关于迭代过程中逐次构造关于H的共轭方向。的共轭方向。 共轭方向的生成共轭方向的生成 设是设是X(k) 和和 X(k+1)为从不同点出发，沿同一方向进行为从不同点出发，沿同一方向进行一维搜索一维搜索而得到的两个而得到的两个 极小点。极小点。 S(j) S(j) S(k) X(k) X(k+1) f (X(k) ) f (X(k+1) ) S(j) T f (X(k) ) = 0 S(j) T f (X(k+1) ) = 0 具有正定对称矩阵具有正定对称矩阵H的二次函数的二次函数 f (X) = 0.5 XT

10、 H X + BT X + C 在在 X(k) 和和 X(k+1)两点处的梯度可以表示为两点处的梯度可以表示为 f (X(k) ) = H X(k) + B （1） f (X(k+1) ) = H X(k+1） ） + B （ （2） （2） （1）得）得 f (X(k+1) ) f (X(k) ) = H ( X(k+1) X(k) )（3） （3）式两边同时左乘）式两边同时左乘S(j) T得得 S(j) Tf (X(k+1) )f (X(k) )= S(j) TH (X(k+1)X(k) )=0 即即 S(j) T H ( X(k+1) X(k) ) = 0 若取若取 S(k) = X(k

11、+1) X(k) 那么，那么， S(k) 和和 S(j) 关于关于H 共轭，即共轭，即 S(j) T H S(k) = 0 这说明：这说明： 沿沿S(j)方向分别对函数做两次一维搜索，得到两个极小点方向分别对函数做两次一维搜索，得到两个极小点X(k) 和和 X(k+1)，该，该 两点的连线方向两点的连线方向S(k)与与S(j)是关于是关于H 共轭的方向。共轭的方向。 X(k) x1 x2 X * S(j)X(k+1) S(k) 上述生成共轭方向的方法完全可以推广到上述生成共轭方向的方法完全可以推广到n维优化问题中，即在维优化问题中，即在n维空间中，维空间中， 按上述方法可以生成按上述方法可以生

12、成n个相互共轭的搜索方向。个相互共轭的搜索方向。 鲍威尔法的基本原理和迭代过程鲍威尔法的基本原理和迭代过程 1）采用坐标轮换法顺次沿）采用坐标轮换法顺次沿n个坐标轴方向进行一维搜索，然后以初始点个坐标轴方向进行一维搜索，然后以初始点X(0) 和终点和终点Xn(1)构成一个构成一个新的方向新的方向 S(1) ，并以次方向搜索方向再作一维搜索得到极小，并以次方向搜索方向再作一维搜索得到极小 点点Xn+1(1)。 2）取始点）取始点X0(2) = Xn+1(1)，并，并去掉去掉原搜索方向组中的原搜索方向组中的第一个方向第一个方向S1(1)=e1，而，而 将第一轮构成的将第一轮构成的新搜索方向新搜索方

13、向 S(1) 作为作为最末一个方向最末一个方向，以此组成第二轮迭代的，以此组成第二轮迭代的n个个 方向。方向。 依此进行下去，直到获得满足迭代收敛精度要求的近似极小点为止。依此进行下去，直到获得满足迭代收敛精度要求的近似极小点为止。 根据这一原理构造的迭代算法称为根据这一原理构造的迭代算法称为鲍威尔基本算法。鲍威尔基本算法。 X1 (1) X * S1(1) X0 (1) S2(1) S(1) x1 x2 X2 (1) X3 (1) X1 (2) X2 (2) S(2) 鲍威尔基本算法的缺点鲍威尔基本算法的缺点 鲍威尔基本算法仅具有理论意义，不要说对于一般的函数，就是对于二次函鲍威尔基本算法仅

14、具有理论意义，不要说对于一般的函数，就是对于二次函 数，它也可能失效。因为在迭代过程中的数，它也可能失效。因为在迭代过程中的n个搜索方向有时会变成线性相关，而不个搜索方向有时会变成线性相关，而不 能形成共轭方向，从而张不成能形成共轭方向，从而张不成n维空间，导致随后的迭代搜索在降维（维空间，导致随后的迭代搜索在降维（“退化退化”） 的空间中进行，可能求不到极小点，故需进行改进。的空间中进行，可能求不到极小点，故需进行改进。 那么，为什么会产生这种情况呢？又该如何去改进呢？那么，为什么会产生这种情况呢？又该如何去改进呢？ 鲍威尔条件及鲍威尔修正算法鲍威尔条件及鲍威尔修正算法 鲍威尔基本算法中，每

15、一轮迭代都是用连接始点和终点所产生的新搜索方向鲍威尔基本算法中，每一轮迭代都是用连接始点和终点所产生的新搜索方向 去机械地替换原方向组中的第一个搜索方向，而不做任何的去机械地替换原方向组中的第一个搜索方向，而不做任何的“好坏好坏”判断，这正判断，这正 是产生向量线性相关而发生是产生向量线性相关而发生“退化退化”的根本原因所在。为了避免这种的根本原因所在。为了避免这种“退化退化”现现 象的发生，鲍威尔对这一基本算法进行了修正。即在每一轮产生新的搜索方向象的发生，鲍威尔对这一基本算法进行了修正。即在每一轮产生新的搜索方向S(k) 后，首先判断原搜索方向组是否可以直接用作下一轮迭代的搜索方向组，若可

16、以，后，首先判断原搜索方向组是否可以直接用作下一轮迭代的搜索方向组，若可以， 则仍用之，否则，还要进一步判断原搜索方向组中哪个方向上函数值下降量最大则仍用之，否则，还要进一步判断原搜索方向组中哪个方向上函数值下降量最大 或贡献最大，然后再用或贡献最大，然后再用 新搜索方向替换这个贡献最大的搜索方向，以保证逐次生成共轭方向，即每一轮新搜索方向替换这个贡献最大的搜索方向，以保证逐次生成共轭方向，即每一轮 迭代的搜索方向组线性无关。迭代的搜索方向组线性无关。 对第对第 k 轮迭代，记轮迭代，记 f 1 = f (X0(k) ) f 2 = f (Xn(k) ) f 3 = f (2Xn(k) -X0

17、(k) ) 及及 m(k) = max f (Xi-1(k) ) - f (Xi (k) ) , i=1,2, n ， 并记并记 S m (k) 为与为与 m (k) 相对应的搜索方向，相对应的搜索方向， S(k) = Xn(k) -X0(k) 鲍威尔条件：鲍威尔条件： 若若 f 3 f 1 , 且且 ( f1 - 2f2 + f3) (f1 - f2 - m(k)2 0.5 m(k) (f1 - f3 )2 同时成立，则用同时成立，则用S(k)替代替代Sm(k) ；否则，仍用原搜索方向组。这就是；否则，仍用原搜索方向组。这就是鲍威尔修正算法鲍威尔修正算法， 通常所说的通常所说的鲍威尔算法鲍威

18、尔算法就是指这一修正算法。就是指这一修正算法。 鲍威尔算法的计算步骤及算法框图鲍威尔算法的计算步骤及算法框图 1）任选初始点）任选初始点X(0)=X0(1) ，给定迭代收敛精度，给定迭代收敛精度 1 , 2 。取初始基本方向组为。取初始基本方向组为单位单位 坐标向量系，即坐标向量系，即Si(1)=ei ( i = 1, 2, , n ), 并置迭代轮次并置迭代轮次k=1。 2）从）从X0(k)出发，依次沿出发，依次沿Si(k) ( i = 1, 2, , n ) 作一维搜索，得作一维搜索，得n个极小点个极小点Xi(k) ( i = 1, 2, , n ),构造新的搜索方向构造新的搜索方向 S(

19、k) = Xn(k) -X0(k) ，并沿此方向进行一维搜索得极小，并沿此方向进行一维搜索得极小 点点Xn+1(k) 。 3）判断迭代终止条件）判断迭代终止条件 | Xn+1(k) X0(k) | 1 ？ 或或 | f (Xn+1(k) ) f (X0(k) ) | 2 | f (Xn+1(k) ) | ？ 若满足，则终止迭代并输出最优解：若满足，则终止迭代并输出最优解： X * = Xn+1(k) 和和 f * = f (X * ) 否则，则继续下面的迭代计算。否则，则继续下面的迭代计算。 4）计算）计算 f (Xi (k) ) ( i = 1, 2, , n ) ，并求，并求 m(k) =

20、 max f (Xi-1(k) ) - f (Xi (k) ) , i=1,2, n = fm-1 - fm 及与之对应的两个点及与之对应的两个点Xm-1(k)和和Xm(k) (1m n),则第则第k轮迭代中贡献最大的方向为轮迭代中贡献最大的方向为 Sm(k) = Xm(k) Xm-1(k) 5）确定映射点）确定映射点 X(k) = 2Xn(k) X0(k) ，并计算，并计算 f (X (k) ) ，记记f1 = f(X0(k), f2 =f(Xn(k) 及及 f3=f(X(k) 检验鲍威尔条件，若满足，则转下一步，否则转第检验鲍威尔条件，若满足，则转下一步，否则转第7）步。）步。 6）置第）

21、置第k+1轮迭代的出发点和搜索方向组轮迭代的出发点和搜索方向组 X0(k+1) = Xn+1(k) Si(k+1) ( i = 1, 2, , n ) 即即 S1(k), , Sm-1(k), S(k), Sm+1(k), , Sn(k) 并置并置 k k+1 ，返回第，返回第2）步。）步。 7）置第）置第k+1轮迭代的出发点和搜索方向组轮迭代的出发点和搜索方向组 若若 f2 f3 ，X0(k+1) = Xn(k) ；否则，；否则，X0(k+1) = X(k) 。 Si(k+1) = Si(k) ( i = 1, 2, , n ) 并置并置 k k+1 ，返回第，返回第2）步。）步。 举例：举

22、例： 用鲍威尔法求目标函数用鲍威尔法求目标函数 f (X) = 10(x1 +x2 5) 2 +( x1 x2 ) 2 的无约束最优解。初始点的无约束最优解。初始点X(0)= 0 0 T ， 迭代收敛精度迭代收敛精度 =0.001。 4.3 单形替换法单形替换法 基本思想基本思想 通过计算出若干点处的函数值，对其大小进行比较，可以看出函数值变化的通过计算出若干点处的函数值，对其大小进行比较，可以看出函数值变化的 大致趋势，从而可以寻求使函数值下降的搜索方向。在大致趋势，从而可以寻求使函数值下降的搜索方向。在n维空间中，由维空间中，由n+1个不个不 同点顺序相连，就可以构成一个具有同点顺序相连，

23、就可以构成一个具有n+1个顶点的多面体个顶点的多面体称之为单纯形。计称之为单纯形。计 算函数在这算函数在这n+1个顶点的函数值，并进行比较，据此来确定有利的搜索方向和步个顶点的函数值，并进行比较，据此来确定有利的搜索方向和步 长，找到一个比较好的点来取代单纯形中较差的那个顶点，从而组成了一个新的长，找到一个比较好的点来取代单纯形中较差的那个顶点，从而组成了一个新的 单纯形，并用之取代原来的单纯形。如此下去，新单纯形不断地向目标函数的极单纯形，并用之取代原来的单纯形。如此下去，新单纯形不断地向目标函数的极 小点靠小点靠 近，直到搜索到极小点为止。近，直到搜索到极小点为止。 计算步骤计算步骤 1）

24、构造初始单纯形）构造初始单纯形 选初始点选初始点X0 ，和步长，和步长h。从。从X0出发沿各坐标轴方向分别走步长出发沿各坐标轴方向分别走步长h，得到，得到n个顶点个顶点 Xi (i=1, 2, , n)，与，与X0构成初始单纯形。构成初始单纯形。 X0 x2 x1 X1 X2 2）计算各顶点的函数值）计算各顶点的函数值 fi = f (Xi) (i=0, 1, 2, , n) 3）比较函数值大小，确定最好点）比较函数值大小，确定最好点XL 、最差点、最差点 XH 和次差点和次差点 XG ，即，即: fL = f (XL) =min fi : i = 0, 1, 2, , n fH = f (X

25、H) =max fi : i = 0, 1, 2, , n fG = f (XG) =max fi : i = 0, 1, 2, , n; i H 4）检验是否满足迭代收敛条件）检验是否满足迭代收敛条件 |( fH fL) / fL | ? 若满足，则结束迭代计算，并输出若满足，则结束迭代计算，并输出 X * = XL 和和 f * = f L 否则，转下一步。否则，转下一步。 5）计算除）计算除XH点外的各点的点外的各点的“重心重心” Xn+1 ，即，即 Xn+1 = (Xi XH) / n 计算反射点：计算反射点： Xn+2 = 2Xn+1 XH 和和 fn+2 = f (Xn+2 ) 当当 f L fn+2 fG 时，以时，以Xn+2 代替代替XH ， fn+2 代代 替替 fH ，构造新的单纯形，然后返回到，构造新的单纯形，然后返回到 3）。）。 X0 x2 x1 X1 X2 XH XL XG Xn+1 Xn+2 6）扩张：当）扩张：当 fn+2 f L 时，取时，取扩张点扩张点Xn+3，即，即 Xn+3 = Xn+1 + (Xn+2 Xn+1) ( =1.22.0