一维搜索方法

1、一维搜索方法摘要：一维搜索方法是求解一维目标函数的极值点的数值迭代方法，可归结为单 变量的函数的极小化问题。虽然优化设计中的大部分问题是多维问题，但是一维 优化方法是优化方法中最基本的方法，在数值迭代过程中都要进行一维搜索，因 此，对一维搜索方法的研究有着重要的意义。关键字：一维搜索、区间消去法、黄金分割法、插值法一.一维搜索的概念当采用数学规划法寻求多元函数的极值点时，一般要进行 一系列如下格式的迭代计算：xk+1 = xk +a d k (k=0，1， 2.)其中dk为第k+1次迭代的搜索方向，ak为沿dk搜索的最佳步长因子(通常 也称作最佳步长)。2.当方向dk给定，求最佳步长ak就是求

2、一元函数的极值问题，f。+1)= f (k+a dk)=q(a )它称作一维搜索。求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化 搜索方法的基础。求解一元函数甲(a)的极小点a *，可采用解析解法和数值解法。解析解法利用一元函数的极值条件平y2，向右前进，加大步长h=2h0，转（3）向前；b）如果y1y3，加大步长h=2h，a1=a2,a2=a3,转（3）继续探测；b）如果y21 3 3耳二寻一&尤=g；zxz 4工否是工1 x2 x3前进计算工1 u工3 X2互王3工2工1后退计算r餐h - 2h气=31=乃&二心北=y/痘=也上=邑丁v.h 0.区间消去法原理基本思想：搜索

3、区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小 的数值近似解。在搜索区间a,b内任取两点a1，b1且a1b1计算其函数值得如下结论:f (a) f ()则取为a1,b缩短后的搜索区间。f勺) f )缩小的新区间为必在a1,b一维搜索方法分类根据插入点位置的确定方法，可以把一维搜索法分成两大类：试探法：即按照某种规律来确定区间内插入点的位置，如黄金分割法， 波纳契法等。裴波纳契数列：1、1、2、3、5、8、13、21、34、55、89、144插值法(函数逼近法)：通过构造插值函数来逼近原函数，用插值函数的 极小点作为区间的插入点，如二次插值法，三次插值法等。三.一维搜索的试探方法黄金

4、分割法1、前提函数在区间a,b上是单谷函数。2、点的插入原则要求插入点a ,1a 2的位置相对于区间a,b两端点具有对称性.a = b -人G - a )a = a + X G - a)要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布。3、点位置的确定方法n 31 nz = 1 z2-2/Ld 0 6182两内分点值a = b -X (b - a) = b - 0.618(b - a)a = a + X (b a) = a + 0.618(b a)结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即1: X = X ：(1 -X)

5、。4、黄金分割法的搜索过程给出初始搜索区间a,b及收敛精度，将X赋以0.618。按坐标点计算公式计算以和以2并计算其对应的函数值 f G) f(以 2)（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式， 进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。（4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返 回到步骤（2）。（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。（6）缩短区间的总次数（迭代次数）：/ ln /（b - a）k ln 0.6185、黄金分割法程序框图绐定百二减 0382(3-力二爪) 花=a + Q.61

6、8(&-3):= /(Xj)B(7 = xl.r1 = = y2D.618(i-7)3 v- -/(js,)/ .x* 0.5(a-b)r=心4 =地=耳以一 31x1 - a-0.32ba) 兑=免1)也可采用迭代次教是否大于或等于k作终止准则,bXb四.一维搜索的插值方法在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够 给出若干点处的函数值。可以根据这些点处的函数值，利用插值方法建立函数的 某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值， 这种方法称作插值方法，又叫函数逼近法。1.牛顿法（切线法）对于一维搜索函数y = fG），假定已经给出极小点的

7、一个较好的近似点气， 在a点附近用一个二次函数G）来逼近函数f（a）0f(a)(a)= f(a )+f/(a )G-a )+ 2f/(a )G-a *然后以该二次函数(a)的极小点作为f (x )极小点的一个新的近似点a0。根据极值必要条件:f / c (k = 0,1,2.) f / (a )kf / (a )/(a)= 0na =a - _na =a1 0 f )k+1牛顿法的计算步骤:给定初始点a。，控制误差s，并令k=0计算f / (af (af / G )求ak+1 =ak - fk若ak+1 -aJ京，则求得近似解a，k+1停止计算，否则作。令k=k+1，转。例题 给定f (a)=

8、a4 -4a3 6a3 - 16a + 4，试用牛顿法求其极小点a *解：给定初始点a 0 = 3，控制误差s =0.001 f /(a)= 4(x3 - 3a2 - 3a - 4)f /(a)= 12C2 - 2a -1)6f / (a)13 31 a = a 0)= 3 + =10 f(a 0)66 31 - 3 =613 s6重复上边的过程，进行迭代，直到ak+1 -ak| 0.001为止。可得到计算结果 如下表所示：值01234ak35.166674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-24184

9、.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059牛顿法的特点：优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。2、二次插值法（抛物线法）基本思想：利用目标函数在不同点的函数值构成一个与原函数fG）相近似 的二次多项式p（x），以函数p（x）的极值点x*p （即pp）的根）作为目标函数 f G）的近似极值点，如下图所示。二次插值多项式的构成及其极值点设y = f G）在单谷区间

10、中的三点 气 a2 a3的相应函数值 f匕） f （a2） f （a3），则可以做出如下的二次插值多项式：p（a）= a +a a +a a2多项式p（a）的极值点可从极值的必要条件求得77/G）=a +2a a =0,艮Ja = _兰 TOC o 1-5 h z p 1一同理：可由以下等式求得a,1p（a ）=ap（a ）=oc +oc a +a a 2 = z 201 22 27?（a ）=a +OLOC +oc oc 2 =301 32 3+ aa +以以2=必)11 21 X)顼以3)如果区间长度仁-以|足够小，则由|oc -a a -a1 31结论:便得出我们所要求的近似极小点a a

11、*1 p如果不满足，必须缩小区间a, a,根据区间消去法原理不断缩小区间。13二次插值法程序框图五.运用MATLAB求解一维搜索数值问题举例用进退法确定函数f（X）= x2 - 6x + 9的一优化搜索区间a,b。设初始点x=0,初始步长h=0。MATLAB 程序：首先你的建立三个M函数文件 %typbound.m;function Iowbound,upbound=typbound(x0,step0,startopint,searchdirection)step=step0;f0=tryobjfun(x0,startopint,searchdirection);x1=x0+step0;f1=

12、tryobjfun(x1,startopint,searchdirection);if f1=f0while truestep=2*step;x2=x1+step;f2=tryobjfun(x2,startopint,searchdirection);if f1=f2lowbound=x0;upbound=x2;break;elsex0=x1;x1=x2;f0=f1;f1=f2;endendelsewhile truestep=2*step;x2=x0-step;f2=tryobjfun(x2,startopint,searchdirection);if f0low,up=typbound(0,0.01,0,