工程优化设计中的数学方法硕士研究生西安电子.ppt

3 1搜索算法结构 一 下降算法模型考虑 fs 常用一种线性搜索的方式来求解 迭代中从一点出发沿下降可行方向找一个新的 性质有改善的点 迭代计算 其中为第次迭代的搜索方向 为沿搜索的最佳步长因子 通常也称作最佳步长 第三章常用的一维搜索方法 可行方向 设 S d Rn d 0 若存在 使 称d为点的可行方向 同时满足上述两个性质的方向称下降可行方向 下降方向 设 S d Rn d 0 若存在 使 称d为在点的下降方向 模型算法 线性搜索求 新点使x k 1 S yes no 5 3 1 二 收敛性概念 考虑 fs 设迭代算法产生点列 x k S 1 理想的收敛性 设x S是g opt 全局最优解 当x x k 或x k x k 满足时 称算法收敛到最优解x 由于非线性规划问题的复杂性 实用中建立下列收敛性概念 2 实用收敛性 定义解集S x x具有某种性质 例 S x x g opt S x x l opt S x f x 0 S x f x 为给定的实数 称为阈值 2 实用收敛性 续 收敛性 设解集S x k 为算法产生的点列 下列情况之一成立时 称算法收敛 1 x k S 2 x k S k x k 的任意极限点 S 全局收敛 对任意初始点x 1 算法均收敛 局部收敛 当x 1 充分接近解x 时 算法收敛 有限步终止 三 收敛速度设算法产生点列 x k 收敛到解x 且x k x k 关于算法的收敛速度 有1 线性收敛 当k充分大时成立 2 超线性收敛 3 二阶收敛 0 是使当k充分大时有 三 收敛速度 续 定理 设算法点列 x k 超线性收敛于x 且x k x k 那么证明 只需注意 x k 1 x x k x x k 1 x k x k 1 x x k x 除以 x k x 并令k 利用超线性收敛定义可得结果 该结论导出算法的停止条件可用 四 二次终结性 一个算法用于解正定二次函数的无约束极小时 有限步迭代可达最优解 则称该算法具有二次终结性 问题描述 已知 并且求出了 处的可行下降方向 从 出发 沿方向 求如下目标函数的最优解 或者选取 使得 常用的一维搜索算法 设其最优解为 叫精确步长因子 所以线性搜索是求解一元函数 的最优化问 题 也叫一维最优化问题或 一般地 一维优化问题可描述为 于是得到一个新点 一维搜索 或解 一般地 线性搜索算法分成两个阶段 第一阶段确定包含理想的步长因子 或问题最优解 的搜索区间 第二阶段采用某种分割技术或插值 方法缩小这个区间 搜索区间的确定黄金分割法 0 618法 二次插值法Newton法 要点 单峰函数的消去性质 进退算法基本思想 黄金分割法基本思想 重新开始 二次插值法要求 极小化框架 Newton法基本思想 方法比较 我们主要介绍如下一些搜索方法 学习的重要性 1 工程实践中有时需要直接使用 2 多变量最优化的基础 迭代中经常要用到 方法分类 1 直接法 迭代过程中只需要计算函数值 2 微分法 迭代过程中还需要计算目标函数的导数 3 2搜索区间的确定 常用的一维直接法有消去法和近似法两类 它们都是从某个初始搜索区间出发 利用单峰函数的消去性质 逐步缩小搜索区间 直到满足精度要求为止 3 2 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 3 2 2进退算法 或称成功 失败法 如何确定包含极小点在内的初始区间 一 基本思想 由单峰函数的性质可知 函数值在极小点左边严格下降 在右边严格上升 从某个初始点出发 沿函数值下降的方向前进 直至发现函数值上升为止 由两边高 中间低的三点 可确定极小点所在的初始区间 二 算法 1 选定初始点a和步长h 2 计算并比较f a 和f a h 有前进 1 和后退 2 两种情况 则步长加倍 计算f a 3h 若f a h f a 3h 令a1 a a2 a 3h 停止运算 否则将步长加倍 并重复上述运算 则将步长改为 h 计算f a h 若f a h f a 令a1 a h a2 a h 停止运算 否则将步长加倍 继续后退 仅仅找区间 若进一步找最小点 参阅P44 三 几点说明缺点 效率低 优点 可以求搜索区间 注意 h选择要适当 初始步长不能选得太小 3 3区间消去法 黄金分割法 消去法的思想 反复使用单峰函数的消去性质 不断缩小包含极小点的搜索区间 直到满足精度为止 消去法的优点 只需计算函数值 通用性强 消去法的设计原则 1 迭代公式简单 2 消去效率高 3 对称 x1 a b x2 4 保持缩减比 保留的区间长度 原区间长度 不变 使每次保留下来的节点 x1或x2 在下一次的比较中成为一个相应比例位置的节点 一 黄金分割 取 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步 重新开始 四 黄金分割法的优缺点 2 缺点 对解析性能好的单峰函数 与后面要介绍的二次插值法 三次插值法及牛顿 拉夫森法等比较 计算量较大 收敛要慢 1 优点 算法简单 效率高 只计算函数值 对函数要求低 稳定性好 对多峰函数或强扭曲的 甚至不连续的 都有效 f x x2 a 1 5 b 1 精度10 5 ax1x2b 3 6034e 0052 9804e 0062 7093e 0056 6107e 005220 6180340 618034 x1 a x2 a b x2 b x1 3 6034e 005 1 1922e 0052 9804e 0062 7093e 005230 6180340 618034 1 1922e 0052 9804e 0061 219e 0052 7093e 005240 6180350 618035 1 1922e 005 2 7117e 0062 9804e 0061 219e 005250 6180320 618032 1 1922e 005 6 2296e 006 2 7117e 0062 9804e 006260 6180380 618038x 2 7117e 006 若用0 618效果较差 f x x2 a 1 5 b 1 精度10 10 ax1x2b 2 1976e 007 9 7339e 008 2 4483e 0089 7933e 008340 6269020 626902 9 7339e 008 2 4483e 0082 5078e 0089 7933e 008350 5951450 595145 9 7339e 008 4 7778e 008 2 4483e 0082 5078e 008360 6802640 680264 4 7778e 008 2 4483e 0081 7832e 0092 5078e 008370 4700170 470017 2 4483e 0081 7832e 009 1 1888e 0092 5078e 008381 127581 12758 x1 a x2 a b x2 b x1 1 7832e 009 1 1888e 0092 805e 0082 5078e 00839 0 113146 0 1131461 7832e 0093 1022e 008 1 1888e 0092 805e 008 9 83816 9 83816x 1 1888e 009 不满足精度 若用0 618效果更差 f x x2 a 1 5 b 1 精度10 10重新开始 ax1x2b 7 8811e 0101 9703e 0108 0587e 0101 791e 009440 6180340 618034 x1 a x2 a b x2 b x1 7 8811e 010 1 7926e 0101 9703e 0108 0587e 010450 6180340 618034 7 8811e 010 4 1182e 010 1 7926e 0101 9703e 010460 6180340 618034 4 1182e 010 1 7926e 010 3 5532e 0111 9703e 010470 6180340 618034 1 7926e 010 3 5532e 0115 3298e 0111 9703e 010480 6180340 618034 1 7926e 010 9 0432e 011 3 5532e 0115 3298e 011490 6180340 618034 9 0432e 011 3 5532e 011 1 6019e 0125 3298e 011500 6180340 618034x 1 6019e 012 满足要求 设f x 在 a b 上可微 且当导数为零时是解 取x a b 2 那么f x 0时 x为最小点 x x f x 0时 x在上升段 x x 去掉 a x 自己画算法框图 3 4二分法 a b 缩小 当区间 a b 的长度充分小时 或者当充分小时 即可将 a b 的中点取做极小点的近似点 这时有估计 我们知道 在极小点 处 且 时 递减 即 而当 函数递增 即 若找到一个区间 a b 满足性质 则 a b 内必有 的极小点 且 为找此 取 若 则在 中有极小点 这时 用 作为新的区间 a b 继续这个过程 逐步将区间 假设f x 是具有极小点的单峰函数 则必存在区间 a b 使f a 0 由f x 的连续性可知 必有x a b 使f x 0 优点 计算量较少 总能找到最优点 缺点 要计算导数值 收敛速度较慢 收敛速度为一阶 其中区间 a b 的确定 一般可采用 进退法 3 5多项式近似法 二次插值法 一 基本思想 对形式复杂的函数 数学运算时不方便 复杂函数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 最后得 其他插值公式参阅P51 52 2 4 三点二次插值公式最常用 迭代过程要点 若任意取x1 x2 x3三个点 则求出的x 可能位于给定区间之外或误差太大 最初的三个点x1 x2 x3应构成一个两边高 中间低的 极小化框架 即满足f1 f2 f3 f2 且两个等号不同时成立 极小化框架可由进退算法求得 在完成一次计算后 得到近似x 要进行搜索区间的收缩 然后在新区间中重新构造三点组成的 极小化框架 有两种方法 终止准则 采用目标函数值的相对误差或绝对误差来判断 前进成功 极小化框架x1x2x3 前进失败 x1 x2 极小化框架x3x2x1 后退 h0 2h0 4h0 h0 h0 2h0 4h0 三 进退算法 用于求 极小化框架 或初始搜索区间 四 逐次二次插值近似法的算法 初始点x1 h0 精度 1 溢出下限 2 步长缩短率m 二次插值法的优点 收敛速度较快 约为1 32阶 缺点 对强扭曲或多峰的 收敛慢 甚至会失败 故要求函数具有较好的解析性能 五 二次插值法与黄金分割法的结合 2 用二次插值法逼近极小点相邻三点的函数值 x1 0 x2 1 x3 2 f1 2 f2 1 f3 18 代入公式 xp 0 555 fp 0 292 例3 3用二次插值法求函数f x 3x3 4x 2的极小点 给定x0 0 h 1 0 2 解1 确定初始区间初始区间 a b 0 2 另有一中间点x2 1 在新区间 相邻三点的函数值 x1 0 x2 0 555 x3 1 f1 2 f2 0 292 f3 1 xp 0 607 fp 0 243由于fpx2 新区间 a b x2 b 0 555 1 x2 xp 0 555 0 607 0 052 0 2 迭代终止 xp 0 607 f 0 243 由于fp0 2 应继续迭代 此例黄金分割法需要5次收缩区间 例 例3 4用二次插值法求的极值点 初始搜索区间 图 解 取x2点为区间 x1 x3 的中点 计算x1 x2 x33点处的函数值f1 19 f2 96 9375 f3 124 可见函数值满足 高 低 高 形态 以x1 x2 x3为插值点构造二次曲线 求第一次近似的二次曲线p x 的极小值点 由公式得 比较函数值可知这种情况应消除左边区段 然后用作为x1 x2 x3新3点 重新构造二次曲线p x 如此反复计算 直到为止 整个迭代过程的计算结果列于表2 2 从表中可见 经7次迭代后 终止迭代 故最优点 要求计算导数的插值法 若目标函数f x 可导 可通过解f x 0求平稳点 进而求出极值点 对高度非线性函数 要用逐次逼近求平稳点 一 Newton法 要求目标函数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 0 一点二次插值 牛顿法程序流程 例题用Newton法求解初始点取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 第三次迭代 x2 1 54 f x2 0 5865 f x1 12 76x2 1 54 0 587 12 76 1 586 例1 求minf x arctantdt解 f x arctanx f x 1 1 x2 迭代公式 xk 1 xk 1 xk2 arctanxk取x1 1 计算结果 kxkf xk 1 f xk 110 785422 0 5708 0 51871 325830 1169 0 11641 01374 0 001095 0 00109557 9631e 010 x4 x 0取x1 2 计算结果如下 2 3 5357 13 9510 279 3441 1 2202e 005 不收敛 二 优缺点 1 优点 收敛速度快 在f x 0的单根处 是2阶收敛 在f x 0的重根处 是线性收敛 2 缺点 需要求二阶导数 若用数值导数代替 由于舍入误差将影响收敛速度 收敛性还依赖于初始点及函数性质 通常在计算程序中规定最大迭代次数 当次数达到K还不能满足精度时 则认为不收敛 要换一个初始点 二 二点二次插值 x 1 割线法 基本思想 用割线代替Newton法中的切线 并与区间消去法相结合 c P52 3 14 P51 3 12 2 另一个二点二次插值 较割线法稍好 收敛速度都为1 618阶 通过检查区间两端导数来收缩区间 新区间两端点的导数值异号 基本思想与二次插值法类似 用四个已知值 如两个点函数值及其导数值 构造一个三次多项式P3 x 用P3 x 的极小点近似目标函数的极小点x 利用函数在两点的函数值和导数值 三 三次插值 三次插值法的收敛速度比二次插值法要快 达到2阶收敛速度 求出 极值的条件 极值充分条件为 将极值点方程带入上式 仅取正号 二点三次插值法一般流程 编写程序应用时建议结合教材框图编写 其更具普适性 鲁棒性 教材P56 58的D S C 法 Powell法及其组合法是区间搜索一二次插值法的结合 P59 P64介绍了有理插值 连分式方法属特殊方法 含教材作者的一些研究成果 大家参阅教材 注意其适应条件 必要时课选用 方法综述 1 如目标函数能求二阶导数 用Newton法收敛快 2 如目标函数能求一阶导数 首先考虑用三次插值法 收敛较快对分法 收敛速度慢 但可靠二次插值如割线法也可选择 3 只需计算函数值的方法 首先考虑用二次插值法 收敛快黄金分割法收敛速度较慢 但可靠 作业 一 用黄金分割法求函数f x 3x4 4x2 2的极小点 给定x0 2 h 1 0 1 x0 2 h 1 0 1 二 ch33 13 7 9课件见 解 1 确定初始区间x1 x0 0 f1 f x1 2x2 x0 h 0 1 1 f2 f x2 1由于f1 f2 应加大步长继续向前探测 x3 x0 2h 0 2 2 f3 f x3 18由于f2 f3 可知初始区间已经找到 即 a b x1 x2 0 2 2 用黄金分割法缩小区间第一次缩小区间 x1 0 0 382X 2 0 0 764 f1 0 282x2 0 0 618X 2 0 1 236 f2 2 72f10 2 例3 1用黄金分割法求函数f x 3x3 4x 2的极小点 给定x0 0 h 1 0 2 第三次缩小区间 令x1 x2 0 764 f1 f2 0 282x2 0 472 0 618X 1 236 0 472 0 944 f2 0 747由于f10 2 应继续缩小区间 第二次缩小区间 令x2 x1 0 764 f2 f1 0 282x1 0 0 382X 1 236 0 0 472 f1 0 317由于f1 f2 故新区间 a b x1 b 0 472 1 236 因为b a 1 236 0 472 0 764 0 2 应继续缩小区间 第四次缩小区间 令x2 x1 0 764 f2 f1 0 282x1 0 472 0 382X 0 944 0 472 0 652 f1 0 223由于f10 2 应继续缩小区间 第五次缩小区间 令x2 x1 0 652 f2 f1 0 223x1 0 472 0 382X 0 764 0 472 0 584 f1 0 262由于f1 f2 故新区间 a b x1 b 0 584 0 764 因为b a 0 764 0 584 0 18 0 2 停止迭代 极小点与极小值 x 0 5X 0 584 0 764 0 674 f x 0 222 返回