第三章一维搜索方法 概述 搜索区间的确定 维搜索的试探方法 黄金分割法 维搜索的插值方法 牛顿法(切线法) 二次插值法
第三章 一维搜索方法 • 概述 – 搜索区间的确定 • 一维搜索的试探方法 – 黄金分割法 • 一维搜索的插值方法 – 牛顿法(切线法) – 二次插值法
概述 直接搜索法更适合于工程实践 对于单个变量(一维问题)的直接搜索, 通常称为一维搜索或线性搜索 多维问题转化为一维问题求解
2 概述 • 直接搜索法更适合于工程实践 • 对于单个变量（一维问题）的直接搜索， 通常称为一维搜索或线性搜索 • 多维问题转化为一维问题求解
多维和一维间的转换 多维目标函数的极值问题,通常采用数值迭代的方法 求解 xk+I=xk+ andk (k=0, 1, 2, L 每一步的格式都是从某一定点x出发沿着某一使函数 值下降的规定方向d,找出在此方向的极值点xx+1。 在任何一次迭代计算过程中,当起步点和方向确定之 后,就把求多维问题的目标函数的极小值这个多维问 题,转变成求一个变量即步长a的最优值的一维问题 f(kt)=minf(xK+ andk)=minf(ak 沿着规定方向求a的最优值以使x+ad)得到极小值 的过程,就是一维搜索或一维最优化回题,而a则称 为一维搜索的最优化步长 多维问题就转换为一系列的一维搜索问题
3 多维和一维间的转换 • 多维目标函数的极值问题，通常采用数值迭代的方法 求解 • 每一步的格式都是从某一定点x k出发沿着某一使函数 值下降的规定方向d k，找出在此方向的极值点x k+1 。 • 在任何一次迭代计算过程中，当起步点和方向确定之 后，就把求多维问题的目标函数的极小值这个多维问 题，转变成求一个变量即步长ak的最优值的一维问题 • 沿着规定方向求ak的最优值以使f(xk+akd k )得到极小值 的过程，就是一维搜索或一维最优化问题，而ak则称 为一维搜索的最优化步长 • 多维问题就转换为一系列的一维搜索问题 ( ) 1 0,1, 2, k k k x x a d k k + = + = L ( ) ( ) ( ) 1 min min k k k k k f x f x a d f a + = + =
维搜索方法 采用数值解法代替解析解法 第一步是确定搜索区间,即最优步长a所在 的区间[a,b,搜索区间应为单峰区间,区间 内目标函数应只有一个极小值 第二步是在此区间内求最优步长ak,使目标 函数〔x+a)达到极小,即通过某种原理不断 缩小搜索区间,从而获得最优步长α*的数值 近似解
5 一维搜索方法 • 采用数值解法代替解析解法 – 第一步是确定搜索区间，即最优步长ak所在 的区间[a,b]，搜索区间应为单峰区间，区间 内目标函数应只有一个极小值 – 第二步是在此区间内求最优步长ak，使目标 函数f(xk+ak )达到极小，即通过某种原理不断 缩小搜索区间，从而获得最优步长a*的数值 近似解
确定初始搜索区间的进退算法 )基本思路 试探后作前进或后返计算 X2x X 12x 142 前进计算 后退计算 6
6 确定初始搜索区间的进退算法 3 x f 2 x 1 x x 1 x 2 x 3 x 1 x 2 x 3 x f x1 x2 x 3 x 前进计算 后退计算 —试探后作前进或后退计算。 一）基本思路 1 x 2 x