资源描述:
《无约束最优化的直接方法ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、Ch11无约束最优化的直接方法1模式搜索法2Rosenbrock算法3Powell方法1.模式搜索法1基本思想Hooke&Jeeves(1961)探测移动依次沿n个坐标轴进行,用以确定新的基点和有利于函数值下降的方向.模式移动沿相邻两个基点连线方向进行.从几何意义上看,寻找具有较小函数值的“山谷”力图使迭代产生的序列沿“山谷”走向逼近极小点,算法从初始基点开始,包括两种类型的移动----探测移动和模式移动.1.模式搜索法1.模式搜索法设目标函数为f(x),xEn.坐标方向给定初始步长,加速因子.任取初始点x(1)作
2、为第1个基点.x(j):第j个基点.y(j):沿ej探测的出发点y(n+1):沿en探测得到的点1.模式搜索法首先,从y(1)=x(1)出发,进行探测移动.先沿e1探测并从y(2)出发,沿e2进行探测.否则,沿e1方向的探测失败,再沿-e1方向探测并从y(2)出发,沿e2进行探测.1.模式搜索法再从y(2)出发,沿e2进行探测.方法同上,得到的点记为y(3).按此方式作下去直至沿n个方向探测完毕,得到点y(n+1).此时,可望d=x(2)-x(1)是有利于函数值减小的方向.1.模式搜索法下一步,沿方向x(2)-x(1)进
3、行模式移动,令新的y(1)y(1)=x(2)+(x(2)-x(1))(1.5)模式移动后,以y(1)为起点进行探测移动,这轮探测移动仍然沿坐标轴方向进行.探测完毕,得到的点仍记做y(n+1)若f(y(n+1))4、满足精度为止,即步长小于事先给定的某个小的正数为止1.2计算步骤1.模式搜索法进行步4.,否则转3进行步4.,否则令进行步4.y(j+1)=y(j)1.模式搜索法4.若j5、结果如下1.模式搜索法012(2,0)81012(1,1)0(1,1)0(1,1)1模式搜索法012(1,1)0(1,1)0(1,1)012(1,1)0(1,1)0(1,1)2.Rosenbrock算法(转轴法)2.1,方法概述算法每次迭代包括探测阶段和构造搜索方向两部分探测阶段:从一点出发,依次沿n个单位正交方向进行探测移动,一轮探测之后,再从第1个方向开始继续探测.经过若干轮探测移动,完成一个探测阶段.同时得到一组新的正交方向,将其单位化.称之为转轴.1.探测阶段2.Rosenbrock算法它们是单位正交方向,沿各方
6、向的步长为每轮探测的起点和终点用y(1)和y(n+1)表示.令y(1)=x(k),开始第1轮探测移动先从y(1)出发,沿d(1)探测2.Rosenbrock算法再从y(2)出发,沿d(2)作探测移动.得y(3).按此方式探测下去,直至沿d(n)探测,得到y(n+1)2.Rosenbrock算法完成一轮探测后,令y(1)=y(n+1)进行下一轮探测.往复下去,至某一轮沿n个方向的探测均失败,.第k次迭代的探测结束时,得到的点记为x(k+1)=y(n+1)2.构造新的搜索方向2.Rosenbrock算法2.Rosenbroc
7、k算法2.Rosenbrock算法将其正交化再单位化可证如下引理:2.Rosenbrock算法2.2计算步骤2.Rosenbrock算法3.若j8、brock方法计算下列函数极小值点2.Rosenbrock算法则第1次探测时有方向经过的点函数值结果--(0,0)3--d(1)=(1,0)(1,0)1成功d(2)=(0,1)(1,1)1成功d(1)(4,1)4失败d(1)(1,4)13失败2.Rosenbrock算法在两个搜索方向都获得一次成功并接着一次失败后。我