机械优化设计之无约束优化方法培训课件(ppt 94页).ppt

何军良 03 54 1 2 目录 CONTENTS 03 54 第四章无约束优化方法 概述 01 最速下降法 牛顿型方法 共轭方向与共轭方向法 02 03 04 坐标轮换法 05 共轭梯度法 变尺度法 鲍威尔方法 06 07 08 单形替换法 09 03 54 3 变尺度法也称拟牛顿法 它是基于牛顿法的思想而又作了重大改进的一类方法 我们所介绍的变尺度法是由Davidon于1959年提出又经Fletcher和Powell加以发展和完善的一种变尺度法 故称为DFP变尺度法 4 7变尺度法 能否克服各自的缺点 综合发挥其优点 2 阻尼牛顿法 1 梯度法 简单 开始时目标函数值下降较快 但越来越慢 目标函数值在最优点附近时收敛快 但要用到二阶导数和矩阵求逆 1 问题提出 4 4 7变尺度法 2 基本思想 变量的尺度变换是放大或缩小各个坐标 通过尺度变换可以把函数的偏心程度降到最低限度 这种算法仅用到梯度 不必计算海赛阵及其逆矩阵 但又能使搜索方向逐渐逼近牛顿方向 具有较快的收敛速度 尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质 例如在用最速下降法求极小值时 需要进行10次迭代才能达到极小点 梯度法 牛顿法 5 4 7变尺度法 2 基本思想 进行尺度变换 在新的坐标系中 函数f x 的二次项变为 目的 减少二次项的偏心 如G是正定 则总存在矩阵Q 使得 对于二次函数 6 4 7变尺度法 2 基本思想 用矩阵Q 1右乘等式两边 得 用矩阵Q左乘等式两边 得 所以 上式说明 二次函数矩阵G的逆阵 可以通过尺度变换矩阵来求得 7 3 变尺度法的搜索方向 S k Akgk 称为拟牛顿方向 1 Ak为构造的n n阶对称矩阵 它随迭代点的位置变化而变化 对梯度起到改变尺度的作用 又称为变尺度矩阵 若Ak I 上式为梯度法的迭代公式若Ak Hk 1 上式为阻尼牛顿法的迭代公式 3 迭代公式 4 7变尺度法 2 当矩阵Ak不断地迭代而能很好地逼近时 就可以不再需要计算二阶导数 变尺度法的关键在于尺度矩阵Ak的产生 8 拟牛顿方向S k Akgk必须具有下降性 收敛性和计算的简便性 下降性 要求变尺度矩阵为对阵正定矩阵 收敛性 要求变尺度矩阵逐渐逼近Hk 1 满足拟牛顿条件 简便性 希望变尺度矩阵有如下递推形式 Ak 1 Ak Ak 4 变尺度矩阵的产生 4 7变尺度法 9 下降性 要求S k 与 gk之间的夹角小于90o 即 S k Tgk 0 将拟牛顿方向带入上式 得 S k Tgk Akgk Tgk gk TAkgk 0 所以只要Ak为对阵正定矩阵 S k 就是下降方向 4 变尺度矩阵的产生 4 7变尺度法 10 变尺度矩阵是随迭代过程的推进而逐次改变的 因而它是一种矩阵序列 选取初始矩阵A0 并以梯度方向快速收敛 通常取单位矩阵E作为初始矩阵 即A0 E 而后的矩阵均是在前一构造矩阵的基础上校正得到 令 推广到一般的k 1次构造矩阵 Ak k 1 2 A1 A0 A0 Ak 1 Ak Ak 矩阵序列的基本迭代式 Ak称为校正矩阵 4 变尺度矩阵的产生 4 7变尺度法 简便性 11 构造矩阵Ak 1应该满足一个重要条件 拟牛顿条件 变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵 主要目的之一就是为了避免计算二阶偏导数和逆矩阵 力图仅用梯度和其他一些易于获得的信息来确定迭代方向 因此 拟牛顿条件是关于海赛矩阵和梯度之间的关系 5 拟牛顿条件 4 7变尺度法 12 设F x 为一般形式n阶的目标函数 并具有连续的一 二阶偏导 在点x k 处的二次泰勒近似展开 该近似二次函数的梯度为 式中 若令 则有 5 拟牛顿条件 4 7变尺度法 13 上式中 x k 1 x k 称之为位移矢量 并简化书写 而gk 1 gk是前后迭代点的梯度矢量差 简化书写 由以上三式得 海赛矩阵与梯度间的关系式 5 拟牛顿条件 4 7变尺度法 14 按照变尺度法产生构造矩阵的递推思想 期望能够借助前一次迭代的某些结果来计算下一个构造矩阵 因此可以根据上式 用第k 1次构造矩阵Ak 1近似代替Hk 1 则 上式即产生构造矩阵Ak 1应满足的一个重要条件 通常称为拟牛顿条件或拟牛顿方程 5 拟牛顿条件 4 7变尺度法 15 6 变尺度矩阵的构造 4 7变尺度法 拟牛顿条件可写成 或 DFP算法中的校正矩阵 Ak取为下列形式 待定系数 保证 Ak对称 16 6 变尺度矩阵的构造 4 7变尺度法 将 2 代入 1 两边对比得 取 则 回代到 2 得 DFP变尺度法的迭代式为 17 由上式可以看出 构造矩阵Ak 1的确定取决于第k次迭代中的下列信息 上次的构造矩阵 Ak迭代点的位移矢量 迭代点的梯度增量 因此 不必作二阶导数矩阵及其求逆的计算 6 变尺度矩阵的构造 4 7变尺度法 18 DFP算法的收敛速度介于梯度法和牛顿法之间 DFP法具有二次收敛性 搜索方向的共轭性 对于二次函数F x DFP法所构成的搜索方向序列S 0 S 1 S 2 为一组关于海赛矩阵H共轭的矢量 即DFP法属于共轭方向法 具有二次收敛性 在任何情况下 这种方法对于二次目标函数都将在n步内搜索到目标函数的最优点 而且最后的构造矩阵An必等于海赛矩阵H 7 DFP变尺度算法的特点 4 7变尺度法 19 7 DFP变尺度算法的特点 4 7变尺度法 关于算法的稳定性 数值计算稳定性较差 算法的稳定性是指算法的每次迭代都能使目标函数值单调下降 构造矩阵正定性从理论上肯定了DFP法的稳定性 但实际上 由于每次迭代的一维搜索只能具有一定的精确度 且存在机器运算的舍入误差 构造矩阵的正定性仍然有可能遭到破坏 为了提高实际计算中的稳定性 一方面应对一维搜索提出较高的精度要求 另一方面 当发生破坏正定性时 将构造矩阵重置为单位矩阵E重新开始 通常采用的简单办法是在n次迭代后重置单位矩阵 20 任取初始点x 0 给出迭代精度 计算初始点精度及其模 若转步骤 否则进行下一步 置k 0 取Ak E 计算迭代方向 沿S k 方向做一维搜索求优化步长a k 使 确定下一个迭代点 8 DFP变尺度算法的计算步骤 4 7变尺度法 21 计算x k 1 的梯度gk 1及其模 若则转步骤 否则转下一步 计算位移矢量和梯度矢量 按DFP公式计算构造矩阵 置k k 1 若k n n为优化问题的维数 返回步骤 否则返回步骤 输出最优解 x F 终止计算 8 DFP变尺度算法的计算步骤 4 7变尺度法 22 DFP算法流程图 k n 入口 出口 23 解 1 取初始点 为了按DFP法构造第一次搜寻方向d0 需计算初始点处的梯度 取初始变尺度矩阵为单位矩阵A0 I 则第一次搜寻方向为 例 用DFP算法求下列问题的极值 24 9 DFP算例 4 7变尺度法 一维搜索最佳步长应满足 得 2 再按DFP法构造点x1处的搜寻方向d1 需计算 沿d0方向进行一维搜索 得 9 DFP算例 4 7变尺度法 25 代入校正公式 9 DFP算例 4 7变尺度法 26 第二次搜寻方向为 再沿d1进行一维搜索 得 9 DFP算例 4 7变尺度法 27 为一维搜索最佳步长 应满足 得 3 判断x2是否为极值点 梯度 海赛矩阵 9 DFP算例 4 7变尺度法 梯度为零向量 海赛矩阵正定 可见满足极值充要条件 因此为极小点 28 例 用DFP变尺度法求目标函数 的最优解 已知初始点 迭代精度 0 01 解 第一次迭代 9 DFP算例 4 7变尺度法 29 式中最优步长应用一维搜索方法在计算机上求解 为了说明问题 又因为此例目标函数简单 所以用解析法来求 为求极小 将上式对 求导 并令f 0 得 于是 9 DFP算例 4 7变尺度法 30 第二次迭代 确定x 1 点的拟牛顿方向S 1 按DFP公式计算构造矩阵 9 DFP算例 4 7变尺度法 31 将数据代入得 则拟牛顿方向为 沿S 1 方向进行一维搜索求最优点x 2 求一维搜索步长 9 DFP算例 4 7变尺度法 32 则 迭代即可结束 输出优化解 9 DFP算例 4 7变尺度法 33 讨论 该题的理论最优点是 按DFP搜索方向为共轭的性质 本题为二元二次函数在两次迭代后即达到最优点 本题计算结果稍有误差 这是由于一维搜索的不精确性产生的 若在已知A1的基础上 再用DFP公式递推下一次的构造矩阵 可计算得 而计算目标函数海赛矩阵的逆阵有 9 DFP算例 4 7变尺度法 34 DFP算法由于舍入误差和一维搜索的不精确 有可能导致Ak奇异 而使数值稳定性方面不够理想 所以1970年 Broyden Fletcher Goldstein Shanno等人提出一种更稳定的算法 称为BFGS算法 其校正公式为 9 BFGS变尺度法 4 7变尺度法 35 36 1 概述 4 8鲍威尔方法 基本思想 基于坐标轮换法 不用求导数 在迭代中逐次产生共轭搜索方向 收敛效果 对于正定 有极小值 二次函数 经过n轮迭代后求得极小点 对于非二次函数 一般也具有较高的收敛速度 Powell法是求解无约束优化问题的最好方法 将其与惩罚函数法结合 可以处理有约束优化问题 为两个极小点 根据梯度与等值面之间关系可知 2 共轭方向的生成 4 8鲍威尔方法 37 对于二次函数 两点处的梯度可表示为 代入到公式 2 共轭方向的生成 4 8鲍威尔方法 38 结论 从不同的点出发沿某一方向分别对函数作两次一维搜索 得到两个极小点 那么这两个极小点的连线方向与该方向对G共轭 2 共轭方向的生成 4 8鲍威尔方法 39 3 基本算法 4 8鲍威尔方法 鲍威尔基本算法的搜索过程 二维 1 任选一初始点x0 再选两个线性无关的向量 如坐标轴单位向量e1 1 0 T和e2 0 1 T作为初始搜索方向 40 3 基本算法 4 8鲍威尔方法 鲍威尔基本算法的搜索过程 二维 2 从x0出发 顺次沿e1 e2作一维搜索 得点 两点连线得一新方向d1 41 3 基本算法 4 8鲍威尔方法 鲍威尔基本算法的搜索过程 二维 用d1代替e1形成两个线性无关向量d1 e2 作为下一轮迭代的搜索方向 再从出发 沿d1作一维搜索得点 作为下一轮迭代的初始点 3 从出发 e2 d1作一维搜索 得到点 两点连线得一新方向 x 1 x 2 x 0 o e 1 e 2 d 1 d 2 x 1 从沿d2作一维搜索得点x2 即是二维问题的极小点x 42 3 基本算法 4 8鲍威尔方法 鲍威尔基本算法的搜索过程 二维 方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤 43 3 基本算法 4 8鲍威尔方法 鲍威尔基本算法的搜索过程 三维 44 第一轮基本方向组取单位坐标矢量系e1 e2 e3 en 沿这些方向依次作一维搜索 然后将始末两点相连作为新生方向 再沿新生方向作一维搜索 完成第一轮的迭代 以后每轮的基本方向组是将上轮的第一个方向淘汰 上轮的新生方向补入本轮的最后而构成 d2k d3k dnk dk 4 基本算法示例 4 8鲍威尔方法 45 4 基本算法示例 4 8鲍威尔方法 46 4 基本算法示例 4 8鲍威尔方法 47 4 基本算法示例 4 8鲍威尔方法 48 4 基本算法示例 4 8鲍威尔方法 49 4 基本算法示例 4 8鲍威尔方法 50 4 基本算法示例 4 8鲍威尔方法 51 4 基本算法示例 4 8鲍威尔方法 52 4 基本算法示例 4 8鲍威尔方法 53 4 基本算法示例 4 8鲍威尔方法 54 可能在某一轮迭代中出现基本方向组为线性相关的矢量系的情况 如第k轮中 产生新的方向 dk xnk x0k 1kd1k 2kd2k nkdnk式中 d1k d2k dnk为第k轮基本方向组矢量 1k 2k nk为各方向的最优步长 若在第k轮的优化搜索过程中出现 1k 0 则方向dk表示为d2k d3k dnk的线性组合 以后的各次搜索将在降维的空间进行 无法得到n维空间的函数极小值 计算将失败 5 基本算法缺陷 4 8鲍威尔方法 55 鲍威尔基本算法的退化 x1 x2 x3 1 0 2e2 3e3 S1 如图所示为一个三维优化问题的示例 设第一轮中 1 0 则新生方向与e2 e3共面 随后的各环方向组中 各矢量必在该平面内 使搜索局限于二维空间 不能得到最优解 e2 e3 S1 5 基本算法缺陷 4 8鲍威尔方法 56 5 基本算法缺陷 4 8鲍威尔方法 57 5 基本算法缺陷 4 8鲍威尔方法 58 5 基本算法缺陷 4 8鲍威尔方法 59 5 基本算法缺陷 4 8鲍威尔方法 60 5 基本算法缺陷 4 8鲍威尔方法 61 5 基本算法缺陷 4 8鲍威尔方法 62 5 基本算法缺陷 4 8鲍威尔方法 63 5 基本算法缺陷 4 8鲍威尔方法 64 5 基本算法缺陷 4 8鲍威尔方法 65 5 基本算法缺陷 4 8鲍威尔方法 66 67 6 修正算法 4 8鲍威尔方法 根据Powell条件判定是否需换方向 如需换向 则换掉函数值下降量最大的方向 选取n个线性无关且尽可能共轭的方向作为下一轮搜索的方向组 做法 形成新的搜索方向组时 不是固定的去掉前一次搜索方向组中的第一个方向 而是首先根据Powell条件 判断原方向组是否需要替换 若需要 则进一步判断原方向组中哪个方向最坏 并以前一轮新生成的搜索方向替换本轮中的这个最坏方向 68 6 修正算法 4 8鲍威尔方法 方向组的构造 在第k轮的搜索中 x0k为初始点 搜索方向为d1k d2k dnk 产生的新方向为dk 此方向的极小点为xk 沿dk方向移动得到点xn 1k 2xnk x0k 称之为x0k对xnk的反射点 计算x0k x1k xnk xk xn 1k各点的函数值 记作 F0 F x0k F2 F xnk F3 F xn 1k F xm 1k F xmk 是第k轮方向组中 依次沿各方向搜索函数下降值 鲍威尔算法的方向淘汰 6 修正算法 4 8鲍威尔方法 69 为了构造第k 1轮基本方向组 采用如下判别式 按照以下两种情况处理 1 上式中至少一个不等式不成立 则第k 1轮的基本方向仍用老方向组d1k d2k dnk k 1轮的初始点取x0k 1 xnkF2 F3x0k 1 xn 1kF2 F3 6 修正算法 4 8鲍威尔方法 70 2 两式均成立 则淘汰函数值下降最大的方向 并用第k轮的新生方向补入k 1轮基本方向组的最后 即k 1轮的方向组为d1k d2k dm 1k dm 1k dnk dk k 1轮的初始点取 x0k 1 xk xk是第k轮沿dk方向搜索的极小点 6 修正算法 4 8鲍威尔方法 dk方向极小点 71 Powell算法的步骤如下 任选初始迭代点 选定迭代精度 取初始基本方向组为单位坐标矢量系 其中 i 1 2 n然后令k 1 轮数 开始迭代 沿诸方向依次进行n次一维搜索 确定各步长 7 修正算法步骤 4 8鲍威尔方法 72 得到点阵i 1 2 n 构成新生方向 沿方向进行一维搜索求得优化步长 3 计算各迭代点的函数值 找出相邻点函数值差最大者 1 m n 及与之相对应的两个点和 并以表示两点的连线方向 7 修正算法步骤 4 8鲍威尔方法 73 4 反射点函数值 5 判断是否满足迭代终止条件 则可结束迭代 最优解为 停止计算 否则 继续进行下步 7 修正算法步骤 4 8鲍威尔方法 74 检验鲍威尔判别条件是否成立 若至少其中之一不成立转下步 否则转步骤 确定k 1轮的基本方向组和起始点 即取老方向组 当F2 F3 当F2 F3 令k k 1 返回步骤 7 修正算法步骤 4 8鲍威尔方法 75 确定k 1轮的方向组和起始点 令k k 1 返回步骤 7 修正算法步骤 4 8鲍威尔方法 76 77 例用鲍威尔法求函数的极小值 解 选取初始点 初始搜索方向 初始点处的函数值 第一轮迭代 1 沿 方向进行一维搜索 得 其中 为一维搜索最佳步长 应满足 得 所以 8 算例 4 8鲍威尔方法 78 2 再沿 方向进行一维搜索 得 其中 为一维搜索最佳步长 应满足 得 所以 取沿 搜索的函数值增量的最大者 终点 的反射点和函数值为 8 算例 4 8鲍威尔方法 79 3 Powell条件判断 F3 F0 不满足判别条件 因而下轮迭代应继续使用原来的搜索方向e1 e2 因为F2 F3 所以取 为下轮迭代起始点 第二轮迭代 1 沿 方向进行一维搜索 得 其中 为一维搜索最佳步长 应满足 得 所以 8 算例 4 8鲍威尔方法 80 2 再沿 方向进行一维搜索 得 其中 为一维搜索最佳步长 应满足 得 所以 取沿 搜索的函数值增量的最大者 终点 的反射点和函数值为 8 算例 4 8鲍威尔方法 81 3 Powell条件判断 满足 用新方向 替换 下轮搜索方向为 下轮起始点为从出发 沿搜索的极小点 其中 为一维搜索最佳步长 应满足 得 已足够接近极值点 2 52 5 T 8 算例 4 8鲍威尔方法 82 单形替换法是利用对简单几何图形各顶点的目标函数值作相互比较 在连续改变几何图形的过程中 逐步以目标函数值较小的顶点取代目标函数值最大的顶点 从而进行求优的一种方法 属于直接法之一 1 基本原理 4 9单型替换法 现以求二元函数的极小点为例 说明单形替换法形成原理 设二元函数在平面上取不在同一条直线上的三个点 和 并以它们为顶点构成一单纯形 三角形 算出各顶点的函数值 比较其大小 现假定比较后有这说明点最差 点最好 点次差 为了寻找极小点 一般来说应向最差点的反对称方向进行搜索 83 1 基本原理 4 9单型替换法 以记为的中点 如图所示 在的延长线上取点 使称为是关于的反射点 算出的函数值 可能出现以下几种情形 1 这说明搜索方向正确 可进一步扩大效果 继续沿向前搜索 也就是向前扩张 这时取其中为扩张因子 一般取 如果 说明扩张有利 就可以点代替点构成新的单纯形 如果 说明扩张不利 舍去点 仍以点代替构成新的单纯形 1 基本原理 4 9单型替换法 84 2 这说明搜索方向正确 但无须扩张 以代替构成新的单纯形 3 这表示点走得太远 应缩回一些 若以表示压缩因子 则有常取为0 5 以代替构成新的单纯形 1 基本原理 4 9单型替换法 85 4 这时应压缩更多一些 将新点压缩至之间 令 1 基本原理 4 9单型替换法 86 如果 则以代替构成新的单纯形 否则认为方向上的所有点的函数值都大于 不能沿此方向搜索 这时 可以以为中心进行缩边 使顶点和向移近一半距离 得新单纯形 以此单纯形为基础再进行寻优 2 比较各顶点Xi的函数值 挑出其中的最优点 记为XL 最劣点 记XH 次差点 记为Xw 3 求反射中心 其中 a 0 通常取a 1 输出XL 为原问题近似极小点 否则 转 2 5 如果满足 2 计算步骤 4 9单型替换法 87 例试用单型替换求的极小值 解 选 并取和 这三点不在一条直线上 用它们作为初始单纯形的顶点 如图所示 3 算例 4 9单型替换法 88 然后计算各顶点的函数值