第三章一维搜索方法 概述 搜索区间的确定 维搜索的试探方法 黄金分割法 维搜索的插值方法 牛顿法(切线法) 二次插值法
第三章 一维搜索方法 • 概述 – 搜索区间的确定 • 一维搜索的试探方法 – 黄金分割法 • 一维搜索的插值方法 – 牛顿法(切线法) – 二次插值法
概述 直接搜索法更适合于工程实践 对于单个变量(一维问题)的直接搜索, 通常称为一维搜索或线性搜索 多维问题转化为一维问题求解
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
二)迭代步骤初始逆迟题 给定x1 h=h y=f(x1)、x2×x1+h、yzf(x2) 3 否 y3-y 是 前进计算 x1=X2 xX2+h、yf(x3) y1=y2 是 y2≥y3 y2-y3 否是 3d a=x、b=x1 否h>0 a=x1、b=x3 3 后退计算 结束
7 h=h0 y1=f(x1)、x2=x1+h、y2=f(x2) 给定x1、h0 y1≥y2 y2≥y3 是 h=2h x3=x2+h、y3=f(x3) 结束 否 h= -h x3=x1 y3=y1 a=x1、b=x3 是 x1=x2 y1=y2 x2=x3 y2=y3 是 a=x3、b=x1 否 h>0 否 二) 迭代步骤 初始进退距 3 x f 2 x1 x x 1 x 2 x 3 x 前进计算 1 x 2 x3 x f x1 x2 x 3 x 后退计算 1 x 2 x 1 y 2 y 3 y
3-1用进退法确定函数f(x)=3x3-8x+9的一维优化初始区间给定 初始点x1=0,初始进退距h=0.1 解 k h 0.1 09 0.18.203 0.2 0.36.681 20.40.18.2030.36.6810.74.429 30.80.3.6.6810.74.4291.5725 可得初始搜索区间a,b]=[03,15
8 0, 0.1. 3 1. ( ) 3 8 9 , 1 0 3 = = − = − + x h f x x x 初始点 初始进退距 用进退法确定函数 的一维优化初始区间 给定 解： k h x1 y1 x2 y2 x3 y3 1 0.1 0.2 0 9 0.1 8.203 0.3 6.681 2 0.4 0.1 8.203 0.3 6.681 0.7 4.429 3 0.8 0.3 6.681 0.7 4.429 1.5 7.125 可得初始搜索区间a, b= 0.3, 1.5
3-2用进退法确定函数f(x)=3x3-8x+9的一维优化初始区间给定 初始点x1=1.8,初始进退距h=0.1 解 k 0.11.812.0961914.377 021914.3771.812.0961.68.488 2-0418120961.68488124584 3-0.81.68.4881.24.584.1045992 可得初始搜索区间,b=[04,16
9 1.8, 0.1. 3 2. ( ) 3 8 9 , 1 0 3 = = − = − + x h f x x x 初始点 初始进退距 用进退法确定函数 的一维优化初始区间 给定 解： k h x1 y1 x2 y2 x3 y3 1 0.1 -0.2 1.8 12.096 1.9 14.377 1.9 14.377 1.8 12.096 1.6 8.488 2 -0.4 1.8 12.096 1.6 8.488 1.2 4.584 3 -0.8 1.6 8.488 1.2 4.584 0.4 5.992 可得初始搜索区间a, b= 0.4, 1.6
进退法的计算机程序框图 to, h t1=t0:t2=t0+h f1=f(t1);f2=f(1 否 h=2h h=h/4 f2<f1 t2=t2+h f1=f2;f2=f(t2) t1=t1+h f2=f1 t1=t2-h f2<f1 f1=f(t1) 否 f2<f1 b=t2 t2=t1-h h=2h 结束
10 进退法的计算机程序框图 t0 , h t1=t0; t2=t0+h f1=f(t1); f2=f(t2) f2<f1 h=2h t2=t2+h f1=f2; f2=f(t2) h=-h/4 否 是 t1=t2-h f2<f1 t1=t1+h f2=f1 f1=f(t1) f2<f1 t2=t1-h h=2h 否 a=t1 b=t2 是 是 否 结束
维搜索方法的分类 为了每次缩短区间,只需要在区间内再插入一点并计 算其函数值。然而,对于插入点的位置,是可以用不 同的方法来确定的。 类称作试探法:区间内插入点位置的确定仅仅按照 区间缩短如何加快,而不顾及函数值的分布关系 黄金分割法等 类称作插值法或函数逼近法:构造一个插值函数来 逼近原来函数,用插值函数的极小点作为区间的插入 点 牛顿法、二次插值法等
11 一维搜索方法的分类 • 为了每次缩短区间，只需要在区间内再插入一点并计 算其函数值。然而，对于插入点的位置，是可以用不 同的方法来确定的。 • 一类称作试探法：区间内插入点位置的确定仅仅按照 区间缩短如何加快，而不顾及函数值的分布关系 – 黄金分割法等 • 一类称作插值法或函数逼近法：构造一个插值函数来 逼近原来函数，用插值函数的极小点作为区间的插入 点 – 牛顿法、二次插值法等