一维搜索方法__论文.doc

一维搜索方法摘要：一维搜索方法是求解一维目标函数的极值点的数值迭代方法，可归结为单变量的函数的极小化问题。虽然优化设计中的大部分问题是多维问题，但是一维优化方法是优化方法中最基本的方法，在数值迭代过程中都要进行一维搜索，因此，对一维搜索方法的研究有着重要的意义。关键字：一维搜索、区间消去法、黄金分割法、插值法一一维搜索的概念1当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算： （k=0，1，2.）其中为第k+1次迭代的搜索方向，为沿搜索的最佳步长因子（通常也称作最佳步长）。2当方向给定，求最佳步长就是求一元函数的极值问题，它称作一维搜索。3求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的基础。4求解一元函数的极小点，可采用解析解法和数值解法。 解析解法 利用一元函数的极值条件，求。 为了直接利用的函数式求解最佳步长因子。可把或它的简写形式进行泰勒展开，取到二阶项，即将上式对进行微分并令其等于零，给出极值点应满足的条件从而求得这里是直接利用函数而不需要把它化成步长因子的函数不过，此时需要计算点处的梯度和海赛矩阵G。该方法的缺点是需要进行求导计算，对于函数关系复杂、求导困难或无法导的情况，使用解析法将是非常不便的。因此，在优化设计中，求解最佳步长因子主要采用数值解法，利用计算通过反复迭代计算求得最佳因子的近似值。数值解法其基本思路是：首先确定所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得数值近似解。二搜索区间的确定与区间消去法原理1. 确定搜索区间的外推法 单谷（峰）区间 在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，区间称为单谷区间。函数值：“大小大”图形：“高低高”单谷区间中一定能求得一个极小点。说明：单谷区间内，函数可以有不可微点，也可以是不连续函数，单谷区间函数图所图1所示。图1 谷区间函数图 外推方法基本思想：对任选一个初始点a1及初始步长h，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高低高”形态。如图2所示。步骤：选定初始点a1，初始步长h=h0，计算y1=f(a1)和y2=f(a1+h)比较y1和y2；a) 如果y1y2，向右前进，加大步长h=2h0，转（3）向前；b) 如果y1y3 ，加大步长h=2h，a1=a2,a2=a3,转（3）继续探测； b）如果y2y3，则初始区间得到：a=mina1,a3,b=maxa1,a3，函数最小所在区间为a,b。图2 外推法图下表显示外推法进行的步骤：前进搜索步骤表后退搜索步骤表 搜索区间外推法程序框图2.区间消去法原理基本思想：搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小的数值近似解。在搜索区间a,b内任取两点a1，b1且a1b1计算其函数值得如下结论： 极小点必在区间a,b1 则取为a1,b缩短后的搜索区间。 缩小的新区间为必在a,b1 缩小的新区间为必在a1,b3一维搜索方法分类根据插入点位置的确定方法，可以把一维搜索法分成两大类：试探法：即按照某种规律来确定区间内插入点的位置，如黄金分割法，波纳契法等。裴波纳契数列：1、1、2、3、5、8、13、21、34、55、89、144 插值法（函数逼近法）：通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入点，如二次插值法，三次插值法等。三.一维搜索的试探方法黄金分割法1、前提 函数在区间a,b上是单谷函数。 2、点的插入原则要求插入点, 的位置相对于区间a,b两端点具有对称性.要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布。3、点位置的确定方法两内分点值结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即。4、黄金分割法的搜索过程（1）给出初始搜索区间a,b及收敛精度，将赋以0.618。（2）按坐标点计算公式计算并计算其对应的函数值 （3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。（4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返回到步骤（2）。（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。（6）缩短区间的总次数（迭代次数）:5、黄金分割法程序框图四一维搜索的插值方法 在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值，这种方法称作插值方法，又叫函数逼近法。1.牛顿法（切线法）对于一维搜索函数，假定已经给出极小点的一个较好的近似点，在点附近用一个二次函数来逼近函数然后以该二次函数的极小点作为 极小点的一个新的近似点。根据极值必要条件：牛顿法的计算步骤： 给定初始点，控制误差，并令k=0 计算 求 若，则求得近似解，停止计算，否则作。 令k=k+1，转。例题 给定，试用牛顿法求其极小点解：给定初始点，控制误差=0.001 重复上边的过程，进行迭代，直到为止。可得到计算结果如下表所示: K 值01234ak35.166674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059牛顿法的特点：优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。2、二次插值法（抛物线法）基本思想：利用目标函数在不同点的函数值构成一个与原函数相近似的二次多项式，以函数的极值点（即的根）作为目标函数 的近似极值点，如下图所示。 二次插值多项式的构成及其极值点设在单谷区间中的三点 的相应函数值，则可以做出如下的二次插值多项式：多项式的极值点可从极值的必要条件求得同理：可由以下等式求得。结论：如果区间长度 足够小，则由便得出我们所要求的近似极小点 如果不满足，必须缩小区间 ，根据区间消去法原理不断缩小区间。二次插值法程序框图五运用MATLAB求解一维搜索数值问题举例用进退法确定函数的一优化搜索区间a,b。设初始点x=0,初始步长h=0。MATLAB程序：1 首先你的建立三个M函数文件 %typbound.m;function lowbound,upbound=typbound(x0,step0,startopint,searchdirection)step=step0;f0=tryobjfun(x0,startopint,searchdirection);x1=x0+step0;f1=tryobjfun(x1,startopint,searchdirection);if f1=f0 while true step=2*step; x2=x1+step; f2=tryobjfun(x2,startopint,searchdirection); if f1=f2 lowbound=x0; upbound=x2; break; else x0=x1; x1=x2; f0=f1; f1=f2; end endelse while true step=2*step; x2=x0-step; f2=tryobjfun(x2,startopint,searchdirection); if f0low,up=typbound(0,0.01,0,0,1,1)运行结果：low = 2.550000000