第二章一维搜索法

第二章一维搜索法概述确定初始单谷区间的进退法一维搜索法分类区间消去法函数逼近法概述求一元函数F(x)的极小点和极小值问题就是一维最优化问题。求解一维优化问题的方法称为一维优化方法，又称一维搜索法。一维搜索法是优化问题中最简单、最基本方法。因为它不仅可以解决单变量目标函数的最优化问题，而且在求多变量目标函数的最优值时，大多数方法都要反复多次地进行一维搜索，用到一维优化法。一般多维优化计算的迭代的基本格式：从一个已知点 x(k)出发(x(k)由上次迭代获得，开始时就是起始点x(0))，沿某一优化方法所规定的是目标函数值下降的搜索方向 S(k)，选择一个步长因子，求得下一个新迭代点x(k1)，x(k1)x(k)S(k)并且满足F(xk1)F(xk)，即新点必须能够使目标函数值有所下降，这个新点就是下一次迭代的出发点，如此重复，直到求出目标函数的最优解为止。理想步长k可以通过F()F(x(k)S(k))的极小点获得minF()，使得目标函数达到最小minF(x(k)S(k))，这种在第k次迭代中求理想步长k的过程，就是一维搜索过程。大致分为两个步骤：确定初始搜索区域［a,b］，该区域应该包括一维函数极小点在内的单谷区域；在单谷区域［a,b］上寻找极小点。寻找极小点k可以采用解析解和数值解等方法。确定初始单谷区间的进退法单谷区域的定义：设函数F(x)在区域［X..X2］内有定义，且

(i)在区域［Xi,X2］内存在极小值X，既有minF(x)F(x)，X [X!,X2]；(2)对区域［xi,X］上任意自变量x，有F(x)F(xx)，x0；对区域[x,x2]上任意自变量x，有F(x)F(xx)，X0;则称［x,,x2］为函数F(x)的单谷区域。即在单谷区域内，在极小点x的左边，函数严格减小；在极小点x的右边，函数严格增大。自动确定单谷区域的进退算法：其基本思路：按照一定的规则试算若干个点， 比较其函数值的大小，直到找到函数值按“高-低-高”变化的单谷区域，搜索过程如下 ：(1)选择一个适当的初始步长h；⑵从任意点X)出发，以x,x0，x2x,h为两个试算点计算该两点的函数值FiF(x,)，F2F(X2)；⑶比较Fi、F2的大小，若FiF2，继续向前搜索；若FiF2，做后退运算。⑷当FiF2，极小点在X2的右方，应加大步长作前进运算， X3X22h，比较F2、F3，若F3F2，形成“高-低-高”变化，极小点在以必］，初始搜索区间确定。若F3F2，继续向前搜索，重复以上步骤；⑸当F］F2，极小点在xi的左方，做后退运算，减小步长，x3X!h2，比较F2、F3，若F3F2，形成“高-低-高”变化，极小点在［X3,Xi］，初始搜索区间确定。若F3F2，继续做后退运算，或加大步长，直到函数出现“高 -低-高”变化。迭代开始时，必须选定起始点 x迭代开始时，必须选定起始点 x0和步长h般地，X。 0,步长h任意选定，过小需要多次迭代；过大，可能遗漏单谷区域。例题：试用进退算法确定函数 F(x)x26x9的初始搜索区间［Xi,X2】。设初始点Xo0,初始步长hi【解】(i)【解】(i)X!0，hi， x2 X)Fi F(Xi)9，F2F(x2)4；(2)因FiF2，前进运算：h2，X3X2h3，F3F(X3)0；11)f(ai)f(b1) 则取［aQ］为缩小后的搜索区域;(3)因F2F3，继续推进:h4,xi1,x23必7,F3Fg)16⑷因F2 F3，故初始搜索区域形成 凶必］［1,7］。课后习题1：［试用进退算法确定函数F(x)3x38x9的初始搜索区间［Xix］。设初始点x0 1，初始步长h0.05。课后习题2课后习题2■式用进退算法确定函数F(x)x44x36x2 16x4的初始搜索区间［X1,X2］。设初始点Xo0,初始步长h0.1。一维搜索法分类当已确定了初始单谷区间后，可以一维寻优。具体方法有区间消去法和函数逼近法。区间消去法又称试探法，就是不断消去不存在最优点的区间，使搜索区域越来越短，最终寻得最优点。为了在每次迭代中缩短区间， 需要在区间内插入计算点，计算函数值。插入计算点方法有斐波纳契法、黄金分割法。函数逼近法又称插值法或近似法，用多项式代替目标函数，并利用这个多项式的极小点作为目标函数的近似最优点。这个多项式根据某点的函数值、一二阶导数等构造出来，有牛顿法(切线法)、二次插值法(抛物线法)等。区间消去法原理在搜索区域［a,b］确定后，在该区间内任取两点a1>b，a1b，并计算函数值f(a1)、f(bj。若f(ajf(bj，则取［a,bj为缩短后的搜索区间；若 f(ajfg)，则取［anb］为缩短后的搜索区间。如图所示：f(b1)f(a1)f(b1)f(a1)a1b1f(b1)f(a1)f(b1)f(a1)a1b1可以归纳为:2)fg) f(bj 则取［印，可为缩小后的搜索区域；实际计算中，常用斐波纳契法、黄金分割法。例题1利用Fibonacci法，求解min(x22x)，允许误差 0.2。3x5、 /解：a=-3,b=5,F(x) x22x，首先计算迭代次数n,一般Fn1(ba)/ (5 (3))/0.2 40,又因34，F9 55，n=8。初始两个搜索点：为 a(F7/F9)(ba)0.054；x2a(F8/F9)(ba)1.945；由于F(xJ F(X2)，保留［-3,1.945］-新区间，保留点x0.054,增加新点x3ax2x1 1.109，比较F(x1),F(x3) 例题2：利用黄金分割法，求解 min(x22x)。3x5解：a=-3,b=5,插入两个新点：x,b(ba)50.6188 0.056;x2x2a(ba)30.6188 1.944；因为F(xJ F(X2)，消去［x2,b］,新区域［-3,1.944］，新一轮迭代:为1.111,x20.056,F(xJF(x2)00000直到前后两次Fmin2课后习题3:|试用黄金分割法求函数 F(x)(x3)的最小值，给定初始单谷域［2,4］，迭代精度为 0.04;课后习题4：试用黄金分割法求函数 F(x)x20x1的最小值，给定初始单谷域［0.2,1］,迭代精度为 0.01；函数逼近法

利用插值方法建立函数的近似表达式，进而求出函数的极小值，并用它作为原来函数的极小值的近似值，这种方法称作函数逼近法，也称插值方法。多项式是函数逼近的常用工具，常用的插值多项式为二次多项式，一种是牛顿法(切线法)，另一种是抛物线法(二次插值法)牛顿法(切线法)函数yf(x)在极小点附近有近似点，在x0附近用二次函数 (x)逼近f(x),f(x)在x0进行泰勒展开有:f(x)1f(x)(x) f(Xo)f(Xo)(XX。)-f(xo)(xxo)二次函数(X)的极小值作为f(x)极小值的新近似点x!。(xj0即:f(Xo)f(Xo)(X!Xo) 0得:Xi Xi Xof(Xo)

f(Xo)依次继续，牛顿法的迭代公式:Xk1xXk1xkf(xk)f(xk)例题3:4 3 2f(x)x4x6x16x4，试用牛顿法求其极小点。3 2解：f(x) 4(x3x3x4)f(x