第三章 一维搜索法.ppt

第三章一维搜索法 求目标函数极值的方法和函数极值点存在的条件 都离不开求目标函数的一 二阶导数或偏导数 但有时函数的导数不易求得 甚至根本就不存在 这时 上述方法就无法应用 直接探索 或称搜索 方法就是在这神情况下形成与发展起来的 并且在工程实践中得到了广泛应用 对于单个变量 一维问题 的直接探索 通常称为一维探索 或一维搜索 寻查 或线性探索 它是一维最优化问题的常用方法 第三章一维搜索法 求多维目标函数的极值问题 可以处理为从选定的初始点出发 沿着某一使函数值下降的待定方向求出目标函数在此方向上的极值点 然后再从点出发沿使目标函数值继续下降的另一个特定方向求目标函数新的极值点 如此逐步迭代下去 直到满足迭代终止判据并求出近似的最优解为止 第三章一维搜索法 以上每一步的格式都是从某一定点出发 沿着某一使函数值下降的规定方向找出在此方向的极值点 这一过程是最优化方法中的一种基本过程 在此过程中因出发点探索方向均暂时为定值 因此 为了使目标函数值为最小 只要找到合适的步长就可以了 也就是说 在任何一次迭代计算过程中 当起步点和方向确定之后 就把求多维目标函数的极小值这个多维问题 变成求一个变量即步长的最优值的一维问题了 即 min 第三章一维搜索法 一维优化需要解决两个方面的问题 1 确定极小点存在的区间 即搜索区间 初始区间 进退法 或叫外推法 2 在搜索区间上寻优 试探法 黄金分割法 插值法 抛物线法 第三章一维搜索法 由单谷函数的性质可知 在极小点左边函数值应一直下降 而在极小点右边则函数值应严格上升 函数值具有的特征是 高 低 高 根据这一特点 若已知方向上的三个点 以及其函数值 和 便可通过比较三个函数值的大小估计极小点所在的区间 3 1确定初始区间的进退法 3 1确定初始区间的进退法 极小点在右端点的右侧 3 1确定初始区间的进退法 极小点在左端点的左侧 3 1确定初始区间的进退法 极小点在与之间 称为初始区间 记为 3 1确定初始区间的进退法 探测初始空间的进退法步骤 1 给定初始点 初始步长 令 记 2 产生新的探测点 记 3 比较函数值和的大小 确定向前或向后探测的策略 若 则加大步长 令 转 4 向前探测 若 则调转方向 令 转 4 向后探测 4 产生新的探测点 令 5 比较函数值和的大小 若 则初始区间已经找到 令 当时 当时 3 1确定初始区间的进退法 若 则继续加大步长 令 转 4 继续探测 例题 求的极小点的初始区间 3 1确定初始区间的进退法 f mfunctionf f x f 3 x 3 4 x 2 3 1确定初始区间的进退法 c f2 fc f2ifh 0a x1 b x3fa f1 fb f3elsea x3 b x1fa f3 fb f1enda b c fa fb fc initial space mfunction a b c fa fb fc initial space x0 h x1 x0 f1 f x1 x2 x0 h f2 f x2 iff1 f2x3 x0 2 h f3 f x3 elseh h x2 x0 h f2 f x2 End whilef2 f3h 2 h x1 x2 x2 x3 f1 f2 f2 f3 x3 x2 h f3 f x3 Endc f2 fc f2 ifh 0a x1 b x3 fa f1 fb f3 elsea x3 b x1 fa f3 b f1 end abcfafbfc Matlab函数文件 3 2黄金分割法 一维搜索试探方法的基本思想 在确定了搜索区间的前提下 不断缩小搜索区间 同时保持搜索区间内函数值 大 小 大 的走势 直到区间的宽度小于预定的精度 黄金分割法基本思想 在搜索区间内插入两个黄金分割点 将区间分成三段 利用函数的单谷性质 通过函数值大小的比较 删去其中一段 在保留下来的区间上作同样的处置 如此往复送代 使搜索区间缩小到精度范围内 得到极小点的近似解 3 2黄金分割法 3 2黄金分割法 黄金分割法是按照对称的原则选取中间插入点而缩小区间的 具有每次达代计算时缩短率不变的特点 3 2黄金分割法 缩短率不变 3 2黄金分割法 黄金分割法的收敛准则 区间长度达到充分小 当 时 由于黄金分割法每次区间收缩比率是完全相等的 如果给定收敛精度和初始区间长度 则完成一维收缩所需缩小区间的次数为 3 2黄金分割法 黄金分割法的计算步骤 1 给定初始区间和收敛精度 2 产生中间插入点并计算其函数值 3 比较函数值和 确定区间的取舍 若 则新区间令记 若 则新区间令记 3 2黄金分割法 4 收敛判断 若 令 结束搜索 否则转 5 3 2黄金分割法 例题 求的极小点 给定 2 用黄金分割法缩小区间 1 确定初始区间 golden setion methodfunctiongoldensection a0 b0 eps a a0 b b0 x1 a 0 382 b a f1 f x1 x2 a 0 618 b a f2 f x2 iff1 f2n0 0 b x2 x2 x1 f2 f1 elsen0 1 a x1 x1 x2 f1 f2 End Matlab函数文件 whileabs b a epsifn0 0 x1 a 0 382 b a f1 f x1 elsex2 a 0 618 b a f2 f x2 endiff1 f2n0 0 b x2 x2 x1 f2 f1 3 2黄金分割法 elsen0 1 a x1 x1 x2 f1 f2 endenda b x a b 2 f f x 3 3二次插值法 二次插值法又称抛物线法 它是以目标函数的二次插值函数的极小点作为新的中间插入点 进行区间缩小的一维搜索算法 设在确定初始区间时已得到相邻的三个点及其函数值 令 过以上三点构造一个二次插值函数 对该函数求导 得到极小点 3 3二次插值法 由二次插值函数通过三点 可以求出系数 可求得 二次插值法以两个中间插入点的距离充分小作为收敛准则 即当 成立时 把作为此次一维搜索的极小点 3 3二次插值法 二次插值法区间缩小的逼近过程 3 3二次插值法 二次插值法的计算步骤 1 给定初始区间 收敛精度和区间中的一个点 2 将三个已知点按顺序排列 3 计算中间插入点及其函数值 4 收敛判断 若 则转 6 否则 转 5 5 缩小区间 若 且当时 令 且当时令 5 缩小区间 若 且当时 令 且当时令 转 3 新的插入点 3 3二次插值法 6 若 则令 否则 令 3 3二次插值法 例题 求的极小点 给定 1 确定初始区间 中间点 2 用二次插值法缩小区间 functionquadraticpolynomial a b c eps x1 a x2 c x3 b eps eps f1 f x1 f2 f x2 f3 f x3 xp 0 5 x2 2 x3 2 f1 x3 2 x1 2 f2 x1 2 x2 2 f3 x2 x3 f1 x3 x1 f2 x1 x2 f3 fp f xp i1 1 i2 1 whileabs x2 xp epsi1 i1 1 iffp f2ifxp x2x3 x2 x2 xp f3 f2 f2 fp elsex1 x2 x2 xp f1 f2 f2 fp endelseifxp x2x1 xp f1 fp elsex3 xp f3 fp endend xp 0 5 x2 2 x3 2 f1 x3 2 x1 2 f2 x1 2 x2 2 f3 x2 x3 f1 x3 x1 f2 x1 x2 f3 fp f xp endwhileabs f2 fp epsi2 i2 1 iffp f2ifxp x2x3 x2 x2 xp f3 f2 f2 fp elsex1 x2 x2 xp f1 f2 f2 fpend 3 3二次插值法 elseifxpepsiffp f2ifxp x2x3 x2 x2 xp f3 f2 f2 fp elsex1 x2 x2 xp f1 f2 f2 fp end elseifxp