第4章无约束优化方法分解.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 第四章 无约束优化方法 第六节 变尺度法（拟牛顿法） ， 变尺度法的流程图： 第四章 无约束优化方法 第六节 变尺度法（拟牛顿法） ， DFP算法： DFP算法的校正公式 第四章 无约束优化方法 第六节 变尺度法（拟牛顿法） ， DFP算法： 第四章 无约束优化方法 第七节 坐标轮换法 ， 基本思想： 每次仅对多元函数的一个变量沿其坐标轴进行一维探索，其余各变量均固定不动，并依次轮换进行一维探索的坐标轴，完成第一轮探索后再重新进行第二轮探索，直到找到目标函数在全域上的最小点为止。 目的：将一个多维的无约束最优化问题，转化为一系列的一维问题来求解。 第四章 无约束优化方法 第七节 坐标轮换法 ， 二维问题 第四章 无约束优化方法 第七节 坐标轮换法 ， 第k轮迭代公式： 包括正负 第四章 无约束优化方法 第七节 坐标轮换法 ， 步长α的几种取法： 随机选择方法 加速步长法 最优步长法（一维搜索方法，如：黄金分割法、二次插值法，来确定最优步长） 第四章 无约束优化方法 第七节 坐标轮换法 ， 加速步长法： 第四章 无约束优化方法 第七节 坐标轮换法 ， 坐标轮换法的流程图 第四章 无约束优化方法 第七节 坐标轮换法 ， 坐标轮换法的特点： 计算简单、概念清楚、易于掌握；但搜索路线较长（需要经过多次曲折迂回的路径才能达到极值点），计算率较低，特别是当维数很高时很费时，所以坐标轮换法只能用于低维（n10）的优化问题求解。此外，坐标轮换法的效率在很大程度上取决于目标函数的性态，也就是等值线的形态与坐标轴的关系。 第四章 无约束优化方法 第八节 鲍威尔法 ， 鲍威尔法的基本思想： 直接利用迭代点的目标函数值来构造共轭方向，然后再从任一初始点出发，逐次的共轭方向作一维搜索求极值点。 第四章 无约束优化方法 第八节 鲍威尔法 ， 共轭方向的生成： 结论：从不同的两点出发，沿同一方向进行两次一维搜索，所得两个极小点的连线方向便是原方向共轭的另一方向。 第四章 无约束优化方法 第八节 鲍威尔法 ， 共轭方向的生成： 二维情况： 任意点出发沿着x1轴方向和AB方向搜索，即可得到极小点。 第四章 无约束优化方法 第八节 鲍威尔法 ， 基本POWELL法（二维）： 第四章 无约束优化方法 第八节 鲍威尔法 基本POWELL法（n维）： 1）从初始点出发，首先沿着n个坐标轴方向进行一维搜索，得到一个终点； 2）由初始点和终点连线形成一个新方向，该方向排在原方向组的最后，去掉原方向组的的第一个方向，形成新的方向组； 3）从上一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。 4）从新的始点出发，沿着新的方向组做一维搜索。 如此反复进行n轮搜索后，可找到n个共轭方向，若目标函数是正定二次型函数，则经过n轮后就可以找到极小点。 第四章 无约束优化方法 第八节 鲍威尔法 改进POWELL法： 获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向。 1）给定初始点 ，选取初始方向组，它由n个线性无关的向量组成 置k=0 2）从 出发顺次沿 作一维搜索得 接着以 为起点，沿方向 移动一个距离 得到 并分别求出 改进POWELL算法的步骤: 一轮迭代的始点 一轮迭代的终点 一轮迭代的反射点 同时计算各中间点函数值 计算n个函数值之差 并找出其中最大的一个 （3）根据是否满足判别条件 来确定是否对原方向组进行替换。 因此有 ， 不满足判别条件，下轮迭代仍用原方向组，并以 中函数值小者作为下一轮迭代的始点。 满足判别条件，则下轮迭代的方向组为 下一轮迭代的初始值为沿 方向进行一维搜索 的极小值点 （4）判断是否满足收敛准则，满足 为极小值点，否则，应进行下一轮迭代。 ， 第四章 无约束优化方法 第八节 鲍威尔法 例： * * * * * * * * * * * 第四章 无约束优化方法 × 4.1 概述 4.2 最速下降法 4.3 牛顿型方法 4.4 共轭方向及共轭方向法 4.5 共轭梯度法 4.6 变尺度法