第3章一维搜索方法(已排)

1、1,当方向 给定，求最佳步长就是求一元函数 :,的极值问题，这一过程被称为一维搜索.,一维搜索方法分类： (a) 试探法； (b)插值法,第3章一维搜索方法,当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算:,2,3.1一维搜索的基本思想,O,f,(,a,),b,x,*,x,a,1.单谷(峰）区间 在给定区间内仅有一个谷值的函数称为单谷数，其区间称为单谷区间。,2. 找初始单谷区间是一维搜索的第一步. 第二步使区间缩小。,单谷区间中一定能求得一个极小点,函数值：“大小大” 图形：“高低高”,3,（1）选定初始点a, 初始步长hh0，计算 y1f(a1)， y2f(a1

2、h)。 （2）比较y1和y2。（a）如y1y2, 向右前进；加大步长 h2 h ，转（3）向前。 （b）如y1y2, 向左后退；h h0，转（3）向后探测。 （c）如y1y2，极小点在a1和a1h之间。,基本思想： 对f(x)任选一个初始点a1及初始步长h， 通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为 “高低高” 形态。,3.2确定初始单谷区间的进退法,步骤：,4,（3）产生新的探测点a3a1h，y3f(a3); （4）比较函数值 y2与y3： （a）如y20时，a,b=a1,a3; hy3, 加大步长 h2 h ，a1=a2, a2=a3,转（3）继续探测

3、。,5,确定初始单谷区间进退法示意图,6,f1f（a1）， f2f（b1）,搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。 假定在搜索区间内a,b 任取两点a1,b1;,3.3区间消去法原理,7,综合为两种情况： 若 则取 为缩短后的搜索区间。 若 则取 为缩短后的搜索区间。,f1f（a1）， f2f（b1） (1)如f1f2, 则缩小的新区间为a1,b; (3)如f1=f2, 则缩小的新区间为a1,b1,8,黄金分割法适用于a,b区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广。 黄金分割法也是

4、建立在区间消去法原理基础上的试探方法。 在搜索区间内a,b适当插入两点 ，将区间分成三段； 利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而得到极小点的数值近似解。,3.4黄金分割法,9,将区间分成三段,黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布 。,10,黄金分割法要求插入两点：,黄金分割法区间消去示意：,11,黄金分割法的搜索过程： 1）给出初始搜索区间及收敛精度 ，将赋以0.618。 2）按坐标点计算公式计算 ， ；并计算其对应的函数值。 3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行

5、区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。 如果 ，则新区间 令 , 记N0=0; 如果 ，则新区间 令 , 记N0=1; 4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）。,12,5）产生新的插入点： 如N0=0，则取 ； 如N0=1，则取 ； 转向3）进行新的区间缩小。,13,解： 1)确定初始区间 x1=x0=0, f1=f(x1)=2 x2=x0+h=0+1=1, f2=f(x2)=1 由于f1f2, 应加大步长继续向前探测。,x3= x0+2h=0+2=2, f3=f(

6、x3)=18 由于f2f3,可知初始区间已经找到，即a,b=x1,x2=0,2,2)用黄金分割法缩小区间 第一次缩小区间： x1=0+0.382X(2-0)=0.764, f1=0.282 x2=0+0.618 X(2-0)=1.236, f2=2.72 f10.2,例 3-1用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定 x0=0, h=1, =0.2。,14,第三次缩小区间： 令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618X(1.236-0.472)=0.944, f2=0.747 由于f10.2, 应继续缩小区间。,第二次缩小区间： 令 x

7、2=x1=0.764, f2=f1=0.282 x1=0+0.382X(1.236-0)=0.472, f1=0.317 由于f1f2, 故新区间a,b=x1,b=0.472, 1.236 因为 b-a=1.236-0.472=0.7640.2, 应继续缩小区间。,15,第四次缩小区间： 令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382X(0.944-0.472)=0.652, f1=0.223 由于f10.2, 应继续缩小区间。,第五次缩小区间： 令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382X(0.764-0.472)=

8、0.584, f1=0.262 由于f1f2, 故新区间a,b=x1,b=0.584, 0.764 因为 b-a=0.764-0.584=0.180.2, 停止迭代。,极小点与极小值： x*=0.5X(0.584+0.764)=0.674, f(x*)=0.222,16,例3-2对函数 ，当给定搜索区间 时，试用黄金分割法求极小点。,17,二次插值的基本思想是利用目标函数在不同3点的函数值构成一个与原函数f(x)相近似的二次多项式p(x)，以函数p(x)的极值点 (即p(x)=0的根)作为目标函数f(x)的近似极值点。,3.5二次插值法,18,1. 二次多项式p(x)的构成及其极小点 设原目标

9、函数的初始单峰区间为。函数在x1, x2, x3 3点处函数值分别为f1, f2, f3，,求待定系数a0, a1和a2, 并代入上式，得：,19,假若f(x)本身为二次函数，则在理论上按前式一次求值就可找到最优点 。 若f(x)为高于二次的函数或为其他函数 ,可采用区间消去法逐步缩小区间 。 根据xp* ，x2，f(xp* )和f(x2)的相互关系，分6种情况进行区间缩小。 在已有的四x1,x2,x3,xp* 中选择新的三个点x1,x2,x3，再进行二次插值。 选点要求： x1f2, f2f3 （高低高形态） 如果 ，以x2,xp* 中函数值较小的点作为最优点x*。,2 缩短区间,20,2）

10、用二次插值法逼近极小点 相邻三点的函数值: 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。,21,在新区间，相邻三点的函数值: 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.0520.2, 迭代终止。 xp*0.607, f*=0.243,由于fp0.2, 应继续迭代。,22,例 3-4用二次插值法求 的极值点。初始搜索区间 ， 。 解：取x2点为区间x1,x3的中点， , 计算x1,x2,x3 3点处的函数值f1=19，f2=-96.9375，f3=124。可见函数值满足“高低高”