最优化课程论文-三点二次插值法.doc

四川理工学院 数学建模课程设计 论文 四川理工学院 最优化方法 课程论文 姓 名 陈晓容 专 业 统计 班 级 1 班 学 号 11071050130 完成日期 2014 6 25 四川理工学院 最优化方法 课程论文 无约束最优化方法无约束最优化方法 三点二次插值法三点二次插值法 摘摘 要要 在生产过程 科学实验以及日常生活中 人们总希望用最少的人力 物力 财力 和时间去办更多的事 获得最大的效益 在管理学中被看作是生产者的利润最大化和 消费者的效用最大化 如果从数学的角度来看就被看作是 最优化问题 最优化问题 分为无约束最优化和约束最优化 本文主要拟就无约束最优化进行分析 无约束最优化计算方法是数值计算领域中十分活跃的研究课题之一 快速的求解 无约束最优化问题 除了自身的重要性以外 还体现在它也构成一些约束最优化问题 的子问题 因此 对于无约束最优化问题 如何快速有效的求解一直是优化工作者十 分关心的事 本文研究求解无约束最优化问题的精确线性搜索方法 三点二次插值 法 并且讨论了这种方法的优缺点以及适用范围 同时论文中对这种方法给出了具体 实例 并对例子进行了 matlab 软件实现 关键词关键词 三点二次插值法 插值多项式 目标函数 目目 录录 一 问题的提出 3 二 设计思路和步骤 3 3 1 设计思路 3 3 2 设计步骤 3 三 程序设计 5 3 1 问题分析 5 3 2 算法设计 5 3 3 算法框图 5 3 4 程序编制 7 四 结果分析 8 四 结果分析 3 1 理论结果 8 3 2 编程结果 9 五 收获提高 11 5 1 设计的优缺点 11 5 2 收获与启发 11 参考文献 11 一 问题的提出 用精确线性搜索方法求 23min 3 0 的近似最优解 精确极小点为 1 设已确定其初始搜索区间为 0 3 取初始插值点 为 2 终止误差 0 05 0 二 设计思路和步骤 2 1 设计思路 在求解一元函数的极小点时 在搜索区间中用低次 通常不超过三次 插值 多项式来近似目标函数 后求该多项式的极小点 比较容易计算 并以此作为目 q 标函数的近似极小点 如果其近似的程度尚未达到所要求的精度时 反复使用此 法 逐次拟合 直到满足给定的精度时为止 2 2 设计步骤 考虑二次多项式 cbaq 2 则 baq 2 四川理工学院 最优化方法 课程论文 令 得 这意味着我们要求 a b 0 q a b 2 今考虑在包含的极小点的搜索区间中 给定三个点 00 b a 1 2 3 满足 时 221 2 2 或者如果 当 时 21 2 2 则我们认为收敛准则满足 如果 则转步 3 否则转步 4 2 2 步 3 如果 则 2 21 221 2 转步 5 否则 转步 5 3 3 步 4 若 则 2 23 223 2 转步 5 否则 转步 5 1 1 步 5 如果收敛准则满足 停止迭代 否则转步 1 在新的搜索区间 上 1 3 按公式计算二次插值函数的极小点 3 3 算法框图 其中 13 13 1 c 12 11212 2 c c 2121 cc 5 0 四川理工学院 最优化方法 课程论文 3 4 程序编制 function eccz syms x 定义 22 是 2 2 否 0 h 2 0 05 精度 f1 subs f x a1 f2 subs f x a2 f3 subs f x a3 C1 f3 f1 a3 a1 C2 f2 f1 a2 a1 C1 a2 a3 ap 0 5 a1 a3 C1 C2 fp subs f x ap if ap a2 if f2 fp a1 a2 f1 f2 a2 ap f2 fp else a3 ap f3 fp end else if f2 fp a3 a2 f3 f2 a2 ap f2 fp else a1 ap 四川理工学院 最优化方法 课程论文 f1 fp end end k k 1 a ap ff subs f x ap end 4 结果分析 4 1 理论结果 0 2 3 0 a 0 0 b 第一次迭代 2 4 20 0 a 0 0 b 代入公式求得 0 9 由于 故继续迭代 令 0 0 0 9 2 1 a 0 a 1 1 b 0 b 第二次迭代 2 0 029 4 1 a 1 1 b 带入公式求得 0 82759 由于 故继续迭代 令 1 0 82759 0 9 2 2 a 2 1 2 b 1 b 第三次迭代 0 08405 0 029 4 2 a 2 2 b 代入公式求得 0 96577 由于 和 2 0 00347 0 029 2 并且 0 06577 故继续迭代 令 2 0 9 0 96557 2 3 a 2 3 3 b 2 b 第四次迭代 0 029 0 00347 4 3 a 3 3 b 代入公式求得 0 98308 由于 和 3 0 000854 0 00347 3 并且 0 01731 故停止迭代 输出近似最优解 0 98308 3 4 2 编程结果 将程序输入 matlab 运行后得如下结果 四川理工学院 最优化方法 课程论文 四 结果分析 从运行结果可以看出 经过四次迭代 结果已经满足精度要求 故停止迭代 得出最 优解为 0 9831 与理论结果相符 五 总结提高 5 1 设计的优缺点 优点 插值法仅需计算函数值 不涉及导数 hesse 矩阵等的计算 计算起来相对 比较简单 能够适用于非光滑和导数表达式复杂或表达式写不出等种种情形 缺点 当迭代步数较多时 计算过程比较复杂 计算量较大 计算起来比较麻烦 当迭代点离目标函数的最优解较远时 追求线性搜索的精度反而会降低整个算法的效 率 5 2 收获与启发 通过对此次课程论文的撰写 使我进一步了解了逐次插值逼近法 三点二次插 值法的原理及方法 能够运用 matlab 对算法进行实现 并能从中分析出每一次迭代的 结果 迭代的次数 最终结果等 同时在平时学习的基础上进一步巩固了手工计算的 方法及步骤 能够快速准确地在题中所给精度范围内计算出最优解 三点二次插值法是精确性线性搜索中一种较好的方法 但是会存在迭代点离目标 函数最优解较远时 过分追求精度反而降低了整个算法效率的问题 因此在工作中我 们可以选择一些放松对精度要求的方法 只要求目标函数在迭代的每一步有充分的 k 下降即可 这就涉及到收敛速度不依赖于精度的一些一维搜索