机械优化设计无约束方法PPT课件.ppt

2020 3 21 1 第四章无约束优化方法 2 坐标轮换法 3 鲍威尔法 4 梯度法 5 共轭梯度法 6 牛顿法 1 概述 7 DFP变尺度法 长江大学机械工程学院 HQS 2020 3 21 2 一 解法分类1 直接法其搜索方向直接取定或由计算目标函数值所得的信息来确定 2 间接法 解析法 确定搜索方向时用到一阶或 和 二阶导数的方法 二 研究无约束优化方法的意义1 是约束优化方法的基础 2 可用于非线性方程组的求解 4 1概述 长江大学机械工程学院 HQS 2020 3 21 3 4 2坐标轮换法 1 几何描述 以二维问题为例 二 迭代步骤 依次沿个n个正交坐标轴的方向搜索 一 搜索方向 长江大学机械工程学院 HQS 2020 3 21 4 2 坐标轮换法流程图 给定 长江大学机械工程学院 HQS 2020 3 21 5 三 算法特点 如 1 等值线为椭圆 且长短轴分别平行于坐标轴时 高效 2 等值线为如图脊线时 无效 3 一般情况 低效 1 编程简单 容易掌握 2 收敛速度通常较低 其有效性取决于目标函数的性态 仅适于低维的情况 长江大学机械工程学院 HQS 2020 3 21 6 长江大学机械工程学院 HQS 2020 3 21 7 4 3Powell法 3 若目标函数为正定二次函数 n轮结束后即可到达最优点 2 每轮迭代产生一个新方向取代原来的第一方向 n轮迭代后可产生n个彼此共轭的方向 1 开始采用坐标轴方向 一 Powell基本算法 长江大学机械工程学院 HQS 2020 3 21 8 二 Powell法 Powell修正算法 应用Powell基本算法时 若有一次搜索的最优步长为0 且该方向被换掉 则该算法失效 1 问题的提出 长江大学机械工程学院 HQS 2020 3 21 9 2 Powell对基本算法的改进在获得新方向构成新方向组时 不是轮换地去掉原来的方向 而是经判别后 在n 1个方向中留下最接近共轭的n个方向 根据Powell条件判定是否需换方向 如需换向 则换掉函数值下降量最大的方向 长江大学机械工程学院 HQS 2020 3 21 10 三 Powell条件 如下述两不等式同时成立则需换向 否则仍取原方向组 计算 映射计算 长江大学机械工程学院 HQS 2020 3 21 11 四 更换方向的步骤 3 更换方向 2 构造新方向 1 找出该轮迭代中目标函数值下降量最大的方向 假定其标号为m 长江大学机械工程学院 HQS 2020 3 21 12 Powell修正算法 F3 F1 Q D Si Si 1i m m 1 n i n K K 1 长江大学机械工程学院 HQS 2020 3 21 13 例 用Powell法求的最优解 初始点 31 T 0 0001 解 长江大学机械工程学院 HQS 2020 3 21 14 4 4梯度法 可取最优步长或下降步长 一 基本思想 2 迭代公式 1 沿负梯度方向搜索 二 终止判别条件 gradient 梯度 前后两个方向正交 长江大学机械工程学院 HQS 2020 3 21 15 从出发 沿搜索得 最速下降性 只是迭代点邻域的局部性质 从全局看 并非最速下降方向 三 迭代步骤 长江大学机械工程学院 HQS 2020 3 21 16 长江大学机械工程学院 HQS 2020 3 21 17 4 5共轭梯度法 下一方向 当前方向 二 共轭方向的构成 利于突破函数的非二次性 每轮搜索方向为一组共轭方向 但第一方向为负梯度方向 一 基本思路 可表示为和的线性组合 长江大学机械工程学院 HQS 2020 3 21 18 因而 因为 A是目标函数的Hessian矩阵 故有 故有 当前后两个梯度正交时 长江大学机械工程学院 HQS 2020 3 21 19 长江大学机械工程学院 HQS 2020 3 21 20 关于前后两个梯度正交的证明 1 当k 1时 2 当k 1时 3 0 长江大学机械工程学院 HQS 2020 3 21 21 k n 重置负梯度方向 三 迭代步骤 长江大学机械工程学院 HQS 2020 3 21 22 四 共轭梯度法的特点 1 为共轭方向法 具有二次收敛性 2 算法简单 编程容易 存储量小 3 需用到一阶导数 长江大学机械工程学院 HQS 2020 3 21 23 长江大学机械工程学院 HQS 2020 3 21 24 4 6牛顿法 鲍威尔法需迭代 n 1 n次才能到达二次函数的极小点 共轭梯度法则需迭代n次 能否更快到达二次函数的极小点 一 原始牛顿法 一 基本思路用目标函数的近似二次函数的极小点来近似原函数的极小点 长江大学机械工程学院 HQS 2020 3 21 25 二 原始牛顿法的迭代公式 令 长江大学机械工程学院 HQS 2020 3 21 26 长江大学机械工程学院 HQS 2020 3 21 27 矩阵求逆的方法 伴随矩阵 行列式 例 长江大学机械工程学院 HQS 2020 3 21 28 二 阻尼牛顿法 具有二次收敛性 但用到二阶导数矩阵求逆 仍取牛顿方向 但改用最优步长因子 因F X 不一定是二次函数 基本牛顿法的步长因子恒为1 有时会导致迭代发散而失效 1 问题的提出 2 改进方法 在Hk正定时可保证收敛性 长江大学机械工程学院 HQS 2020 3 21 29 3 阻尼牛顿法的迭代步骤 由出发 沿方向搜索得 长江大学机械工程学院 HQS 2020 3 21 30 4 7DFP变尺度法 能否克服各自的缺点 综合发挥其优点 2 阻尼牛顿法 1 梯度法 一 问题的提出 由Davidan Fletcher Powell共同提出 简单 开始时目标函数值下降较快 但越来越慢 目标函数值在最优点附近时收敛快 但要用到二阶导数和矩阵求逆 长江大学机械工程学院 HQS 2020 3 21 31 二 基本思路 2 迭代终了 具有二阶收敛性 1 当和梯度法一样 便于突破函数的非二次性 式中 1 Ak 构造矩阵 在迭代中产生 不用求导和作矩阵求逆 迭代公式 长江大学机械工程学院 HQS 2020 3 21 32 三 构造矩阵应满足的条件 1 应为正定对称矩阵 1 应为对称矩阵 E和均为对称矩阵 2 应为正定矩阵 因为应使为函数下降方向 即与的夹角应小于900 二次型正定 长江大学机械工程学院 HQS 2020 3 21 33 2 应能逼近 以近似二次函数的梯度作为下一迭代点处的梯度 其梯度 用代替 得 长江大学机械工程学院 HQS 2020 3 21 34 四 的构造方法 用递推方法构造 于是有 关键是确定 1 再令 2 代入 1 两边对比得 回代到 2 得 3 长江大学机械工程学院 HQS 2020 3 21 35 五 迭代步骤 长江大学机械工程学院 HQS 2020 3 21 36 4 8无约束优化方法的评价准