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)的一维优化问题来求解，的一维优化问题来求解，并记完成并记完成n次一维搜索为一轮。若一轮搜索后次一维搜索为一轮。若一轮
3、搜索后未得到满足精度要求的最优点，则继续下一未得到满足精度要求的最优点，则继续下一轮迭代搜索。如此反复，直至得到满足精度轮迭代搜索。如此反复，直至得到满足精度要求的最优点为止。在每一轮搜索中，每次要求的最优点为止。在每一轮搜索中，每次迭代仅对迭代仅对n元函数的一个变量沿其坐标轴方向元函数的一个变量沿其坐标轴方向进行一维搜索，其余进行一维搜索，其余n-1个变量均保持不变，个变量均保持不变，再依次轮换进行一维搜索的坐标轴，直至完再依次轮换进行一维搜索的坐标轴，直至完成沿成沿n个沿坐标轴方向的个沿坐标轴方向的n次一维搜索。次一维搜索。x1x2X0(1)X1(1)X2(1)取初始点取初始点X(0)=X
4、0(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 +2(1)0 1T第一轮迭代搜索：第一轮迭代搜索：若满足，则输出最优解，否则，继续下一若满足，则输出最优解，否则，继续下一轮迭
5、代搜索。轮迭代搜索。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个坐标轴方向向量为单位向量，即个坐标轴方向向量为单位向量，即e1=1 0 0 T，e2=0 1 0 0 T，en=0 0 1T。3）按如下迭代计算公式进行迭代计算）按如下迭代计算公式进行迭代计算
6、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，返回，返回3）。）。举例：举例：用坐标轮换法求目标函数用坐标轮换法求目标函数 f(X)=x12+x22 x1x2 4x1 10 x2+60 的无约束最优解。初始点的无约束最优解。初始点X(0)=0 0 T，迭代迭代收敛精度收敛精度=0.1。坐标轮换法搜
7、索过程和收敛情况讨论坐标轮换法搜索过程和收敛情况讨论 X0(1)X*X1(1)X0(1)X*X1(1)x1x2X0(1)X1(1)X2(1)X*等值线出现脊线的情况（等值线出现脊线的情况（4M14图）图）4.2 鲍威尔（鲍威尔（Powell）法）法 基本思想基本思想 它是直接利用函数值来构造共轭搜索方它是直接利用函数值来构造共轭搜索方向的一种共轭搜索方向法，又称鲍威尔共轭向的一种共轭搜索方向法，又称鲍威尔共轭方向法或方向加速法。由于对于方向法或方向加速法。由于对于n维正定二次维正定二次函数，共轭搜索方向具有函数，共轭搜索方向具有n次收敛的特性，所次收敛的特性，所以鲍威尔法是直接搜索法中十分有效
8、的一种以鲍威尔法是直接搜索法中十分有效的一种算法，一般认为对于维数算法，一般认为对于维数n 20的目标函数它的目标函数它是成功的。鲍威尔法是在研究具有正定对称是成功的。鲍威尔法是在研究具有正定对称矩阵矩阵H的二次函数的极小化问题时形成的，其的二次函数的极小化问题时形成的，其基本思想是在不用函数导数信息的前提下，基本思想是在不用函数导数信息的前提下，在迭代过程中逐次构造关于在迭代过程中逐次构造关于H的共轭方向。的共轭方向。共轭方向的生成共轭方向的生成 设是设是X(k)和和 X(k+1)为从不同点出发，沿同为从不同点出发，沿同一方向进行一方向进行一维搜索一维搜索而得到的两个极小点。而得到的两个极小
9、点。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 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)
10、X(k)=0即即 S(j)T H(X(k+1)X(k)=0若取若取 S(k)=X(k+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)x1x2X*S(j)X(k+1)S(k)上述生成共轭方向的方法完全可以推广上述生成共轭方向的方法完全可以推广到到n维优化问题中，即在维优化问题中，即在n维空间中，
11、按上述维空间中，按上述方法可以生成方法可以生成n个相互共轭的搜索方向。个相互共轭的搜索方向。鲍威尔法的基本原理和迭代过程鲍威尔法的基本原理和迭代过程 1）采用坐标轮换法顺次沿）采用坐标轮换法顺次沿n个坐标轴方个坐标轴方向进行一维搜索，然后以初始点向进行一维搜索，然后以初始点X(0)和终点和终点Xn(1)构成一个构成一个新的方向新的方向 S(1)，并以次方向搜索，并以次方向搜索方向再作一维搜索得到极小点方向再作一维搜索得到极小点Xn+1(1)。2）取始点）取始点X0(2)=Xn+1(1)，并，并去掉去掉原搜索原搜索方向组中的方向组中的第一个方向第一个方向S1(1)=e1，而将第一轮，而将第一轮构
12、成的构成的新搜索方向新搜索方向 S(1)作为作为最末一个方向最末一个方向，以，以此组成第二轮迭代的此组成第二轮迭代的n个方向。个方向。依此进行下去，直到获得满足迭代收敛精度依此进行下去，直到获得满足迭代收敛精度要求的近似极小点为止。要求的近似极小点为止。根据这一原理构造的迭代算法称为根据这一原理构造的迭代算法称为鲍威鲍威尔基本算法。尔基本算法。X1(1)X*S1(1)X0(1)S2(1)S(1)x1x2X2(1)X3(1)X1(2)X2(2)S(2)鲍威尔基本算法的缺点鲍威尔基本算法的缺点 鲍威尔基本算法仅具有理论意义，不要鲍威尔基本算法仅具有理论意义，不要说对于一般的函数，就是对于二次函数，
13、它也说对于一般的函数，就是对于二次函数，它也可能失效。因为在迭代过程中的可能失效。因为在迭代过程中的n个搜索方向个搜索方向有时会变成线性相关，而不能形成共轭方向，有时会变成线性相关，而不能形成共轭方向，从而张不成从而张不成n维空间，导致随后的迭代搜索在维空间，导致随后的迭代搜索在降维（降维（“退化退化”）的空间中进行，可能求不到）的空间中进行，可能求不到极小点，故需进行改进。极小点，故需进行改进。那么，为什么会产生这种情况呢？又该那么，为什么会产生这种情况呢？又该如何去改进呢？如何去改进呢？鲍威尔条件及鲍威尔修正算法鲍威尔条件及鲍威尔修正算法 鲍威尔基本算法中，每一轮迭代都是用鲍威尔基本算法中
14、，每一轮迭代都是用连接始点和终点所产生的新搜索方向去机械地连接始点和终点所产生的新搜索方向去机械地替换原方向组中的第一个搜索方向，而不做任替换原方向组中的第一个搜索方向，而不做任何的何的“好坏好坏”判断，这正是产生向量线性相关判断，这正是产生向量线性相关而发生而发生“退化退化”的根本原因所在。为了避免这的根本原因所在。为了避免这种种“退化退化”现象的发生，鲍威尔对这一基本算现象的发生，鲍威尔对这一基本算法进行了修正。即在每一轮产生新的搜索方向法进行了修正。即在每一轮产生新的搜索方向S(k)后，首先判断原搜索方向组是否可以直接后，首先判断原搜索方向组是否可以直接用作下一轮迭代的搜索方向组，若可以
15、，则仍用作下一轮迭代的搜索方向组，若可以，则仍用之，否则，还要进一步判断原搜索方向组中用之，否则，还要进一步判断原搜索方向组中哪个方向上函数值下降量最大或贡献最大，然哪个方向上函数值下降量最大或贡献最大，然后再用后再用新搜索方向替换这个贡献最大的搜索方向，以新搜索方向替换这个贡献最大的搜索方向，以保证逐次生成共轭方向，即每一轮迭代的搜索保证逐次生成共轭方向，即每一轮迭代的搜索方向组线性无关。方向组线性无关。对第对第 k 轮迭代，记轮迭代，记f 1=f(X0(k)f 2=f(Xn(k)f 3=f(2Xn(k)-X0(k)及及 m(k)=max f(Xi-1(k)-f(Xi(k),i=1,2,n，
16、并记并记 Sm(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)；否则，仍用原搜；否则，仍用原搜索方向组。这就是索方向组。这就是鲍威尔修正算法鲍威尔修正算法，通常所说，通常所说的的鲍威尔算法鲍威尔算法就是指这一修正算法。就是指这一修正算法。鲍威尔算法的计算步骤及算法框图鲍威尔算法的计算步骤及算法框图 1）任选初始点）任选初始点X(0)=X0(1)，给定迭代收敛精度，给定迭代
17、收敛精度 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(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)|？若满足，
18、则终止迭代并输出最优解：若满足，则终止迭代并输出最优解：X*=Xn+1(k)和和 f*=f(X*)否则，则继续下面的迭代计算。否则，则继续下面的迭代计算。4）计算）计算 f(Xi(k)(i=1,2,n)，并求，并求 m(k)=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
19、(Xn(k)及及 f3=f(X(k)检验鲍威尔条件，若满足，则转下一步，否则检验鲍威尔条件，若满足，则转下一步，否则转第转第7）步。）步。6）置第）置第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)并
20、置并置 k k+1，返回第，返回第2）步。）步。举例：举例：用鲍威尔法求目标函数用鲍威尔法求目标函数 f(X)=10(x1+x2 5)2+(x1 x2)2 的无约的无约束最优解。初始点束最优解。初始点X(0)=0 0 T，迭代收敛精迭代收敛精度度=0.001。4.3 单形替换法单形替换法 基本思想基本思想 通过计算出若干点处的函数值，对其大通过计算出若干点处的函数值，对其大小进行比较，可以看出函数值变化的大致趋小进行比较，可以看出函数值变化的大致趋势，从而可以寻求使函数值下降的搜索方向。势，从而可以寻求使函数值下降的搜索方向。在在n维空间中，由维空间中，由n+1个不同点顺序相连，就个不同点顺序
21、相连，就可以构成一个具有可以构成一个具有n+1个顶点的多面体个顶点的多面体称称之为单纯形。计算函数在这之为单纯形。计算函数在这n+1个顶点的函数个顶点的函数值，并进行比较，据此来确定有利的搜索方值，并进行比较，据此来确定有利的搜索方向和步长，找到一个比较好的点来取代单纯向和步长，找到一个比较好的点来取代单纯形中较差的那个顶点，从而组成了一个新的形中较差的那个顶点，从而组成了一个新的单纯形，并用之取代原来的单纯形。如此下单纯形，并用之取代原来的单纯形。如此下去，新单纯形不断地向目标函数的极小点靠去，新单纯形不断地向目标函数的极小点靠近，直到搜索到极小点为止。近，直到搜索到极小点为止。计算步骤计算
22、步骤 1）构造初始单纯形）构造初始单纯形 选初始点选初始点X0，和步长，和步长h。从。从X0出发沿各坐出发沿各坐标轴方向分别走步长标轴方向分别走步长h，得到，得到n个顶点个顶点Xi(i=1,2,n)，与，与X0构成初始单纯形。构成初始单纯形。X0 x2x1X1X2 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(XH)=max fi:i=0,1,2,n fG=f(XG)=max fi
23、: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 x2x1X1X2
24、XHXLXGXn+1Xn+2 6）扩张：当）扩张：当 fn+2 f L 时，取时，取扩张点扩张点Xn+3，即，即Xn+3=Xn+1+(Xn+2 Xn+1)(=1.22.0)并计算并计算 fn+3=f(Xn+3)。若若 fn+3 fn+2，则以，则以Xn+3 代替代替XH，fn+3代替代替fH，构造一个新的单纯形；，构造一个新的单纯形；否则，以否则，以Xn+2 代替代替XH，fn+2 代替代替fH，构造新的，构造新的单纯形；然后返回到单纯形；然后返回到 3）。）。Xn+3 7）收缩：当）收缩：当 fn+2 f G 时，则需收缩。时，则需收缩。若若 fn+2 fH，则取，则取收缩点收缩点Xn+4：
25、Xn+4=Xn+1+(Xn+2 Xn+1)（=0.5）fn+4=f(Xn+4)否则，以否则，以XH代替上式中的代替上式中的Xn+2，计算计算收敛点收敛点Xn+4：Xn+4=Xn+1+(XH Xn+1)fn+4=f(Xn+4)X0 x2x1X1X2XHXLXGXn+1Xn+2Xn+3 若若 fn+4 fH，则以，则以Xn+4 代替代替XH，fn+4代替代替fH，形成新的单纯形，然后返回到，形成新的单纯形，然后返回到 3）；否则）；否则转下一步转下一步8）。）。Xn+4Xn+4 8）缩边：将单纯形向）缩边：将单纯形向XL缩边，可以将各向量缩边，可以将各向量 (Xi XL)(i=0,1,2,n)的长度都缩小一半，即的长度都缩小一半，即 Xi=XL+0.5(Xi XL)=0.5(Xi +XL)(i=0,1,2,n)形成新的单纯形，然后返回到形成新的单纯形，然后返回到 2）。）。X0 x2x1X1X2XHXLXG 举例：举例：用单形替换法求目标函数用单形替换法求目标函数 f(X)=4(x1 5)2+(x2 6)2 的无约束最优解。的无约束最优解。初始点初始点X0=8 9T，X1=10 11T，X3=8 11T，迭代收敛精度迭代收敛精度=0.01。
