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

《机械优化设计ppt课件第四章 无约束优化的直接搜索法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、机械优化设计太原科技大学张学良第四章无约束优化的直接搜索法各种无约束优化方法的区别就在于确定其搜索方向S(k)的方法不同，所以搜索方向的构成问题是无约束优化方法的关键。根据构造搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类：X(k+1)=X(k)+(k)S(k)(k=0,1,2,…)一类是只利用目标函数值信息的无约束优化方法，如坐标轮换法、鲍威尔法，称为直接搜索法；另一类是利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法，称为间接搜索法。基本思想§4.1坐标轮换法（变量轮换法、交替法、降维法）将n维无约束优化问题转化为n个沿坐标轴

2、方向ei(i=1,2,…,n)的一维优化问题来求解，并记完成n次一维搜索为一轮。若一轮搜索后未得到满足精度要求的最优点，则继续下一轮迭代搜索。如此反复，直至得到满足精度要求的最优点为止。在每一轮搜索中，每次迭代仅对n元函数的一个变量沿其坐标轴方向进行一维搜索，其余n-1个变量均保持不变，再依次轮换进行一维搜索的坐标轴，直至完成沿n个沿坐标轴方向的n次一维搜索。x1x2X0(1)X1(1)X2(1)取初始点X(0)=X0(1)，x1坐标轴方向的单位向量S1(1)=e1=[10]T，x2坐标轴方向的单位向量S2(1)=e2=[01]T。X1(1)=X0(1)+α1(1)S1(1)，X2(

3、1)=X1(1)+α2(1)S2(1)判断是否满足迭代收敛准则：

4、

5、X2(1)–X0(1)

6、

7、≤？X1(1)=X0(1)+α1(1)e1(1)=[x1(0)x2(0)]T+α1(1)[10]TX2(1)=X1(1)+α2(1)e2(1)=[x1(1)x2(1)]T+α2(1)[01]T第一轮迭代搜索：若满足，则输出最优解，否则，继续下一轮迭代搜索。Xi(k)=Xi-1(k)+αi(k)ei(k)(k—迭代轮次，i—k轮迭代的第i次一维搜索αi(k)—一维搜索求得的最优步长）

8、

9、Xn(k)–X0(k)

10、

11、≤？计算步骤与算法框图1）任选初始点X(0)=X0(1)=[x1(0)x2(0

12、)…xn(0)]T，给定迭代收敛精度，i=1，k=1。2）置n个坐标轴方向向量为单位向量，即e1=[10…0]T，e2=[010…0]T，…，en=[0…01]T。3）按如下迭代计算公式进行迭代计算Xi(k)=Xi-1(k)+αi(k)ei(k)(k—迭代轮次，i—k轮迭代的第i次一维搜索i=1，2，…，n）4）判断是否满足迭代收敛准则

13、

14、Xn(k)–X0(k)

15、

16、≤？若满足，则输出最优解:X*=Xn(k)，f*=f(X*)否则，令X0(k+1)=Xn(k)，kk+1，返回3）。举例：用坐标轮换法求目标函数f(X)=x12+x22–x1x2–4x1–10x2+60的无约束最优解

17、。初始点X(0)=[00]T，迭代收敛精度=0.1。坐标轮换法搜索过程和收敛情况讨论X0(1)X*X1(1)X0(1)X*X1(1)x1x2X0(1)X1(1)X2(1)X*等值线出现脊线的情况（4M14图）§4.2鲍威尔（Powell）法基本思想它是直接利用函数值来构造共轭搜索方向的一种共轭搜索方向法，又称鲍威尔共轭方向法或方向加速法。由于对于n维正定二次函数，共轭搜索方向具有n次收敛的特性，所以鲍威尔法是直接搜索法中十分有效的一种算法，一般认为对于维数n≤20的目标函数它是成功的。鲍威尔法是在研究具有正定对称矩阵H的二次函数的极小化问题时形成的，其基本思想是在不用函数导数信息的

18、前提下，在迭代过程中逐次构造关于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.5XTHX+BTX+C在X(k)和X(k+1)两点处的梯度可以表示为▽f(X(k))=HX(k)+B（1）▽f(X(k+1))=HX(k+1）+B（2）（2）－（1）得▽f(X(k+1))－▽f(X(k))=H(X(k+1)－X(k))（3）（3）式

19、两边同时左乘[S(j)]T得[S(j)]T[▽f(X(k+1))－▽f(X(k))]=[S(j)]TH(X(k+1)－X(k))=0即[S(j)]TH(X(k+1)－X(k))=0若取S(k)=X(k+1)－X(k)那么，S(k)和S(j)关于H共轭，即[S(j)]THS(k)=0这说明：沿S(j)方向分别对函数做两次一维搜索，得到两个极小点X(k)和X(k+1)，该两点的连线方向S(k)与S(j)是关于H共轭的方向。X(k)x1x2X*S(j)X(k+1