工程最优化第四章.ppt

第四章单变量函数的最优化方法 搜索区间的确定黄金分割法二次插值法Newton Raphson法 要点 单峰函数的消去性质 进退算法基本思想 黄金分割法基本思想 重新开始 二次插值法要求 极小化架子 Newton Raphson法基本思想 方法比较 学习的重要性 1 工程实践中有时需要直接使用 2 多变量最优化的基础 迭代中经常要用到 方法分类 1 直接法 迭代过程中只需要计算函数值 2 间接法或微分法 迭代过程中还需要计算目标函数的导数 4 1搜索区间的确定 常用的一维直接法有消去法和近似法两类 它们都是从某个初始搜索区间出发 利用单峰函数的消去性质 逐步缩小搜索区间 直到满足精度要求为止 4 1 1单峰函数 定义 如果函数f x 在区间 a b 上只有一个极值点 则称f x 为 a b 上的单峰函数 连续单峰函数 不连续单峰函数 离散单峰函数 非单峰函数 单峰函数具有一个重要的消去性质 定理 设f x 是区间 a b 上的一个单峰函数 x a b 是其极小点 x1和x2是 a b 上的任意两点 且a x1 x2 b 那么比较f x1 与f x2 的值后 可得出如下结论 I 消去 a x1 II 消去 x2 b II 若f x1 f x2 x a x2 在单峰函数的区间内 计算两个点的函数值 比较大小后 就能把搜索区间缩小 在已缩小的区间内 仍含有一个函数值 如再计算另一点的函数值 比较后就可进一步缩小搜索区间 I 若f x1 f x2 x x1 b 4 1 2进退算法 如何确定包含极小点在内的初始区间 一 基本思想 由单峰函数的性质可知 函数值在极小点左边严格下降 在右边严格上升 从某个初始点出发 沿函数值下降的方向前进 直至发现函数值上升为止 由两边高 中间低的三点 可确定极小点所在的初始区间 二 算法 1 选定初始点a和步长h 2 计算并比较f a 和f a h 有前进 1 和后退 2 两种情况 则步长加倍 计算f a 3h 若f a h f a 3h 令a1 a b1 a 3h 停止运算 否则将步长加倍 并重复上述运算 则将步长改为 h 计算f a h 若f a h f a 令a1 a h b1 a h 停止运算 否则将步长加倍 继续后退 三 几点说明 P87 4 2区间消去法 黄金分割法 消去法的思想 反复使用单峰函数的消去性质 不断缩小包含极小点的搜索区间 直到满足精度为止 消去法的优点 只需计算函数值 通用性强 消去法的设计原则 1 迭代公式简单 2 消去效率高 一 黄金分割 取 0 61803398874189 二 黄金分割法的基本思想 黄金分割重要的消去性质 设x1 x2为 a b 中对称的两个黄金分割点 x1为 a x2 的黄金分割点 x2为 x1 b 的黄金分割点 在进行区间消去时 不管是消去 a x1 还是消去 x2 b 留下来的区间中还含一个黄金分割点 只要在对称位置找另一个黄金分割点 又可以进行下一次区间消去 每次消去后 新区间的长度约为原区间的0 618倍 经过n次消去后 保留下来的区间长度为0 618nL 需计算函数值的次数为n 1 黄金分割比 0 618 所以此法也称为0 618法 三 算法 开始 x a x2 x x1 b 在迭代过程中 四个点的顺序始终应该是a x1 x2 b 但在计算第二个分割点时使用x1 a b x2或x2 a b x1 由于舍入误差的影响 可能破坏a x1 x2 b这一顺序 导致混乱 迭代中必须采取一些措施 1 终止限 不要取得太小 2 使用双精度运算 3 经过若干次运算后 转到算法中的第3步 重新开始 开始 b x2 x2 x1 f2 f1x1 a b x2 f1 f x1 否 在迭代过程中 四个点的顺序始终应该是a x1 x2 b 但在计算第二个分割点时使用x1 a b x2或x2 a b x1 由于舍入误差的影响 可能破坏a x1 x2 b这一顺序 导致混乱 迭代中必须采取一些措施 1 终止限 不要取得太小 2 使用双精度运算 3 经过若干次运算后 转到算法中的第3步 重新开始 例4 2 1PP89 四 黄金分割法的优缺点 2 缺点 对解析性能好的单峰函数 与后面要介绍的二次插值法 三次插值法及牛顿 拉夫森法等比较 计算量较大 收敛要慢 1 优点 算法简单 效率高 只计算函数值 对函数要求低 稳定性好 对多峰函数或强扭曲的 甚至不连续的 都有效 4 3多项式近似法 二次插值法 一 基本思想 对形式复杂的函数 数学运算时不方便 复杂函数f x 极小点x 函数近似 最优点也应近似 一次多项式二次多项式三次多项式 如何构造符合要求的多项式 二 二次插值多项式近似法 抛物线法 的基本原理 设目标函数f x 在三点x1 x2 x3上的函数值分别为f1 f2 f3 相应的二次插值多项式为P2 x a0 a1x a2x2 令P2 x 和f x 在三点上的函数值相等 三个待定系数 P2 x 的平稳点是P2 x a1 2a2x 0的解 所以只需求出a1 a2 最后得 迭代过程要点 若任意取x1 x2 x3三个点 则求出的x 可能位于给定区间之外或误差太大 最初的三个点x1 x2 x3应构成一个两边高 中间低的 极小化架子 即满足f1 f2 f3 f2 且两个等号不同时成立 极小化架子可由进退算法求得 在完成一次计算后 得到近似x 然后进行搜索区间的收缩 再在新区间中重新构造三点组成的 极小化架子 有两种方法 终止准则 采用目标函数值的相对误差或绝对误差来判断 PP91 前进成功 极小化架子x1x2x3 前进失败 x1 x2 极小化架子x3x2x1 后退 h0 2h0 4h0 h0 h0 2h0 4h0 三 进退算法 用于求 极小化架子 或初始搜索区间 四 逐次二次插值近似法的算法 初始点x1 h0 精度 1 溢出下限 2 步长缩短率m 二次插值法的优点 收敛速度较快 约为1 3阶 缺点 对强扭曲或多峰的 收敛慢 甚至会失败 故要求函数具有较好的解析性能 五 二次插值法与黄金分割法的结合 4 4要求计算导数的迭代法 如目标函数f x 可导 可通过解f x 0求平稳点 进而求出极值点 对高度非线性函数 要用逐次逼近求平稳点 4 4 1Newton Raphson法 要求目标函数f x 在搜索区间内具有二阶连续导数 且已知f x 和f x 的表达式 一 基本思想 采用迭代法求 x 0的根 xk 1 xk 2 xk xk xk 1 xk xK 1 xk xk xk 用于求 x f x 0的根 xK 1 xk f xk f xk 例题4 4 1用Newton Raphson法求解初始点取x0 1 迭代二次 解 f x 的一阶和二阶导函数为 迭代公式为xK 1 xk f xk f xk 第一次迭代 x0 1 f x0 12 f x0 36x1 1 12 36 1 33 第二次迭代 x1 1 33 f x1 3 73 f x1 17 6x2 1 33 3 73 17 6 1 54 本例精确解为x 二 优缺点 1 优点 收敛速度快 在f x 0的单根处 是二阶收敛 在f x 0的重根处 是线性收敛 2 缺点 需要求二阶导数 若用数值导数代替 由于舍入误差将影响收敛速度 收敛性还依赖于初始点及函数性质 通常在计算程序中规定最大迭代次数K 当次数达到K还不能满足精度时 则认为不收敛 可更换一个初始点再试 4 4 2对分法 假设f x 是具有极小点的单峰函数 则必存在区间 a b 使f a 0 由f x 的连续性可知 必有x a b 使f x 0 优点 总能找到最优点 缺点 要计算导数值 收敛速度为一阶 4 4 3割线法 x 基本思想 用割线代替Newton Raphson法中的切线 并与区间消去法相结合 c 新区间两端点的导数值异号 4 4 4三次插值多项式近似法 基本思想与二次插值法类似 用四个已知值 如两个点函数值及其导数值 构造一个三次多项式P3 x 用P3 x 的极小点近似目标函数的极小点x 三次插值法的收敛速度比二次插值法要