三无约束优化方法.ppt

例4-4 二维无约束目标函数 试用单形替换法求其极小值。 解： 选 为顶点做初始单纯形，计算各顶点函 数值： 可见最好点xL =x0,最差点xH = x1，次差点xG = x2。求x0， x2的重心x3： 求反射点x4及其函数值 f4： 由于 f4 f0 , 故需要扩张，取 得扩张点x5 ： 由于 f5 f4 , 故以x5代替x4，由x0x2x5构成新单纯形 ，进行下一循环，经过32次循环，可将目标函数值降到1×10-6,接近极小值。 f *= f (x*)= f (5,6)=0. 单纯形法一般用于维数小于10的情况。 §3.7 无约束优化设计方法小结 1.可靠性。即在合理的精度要求下，在一定允许的时间内能解出各种不同类型问题的成功率。能够解出的问题越多，则算法的可靠性越好； 2.有效性。即算法的解题效率。它有两个衡量标准。其一是对同一题目，在相同精度和初始条件下，比较机时多少。其二是在相同精度下，计算同一题目所需要的函数的计算次数； 3.简便性。一方面指实现该算法的准备工作量的大小。另一方面指算法占用存储单元的数量。 一. 评价准则: §3.7 无约束优化设计方法小结 二. 适用范围: 可靠性：牛顿法较差，因为它对目标函数要求太高，解题成功率较低。 有效性：坐标变换法和梯度法的计算效率较低，因为它们从理论上不具有二次收敛性。 简便性：牛顿法和变尺度法的程序编制较复杂，牛顿法还占用较多的存储单元。 §3.7 无约束优化设计方法小结 三. 优化方法的选择: 在选用无约束优化方法时，一方面要考虑优化方法的特点，另一方面要考虑目标函数的情况。 1、一般而言，对于维数较低或者很难求得导数的目标函数，使用坐标轮换法或鲍威尔法较合适。 2、对于二次性较强的目标函数，使用牛顿法效果好。 3、对于一阶偏导数易求的目标函数，使用梯度法可使程序编制简单，但精度不宜过高。 4、综合而言，鲍威尔法和DFP法具有较好的性能。 §3.7 无约束优化设计方法小结 Poweel法 共轭梯度法 牛顿法 变尺度 (DFP)法 迭代次数 搜索次数 搜索方向 收敛速度 存储量 适用维数 稳定性 2 2 1 2 6 2 1 2 共轭方向 零阶算法 一阶算法 二阶算法 超线性 较慢 二次收敛 收敛最快 二次收敛 小 中 最大 较大 存储量随n2↑ 随n↑，t↑↑ n20 n200～300 好 中 差 中下 四. 各算法对比: 学习要求 1、掌握最速下降法， 2、掌握共轭方向概念； 3、掌握共轭梯度法原理和程序设计； 4、掌握牛顿法原理及流程设计； 5、了解鲍威尔方法，坐标轮换法，DFP变尺度法和单形替换法。 鲍威尔法的流程图 一. 梯度法（最速下降法）： 1.基本思想： 2.负梯度方向为最速下降方向的证明： 目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向为搜索方向，期望很快找到最优点。 S 由方向导数概念可得： 设： 取最小值－1时，S为梯度的负方向。 §3.4 梯度法和共轭梯度法 4.迭代格式： 3.搜索方向： a.任意给定一个初始步长，使其满足： 根据一元函数的极值必要条件和多元复合函数的求导公式，得： 或 负梯度方向 或单位负梯度向量 5.最佳步长 的选取： b.沿负梯度方向作一维搜索，求最佳步长，对目标函数求极小，以得到最佳步长： 即： §3.4 梯度法和共轭梯度法 最速下降法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。　这是因为，梯度是函数的局部性质，从局部上