【教学课件】第十一讲非线性规划(三).ppt

《【教学课件】第十一讲非线性规划(三).ppt》由会员分享，可在线阅读，更多相关《【教学课件】第十一讲非线性规划(三).ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 1 11/10/20231/10/2023第二十三讲第十一讲第十一讲 非线性规划（三）非线性规划（三）1不使用导数的无约束寻优方法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Econo

2、mics&Managementpage page 2 21/10/20231/10/2023第二十三讲1 不使用导数的无约束寻优方法（1）不用导数的方法又称最优化搜索法，一般情况，利用导数迭代寻优比搜索法速度快。然而利用导数寻优常常面临两个困难：在多变量或复杂函数中，求导困难。执行方法前准备工作太多。因此，对使用者来说，非导数型搜索法还是常用的。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage p

3、age 3 31/10/20231/10/2023第二十三讲1 不使用导数的无约束寻优方法（2）1直接搜索法坐标轮换法该法是在寻优过程中，每次先让其它变量不变，轮流的顺次令某一个变量变化并取函数f(X)极小点（或极大点）。起始点为X(0)，先沿第1个坐标方向e1进行搜索，得最佳步长(0)及最优点X(1)，使满足：f(X(0)+e1)=f(X(0)+(0)e1)=f(X(1)即X(1)=X(0)+(0)e1Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool

4、 of Economics&Managementpage page 4 41/10/20231/10/2023第二十三讲1 不使用导数的无约束寻优方法（3）然后以X(1)为起点，沿e2坐标搜索，得最优解X(2)，即(X(1)+e2)=f(X(2)，X(2)=X(1)+(1)e2直到en为止，得X(n)：minf(X(n1)+en)=f(X(n1)+(n1)en)=f(X(n)即X(n)=X(n1)+(n1)en若X(n)X(0)1，则停止，得最优解X(n)=X*，否则，以X(n)为起点（令X(0)=X(n)）重新按上述步骤搜索。Operations Research Operations Re

5、search Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 5 51/10/20231/10/2023第二十三讲1 不使用导数的无约束寻优方法（4）这种方法简单、直观，但对于山脊形函数或自变量间有大的交互作用不适用。例如图4-11所示函数就不宜用该法寻优。最优点终点x2x1X(0)图4-11Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&Managem

6、entSchool of Economics&Managementpage page 6 61/10/20231/10/2023第二十三讲1 不使用导数的无约束寻优方法（5）步长加速法(Hooke and Jeeves method)或模式搜索法（PatternSearchmethod）。该法为改进坐标轮换法而设计，方法搜索简单（不在某方向上取极值点）。其主要分两步进行：环绕基点的“探测搜索”，称I型搜索。在选择的极小化方向上的“模式搜索”。又称II型搜索。第一步：先给出X的初始值X(0)及每步增量X值，然后按增量变化，求出下一个较好点。其方法为（都以求极小点为例）：Operations Re

7、search Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 7 71/10/20231/10/2023第二十三讲1 不使用导数的无约束寻优方法（6）先令x1(0)改变x1(0),即x1(1)=x1(0)+x1(0)，若fX，则以x1(0)+x1(0)作为X新元素分量；否则，令x1(1)=x1(0)x1(0)，若fX就令x1(0)x1(0)为新元素分量；若都不能使f fX，就仍令原X(0)为新元素，然后按同样方法把X2(0)

8、试采改变一个X2(0)值，直到变化n次，找到一个新点X(1)，便完成了“探测搜索”。第二步：以新点为基点，连接，按此矢量方向进行模式搜索或加速移步，模式搜索得到X(2)后，再进行II型探测搜索，就得到新点X(3)，Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 8 81/10/20231/10/2023第二十三讲1 不使用导数的无约束寻优方法（7）若fX(3)0称反射系数，=1时可保持

9、正多面体；1说明反射点可伸缩，通常取=1。ii)扩大若fXn+3(k)fXl(k)，则扩大战果，令Xn+4(k)Xn+2(k)Xn+3(k)Xn+2(k)为扩大系数，通常取=2。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 15151/10/20231/10/2023第二十三讲1 不使用导数的无约束寻优方法（14）若fXn+4(k)fXi(k)说明反射点值仍较大，则应收缩进去，即Xn

10、+5(k)Xn+2(k)+Xh(k)Xn+2(k)0fXh(k)，需将所有矢量Xi(k)Xl(k)缩减一半（i=1，2，n+1），即都向最小点靠近。Xi(k)=Xl(k)+0.5Xi(k)Xl(k)i=1，2，n+1v)其余情况令Xn+3(k)取代Xh(k)。这样便又构成新的多面体，重复上述步骤继续下去，直到多面体小到给定精度为止。其结束规则为：其中，给定精度 Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 17171/10/20231/10/2023第二十三讲1 不使用导数的无约束寻优方法（16）3Powell法（鲍威尔法）（略）