机械优化设计教案第四章无约束优化PPT课件.ppt

1 第 章无约束优化方法 无约束优化算法 直接法 间接法 即不用导数信息的算法 它只需进行函数值的计算与比较 来确定迭代方向和步长 如 坐标轮换法 共轭方向法和鲍威尔法 即使用导数信息的算法 它需要利用函数的一阶或二阶偏导数矩阵 来确定迭代方向和步长 如 梯度法 牛顿法和变尺度法 4 1概述 无约束优化问题的数学模型 2 4 2坐标轮换法 变量轮换法 基本原理将一个多维无约束优化问题转化为一系列一维优化问题来求解 即 一次沿着坐标轴的方向进行一维搜索 求得极小点 图3 13 图4 1坐标轮换法的基本原理 3 图4 1坐标轮换法的基本原理 4 特点 坐标轮换法简单易行 但由于它只能轮流沿n个坐标方向前进 因而效率低下 特别是维数较高或目标函数性态不好的情况下 收敛速度很慢 5 图4 2模式搜索法 4 3模式搜索法 由图4 1可见 在沿着坐标进行了一轮搜索后 如果沿着所定义的方向进行一次寻优 将大大提高坐标轮换法寻优的速度 其基本原理如图4 2所示 基本原理 6 图4 2模式搜索法 特点 模式搜索法是对坐标轮换法的一种改进 它改变了完全沿着坐标方向寻优的模式 可以较好的提高计算精度 并利用已有的计算信息 但该方法需要储存函数在k轮迭代开始的坐标值 7 4 4Powell共轭方向法共轭方向法及其构成坐标轮换法的收敛速度很慢 原因在于其搜索方向总是平行于坐标轴 不适应函数的变化情况 8 图4 3共轭方向的形成 9 图4 3共轭方向的形成 10 11 12 共轭方向法的基本原理 图4 4共轭方向法的迭代过程 先采用坐标轮换法进行第一轮迭代 然后以第一轮迭代的最末一个极小点和初始点相连 构成一个新方向 并以此新方向为最末一个方向 而去掉第一个方向 得到第二轮迭代的n个方向 如此进行下去 直至求得问题的最小点 13 共轭方向法的迭代过程 以图示二维问题为例 14 15 Powell共轭方向法的基本原理共轭方向法的基本要求 各方向组的向量应该是线性无关的 然而很不理想的是 上述方法每次迭代时所产生的新方向可能出现线性相关 使搜索运算将在维数下降了的空间进行 从而导致计算不能收敛到真正的极小点而失败 16 针对上述问题 Powell提出了对共轭方向法的如下改进方法 在每一轮迭代完成并产生共轭方向后 先对共轭方向的好坏进行判别 检验它是否与其他方向线性相关 若共轭方向不好 则不用它作为下一轮的迭代方向 而仍采用原来的一组迭代方向 若共轭方向好 则可用它替换前一轮迭代中使函数值下降最多的一个方向 而不一定替代第一个迭代方向 17 在Powell共轭方向法中 判别是否用新的方向替换原方向组中某一方向的判别原则按下式是否同时满足来处理 图4 5 4 1 18 图4 5 19 20 Powell共轭方向法的迭代步骤 21 22 23 Powell共轭方向法的算法框图 A B 24 B C 25 结束 A C 图4 6 26 4 5最速下降法基本原理在迭代过程的某一点Xk处 目标函数的负梯度方向 f Xk 是函数的最速下降方向 最速下降法即利用这一性质 将n维无约束极小化问题转化为一系列沿目标函数负梯度方向进行一维寻优的一种方法 即在每一迭代点Xk 选取搜索方向Sk为负梯度方向 27 最速下降法的迭代公式 迭代步骤 28 29 图4 7等值线是椭圆 a 和圆 b 的情况下最速下降法的迭代过程 对于等值线为圆的优化问题 最速下降法一次迭代就可达到极小点 当等值线不是圆时 负梯度方向不再指向圆心 实线 迭代次数增加 偏心越严重 迭代次数越多 形成 锯齿现象 而且 在搜索开始时步长越大 愈接近极小点步长愈小 最后收敛的速度及其缓慢 30 最速下降法的特点 迭代过程简单 对初始点X0的要求不高 虽要计算导数 但只要求一阶偏导 存储单元较少 收敛慢 对于复杂的优化问题 最速下降法不具备实用价值 但由于在迭代开始时函数值下降较快 常用于其他方法中作初始迭代法 31 4 6牛顿法 求出这个二次近似函数的极小点 基本思想 牛顿法是最速下降法的进一步发展 其基本思想 在求目标函数f X 的极小值时 先将f X 在点Xk附近作泰勒展开 取其二次函数式 32 若f X 是二次函数 则X 即f X 的极小点 否则只是一个近似点 若该极小值满足精度要求 以该极小点作为原目标函数的近似极小点 否则 以此近似极小点作为下一次迭代的初始点 继续以上过程 迭代下去 直至所求出的近似极小点满足精度要求为止 33 34 阻尼牛顿法 或修正牛顿法 阻尼牛顿法是为了克服牛顿法的上述弊病 对其加以改进而提出的 牛顿法的特点牛顿法不仅利用了函数的一阶导数信息 还利用了函数的二阶导数信息 其收敛速度较最速下降法快得多 但牛顿法要计算Hessian矩阵及其逆矩阵 计算量存储量均很大 且都以维数n2比例增加 维数高时这个问题更加突出 此外 若Hessian矩阵是奇异矩阵时 其逆矩阵不存在 此方法便不能应用 对初始点的选取要求较高 否则不能收敛 阻尼牛顿法迭代公式 35 4 7变尺度法 DFP法及BFGS法 变尺度法是在克服了最速下降法的收敛慢和牛顿法计算量大的缺点而发展起来的 是求解无约束优化问题最有效的算法 在工程优化设计中得到了广泛的应用 变尺度法的迭代公式 4 2 基本思想 36 4 3 4 4 上式即最速下降法的迭代公式 上式即阻尼牛顿法的迭代公式 最速下降法和阻尼牛顿法可看作变尺度法的一种特殊形式 4 5 37 DFP变尺度法DFP算法的迭代修正矩阵 4 6 38 DFP变尺度法迭代步骤 39 40 DFP变尺度法的算法框图 41 DFP方法的特点 变尺度法在最初的几步迭代 与最速下降法类似 函数值下降较快 而在最后的几步迭代 与牛顿法相近 可较快地收敛到极小点 因此 变尺度法能够克服最速下降法收敛慢的缺点 但却保留了最速下降法在最初几步函数值下降快的优点 同时避免了计算Hessian矩阵及其逆矩阵 从而克服了牛顿法计算量大的缺点 但却有较快的收敛速度 所以 在目标函数的梯度容易计算的情况下 变尺度法是一种很有效的方法 但在计算变尺度矩阵的公式中 其分母含有近似矩阵Ak 计算中容易引起数值不稳定 甚至可能得到奇异矩阵Ak 为提高实际运算稳定性 通常将进行n次 n为目标函数的维数 迭代作为一个循环 将变尺度矩阵重置为n维单位矩阵I 并以一个循环的终点作为起点 进行下一轮的迭代 42 BFGS变尺度法为了进一步改善DFP变尺度法在实际计算中存在的算法稳定性 Broydon等人提出了改进的算法 BFGS变尺度法 BFGS法与DFP法的不同之处在于修正矩阵 Ak的计算公式不同 4 7 BFGS变尺度法的特点BFGS法的修正矩阵 Ak的计算公式分母中不再有近似矩阵Ak BFGS法的优点在于计算中它的数值稳定性强 该方法是变尺度法中最受欢迎的一种算法 43 4 8共轭梯度法共轭梯度法是由弗来特 Fletcher 和里伍斯 Reeves 提出的 共轭梯度法是共轭方向法的一种 因为在该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的 故称共轭梯度法 4 8 共轭方向与梯度之间的关系 44 图4 9共轭梯度法的几何说明 4 9 共轭梯度法便是利用这个性质做到不必计算矩阵G就能求得共轭方向 该性质的几何说明如图4 8所示 45 共轭梯度法的计算过程 46 47 4 9 48 49 4 10 50 从共轭梯度法的计算过程可以看出 第一个搜索方向取作负梯度方向 这是最速下降法 其余各步的搜索方向是将负梯度偏转一个角度 即对负梯度进行修正 因此 共轭梯度法实质上是对最速下降法进行的一种改进 故它又称旋转梯度法 共轭梯度法的特点 程序简单 存储量少 具有最速下降法的优点 而在收敛速度上比最速下降法快 具有二次收敛性 51 52 4 9单纯形法在实际工程的最优化问题中 目标函数的导数往往很难求出或者根本无法求出 单纯形法只需要计算目标函数值 无需求其导数 因此计算比较简单 其几何概念也比较清晰 属于直接法一类的无约束最优化方法 这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况 这也是直接法的一个优点 单纯形n维欧氏空间En中的单纯形 是指在n维空间中由n 1个线性独立的点构成的简单图形或凸多面体 如 在一维空间中为由两点构成的线段 在二维空间中为由不在同一直线上的三个点构成的三角形 在三维空间中为由不在同一平面上的四个点构成的四面体 53 基本思想根据问题的维数n 选取由n 1个顶点构成的单纯形 求出这些顶点处的目标函数值并加以比较 确定它们当中有最大值的点及函数值的下降方向 再设法找到一个新的比较好的点替换那个有最大值的点 从而构成新的单纯形 随着这种取代过程的不断进行 新的单纯形将向着极小点收缩 这样经过若干次迭代 即可得到满足收敛准则的近似解 大致求优步骤 54 55 4 11 4 12 4 13 56 4 14 4 15 4 16 4 17 57 图4 12单纯形法中的收缩步 58 单纯形法的计算步骤 59 60 61 62 63 4 10Hooke Jeeves直接探索法Hooke Jeeves与Powell又都属于模式探索方法 PatternSearchMethod Hooke Jeeves法的程序简单 当变量数较少时比较有效 适应性较强 但在每轮探索中包括了一次沿坐标轴的移步 其收敛速度虽比坐标轮换法有所改善 但仍然较慢 同样不适合高维数问题 每一轮探索包括两种移动 探测性移动和模式性移动 64 65 66 图4 13在二维空间中HookeJeeves法的探索过程 67 68 69 4 11Marquardt法 70 Marquardt法的基本原理 4 18 4 19 71 Marquardt法的迭代步骤 72 73 Marquardt法的特点Marquardt法的优点是算法简单 接近极小点时收敛得非常快 同时也不需要一维探索 但要计算Hessian矩阵并解式 4 18 所示的线性方程组 从而增加了工作量 尽管如此 它还是集中了最速下降法及牛顿法的优点 比它们有效 74 4 12最小二乘法 或Gauss Newton法 4 20 75 4 21 76 77 4 22 78 4 23 4 24 79 Gauss Newton法的迭代步骤 80 81 4 25 82 4 26 83 4 13小结在这许多无约束优化方法中 究竟哪个最好 由于实际问题的复杂性 和各种方法各自具有一定的特点 应该从多方面来进行分析 一般认为 评价一种算法的优劣可以从以下几方面加以考察 1 可靠性指算法在合理的精度要求下 在一定时间内能解出各种不同类型问题的成功率 能解出的问题越多 则算法的可靠性越好 有的文献称之为通用性 84 2 有效性指算法的解题效率 常有两种衡量标准 在同一题目 同一精度要求和同一初始点的情况下所用计算机的机时数 在同样条件下的函数求值次数 这里包括目标函数的求值和导数求值的总次数 后者与计算机的计算速度无关 可能更客观一些 3 准备工作量和占用存储单元的数量各种算法预先用解析法求出目标函数的一阶或二阶偏导数 有的方法编制程序比较复杂 如果算法所占用的存储单元数量多 则在维数很高时 使用时会受到计算