基于MATLAB的鲍威尔法求极值问题.doc

机械优化设计报告（4）13基于MATLAB的鲍威尔法求极值问题姓名：xxx学号：xxx（北京理工大学机械与车辆学院车辆工程北京100081）摘要：无约束优化方法主要有七种按照求导与否把这些方法分为间接法和直接法。牛顿法的成败与初始点选择有极大关系其可靠性最差；坐标轮换法、单纯形法和最速下降法对于高维优化问题计算效率很低有效性差；由于编制变尺度法程序复杂其简便性不足。综合考虑后鲍威尔法、共轭梯度法具有较好的综合性能。本文首先对鲍威尔法的原理进行阐述根据其迭代过程给出流程图并编写MATLAB程序。最后用此MATLAB程序求解实际的极值问题并对求解结果进行简要分析。鲍威尔法的基本思想1.1其他优化方法对鲍威尔法形成的影响通过对鲍威尔法的学习可以很明显看出来其迭代思想中汲取了其他几种优化方法的核心思想。为了更全面、更深入的学习鲍威尔法很有必要对其他有影响的优化思想进行学习和梳理。由最基本的数学基础知识可知梯度方向是函数增加最快的方向负梯度方向是函数下降最快的方向于是利用这个下降最快方向产生了最速下降法。每次迭代都沿着负梯度方向进行一维搜索直到满足精度要求为止。其特点是相邻两个搜索方向互相正交所以很明显的一个现象就是刚开始搜索步长比较大愈靠近极值点其步长愈小收敛速度愈慢特别当二维二次目标函数的等值线是较扁的椭圆时迭代速度更慢。这时倘若目标函数是等值线长、短轴都平行于坐标轴的椭圆形则通过坐标轮换法可以很高效的解决问题。通过两次分别沿坐标轴进行一维搜索便可达到极值点。但对于目标函数的等值线椭圆的长、短轴倾斜于坐标轴时坐标轮换法的搜索效率也显得极低。抛开这两种特殊情况对于一般形态的目标函数如果在某些明显可以直达最优点的情况下（一般为靠近极值点区域）迭代过程完全可以不沿负梯度方向搜索取而代之的是找到直达最优点的方向一步到位。但这样的直达方向应该如何去找呢？共轭梯度法由此产生。其基本原理是：任意形式的目标函数在极值点附近的特性都近似一个二次函数其等值线在极值点附近为近似的同心椭圆簇而同心椭圆簇有一个特性便是任意两条平行线与椭圆簇切点的连线必通过椭圆的中心。而这个连线方向便是所寻找的直达方向。通过对其迭代过程的分析很明显可以看出需大量的求目标函数的一阶和二阶偏导数。对于一些实际的机械优化问题目标函数可能复杂到难以求取其偏导数或者根本就不存在求取极值问题就显得无从下手。所以一个效率高的、适应性强的优化方法急需出现而鲍威尔法便是这么一种综合的方法。1964年鲍威尔提出了对共轭方向法的改进方法——鲍威尔共轭方向法。一维搜索法、共轭方向和坐标轮换法的思想在鲍威尔法中体现的淋漓尽致。下面就对鲍威尔法的基本原理进行阐述。1.2鲍威尔法的数学原理通过前文可知鲍威尔法也算一种共轭方向法但与共轭梯度法相比不需要对函数求导而是在迭代过程中逐次构造出用于搜索的共轭方法。对于二维无约束优化问题采用鲍威尔法求解的迭代过程如图1-1所示。任选一初始点令按照坐标轮换法选择两个单位向量和以此作为搜索方向进行第一轮搜索得到点。用和的连线方向构成新的搜索方向。从点出发沿方向一维搜索得到点作为下一轮搜索的初始点。从出发依次沿和方向进行一维搜索得到点和点。用点和点的连线方向构成新的搜索方向。和是从两个不同点出发沿相同方向搜索得到的所以与和的连线方向互为共轭方向。从点出发沿方向一维搜索得到点。因是从点出发依次沿两个互为共轭的方向和进行两次一维搜索得到的所以就是该二维二次函数的极小点。图1-1二维情况下鲍威尔法的迭代过程将上述二维优化问题扩展到n维的情况得到鲍威尔法的基本迭代过程：从初始点出发依次沿n个线性无关的方向组进行一维搜索得到一个终点沿初始点和终点的连线方向一维搜索得到下一轮迭代的初始点并以这个方向作为下一轮迭代方向组中的最后一个方向同时去掉第一个方向组成的新方向组进行第一轮迭代。若目标函数是个n维的正定二次函数则经过这样的n轮迭代以后就可以收敛到最优点。但是这种方法有一个缺陷通过这种方法产生的n个新方向有可能是线性相关或近似线性相关的。因为新方向如果其中出现了则就可以表示为…的线性组合这样用新方向替换后新的坐标轮换方向组就成为线性相关的一组向量以后的各轮迭代计算将在维数下降了的空间内进行这将导致算法收敛不到真正的最优点。针对此现象通过适当改进产生了新的鲍威尔法。1.3改进的鲍威尔法由上一小节讨论可知如果对新方向组的形成加以适当的选择防止其线性相关则可以避免鲍威尔法的“退化”。在这里直接给出是否用方向替代来组成新的搜索方向组的判别条件供后面编程所用。设。其中最大者。若且成立则用方向替代方向否则仍用原来的n个搜索方向。这样改进后的鲍威尔法保证了对于非线性函数计算时收敛的可靠性。迭代过程和算法流程图2.1迭代过程给定初值点n个线性无关的初始向量组及精度置。从点出发沿中的方向进行一维搜