第三章一维搜索(线性搜索)

第三章一维搜索方法3.1概述3.2确定初始区间3.3缩小区间3.4黄金分割法（0.618法）3.5一维搜索的插值方法2()0fX12(,,,)TnXxxx第3章一维搜索方法3.1概述3.1.1一维问题是多维问题的基础求目标函数f(X)的极小点，从理论上说需要求解方程：其中那么如何来求f(X)的极小点呢？基本思想:011,,,,kkXXXX011()(),,()()kkfXfXfXfX这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。3kkkSXfkkkSXfmin:kkkkSaXX1()fX这个过程称为一维搜索过程。kkkSXf52128)(212221xxxxXF如：52202521282212221xxxxF则0000,11TTXd1100X当Sk方向上的任何一点可以表示为其中α是步长因子，为实系数，此时Sk方向上任何一点的目标函数值为，它是参数α的一元函数。那么在沿Sk方向求的极小点，这就是求一元函数的极小问题，它可表示为：)2,1,0(1kSXXkkk一维搜索示意图求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的基础。求解一元函数的极小点，可采用解析解法，即利用一元函数的极值条件求在用函数的导数求时，所用的函数是仅以步长因子为变量的一元函数，而不是以设计点x为变量的多元函数。)(*0)(*'*)(*)()(xf3.1.2的确定方法为了直接利用的函数式求解最佳步长因子。把或它的简写形式进行泰勒展开，取到二阶项，即将上式对进行微分并令其等于零，给出极值点应满足的条件从而求得这里是直接利用函数而不需要把它化成步长因子。的函数。不过，此时需要计算点处梯度和海赛矩阵H。解析解法的缺点——需要进行求导计算。对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。因此，在优化设计中，求解最佳步长因子主要采用数值解法，利用计算机通过反复迭代计算求得最佳步长因子的近似值。数值解法的基本思路是：首先确定所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得的数值近似解。解析法:①f(X(k)+αS(k))沿S(k)方向在x(k)点泰勒展开；②取二次近似：()()()()()2()()()1()[()][]()2kkkkTkkTkkfxSfxfxSSGxS0)()()(kkSxfdd③对α求导，令其为零。()()()()()[()][]()0kTkkTkkfxSSGxS()()()()()()[()][]()kTkkkTkkfxSSGxS④求得最优步长1()()()kkkkkffsxx数值解法基本思路：kk解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。一维搜索也称直线搜索。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。一维搜索一般分为两大步骤：(1)确定初始搜索区间[a，b]，该区间应是包括一维函数极小点在内的单谷区间。(2)在单谷区间[a,b]内通过缩小区间寻找极小点。先确定在的搜索区间，然后根据区间消去法原理不断缩小此区间所，从而获得的数值近似解。1、确定搜索区间的外推法在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。函数值：“大—小—大”图形：“高—低—高”单谷区间中一定能求得一个极小点。3.2确定初始区间从开始，以初始步长向前试探。如果函数值上升，则步长变号，即改变试探方向。如果函数值下降，则维持原来的试探方向，并将步长加倍。区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的“高－低－高”趋势。单谷区间f(x)0α1α3α0f(x)α3α1说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；外推方法基本思想：对任选一个初始点及初始步长，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高—低—高”形态。)(xf1ah步骤：1）选定初始点a1，初始步长h=h0，计算y1=f(a1)和y2=f(a1+h)2）比较y1和y2；a）如果y1y2，向右前进，加大步长h=2h0，转（3）向前；b）如果y1y2，向左后退，h=-2h0，将a1和a2,y1和y2的值互换。转（3）向后探测；c）如果y1=y2，极小点在a1和a1+h之间。3）产生新的探测点a3=a2+h，y3=f(a3)；4）比较函数值y2和y3：a）如果y2y3，加大步长h=2h，a1=a2,a2=a3,转（3）继续探测；b）如果y2y3，则初始区间得到：a=min[a1,a3],b=max[a1,a3]，函数最小值所在区间为[a,b]。31,321321yyy右图表示沿的正向试探。每走一步都将区间的始点、中间点沿试探方向移动一步（进行换名）。经过三步最后确定搜索间，并且得到区间始点、中间点和终点所对应的函数值。y1y3→y2y2→y1a3→a2a2→a1a1Oaa3h0h02h0图3-2正向搜索的外推法右图所表示的情况是：开始是沿的正方向试探，但由于函数值上升而改变了试探方向，最后得到始点，中间点和终点及它们的对应函数值从而形成单谷区间为一维搜索区间。y1←y2a2←a3a1←a2←a1Oaa32h0h0h0y3y1←y2←y1y2←y3a1←a2图3-3反向搜索的外推法khx1x2x30h0初始点初始点+h012h0初始点初始点+h0初始点+3h024h0初始点+h0初始点+3h0初始点+7h038h0初始点+3h0初始点+7h0初始点+15h0前进搜索步骤表khx1x2x30h0初始点初始点+h012h0初始点+h0初始点初始点-2h024h0初始点初始点-2h0初始点-6h038h0初始点-2h0初始点-6h0初始点-14h0后退搜索步骤表19.1.0,0,983)(:13013hxxxxf初始进退距给定初始点的一维优化初始区间用进退法确定函数例khx1y1x2y2x3y310.10.2090.18.2030.36.68120.40.18.2030.36.6810.74.42930.80.36.6810.74.4291.57.125.5.1,3.0,ba可得初始搜索区间解：20.1.0,8.1,983)(23013hxxxxf初始进退距给定初始点的一维优化初始区间：用进退法确定函数例:解khx1y1x2y2x3y310.1-0.21.812.0961.914.3771.914.3771.812.0961.68.4882-0.41.812.0961.68.4881.24.5843-0.81.68.4881.24.5840.45.992.6.1,4.0,ba可得初始搜索区间运用进退法确定出初始搜索区间[a,b]后，便可采用一维优化方法来求出函数f(x)在区间内的最优点x*。212.程序框图h=h0y1=f(x1)、x2=x1+h、y2=f(x2)给定x1、h0y1≥y2y2≥y3是h=2hx3=x2+h、y3=f(x3)结束否h=-hx3=x1y3=y1a=x1、b=x3是x1=x2y1=y2x2=x3y2=y3是a=x3、b=x1否h0否初始进退距3xf2x1xx1x2x3x前进计算1x2x3xfx1x2x3x后退计算1x2x1y2y3y,ab11,ab，搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。假定在搜索区间内任取两点，且)(2)(111bffaff3.3区间消去方法(1)f（a1）f（b1）,则极小点必在区间[a，b1]内;)(2)(111bffaff(1)f（a1）f（b1）,则极小点必在区间[a，b1]内;(2)f（a1）f（b1）,则极小点必在区间[α1，b]内;)(2)(111bffaff(1)f（a1）f（b1）,则极小点必在区间[a，b1]内;(2)f（a1）f（b1）,则极小点必在区间[α1，b]内;(3)f（a1）=f（b1）,则极小点必在区间[α1，b1]内)(2)(111bffaff可以总结为两种情况：①若，则取[a,b1]为缩小后的搜索区间。②若，则取[a1,b]为缩小后的搜索区间。)()(11bfaf)()(11bfaf试探法黄金分割法插值法二次插值法3一维搜索方法分类从前面的分析可知，每次缩短区间，只需要在区间内再插入一点并计算其函数值。而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。一维搜索方法分类3.4黄金分割法（0.618法）1.黄金分割法2.黄金分割法的搜索过程概述在实际计算中，最常用的一维搜索试探方法是黄金分割法，又称作0.618法。我们可以通过学习黄金分割法来了解一维搜索试探方法的基本思想。在搜索区间[a,b]内适当插入两点α1、α2，并计算其函数值。α1、α2将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。3.4黄金分割法（0.618法）黄金分割法是建立在区间消去法原理基础上的试探方法。适用于[a,b]区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。黄金分割法对插入点的要求：1）要求插入点α1、α2的位置相对于区间[a,b]两端点具有对称性，即其中为待定常数。1()bba2()aba1.黄金分割法2）黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。即每次缩小所得的新区间长度与缩小前区间长度之比（即：区间收缩率）为定值。设原区间[a,b]长度为1如下图所示，保留下来的区间[a,α2]长度为，区间缩短率为。为了保持相同的比例分布，新插入点α3应在位置上，α1在原区间的位置应相当于在保留区间的位置。故有取方程正数解，得ab2111a213(1)2图2-5黄金分割法α1、α2将区间分成三段黄金分割法要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。)(618.0)()(618.0)(21abaabaabbabb两内分点值:结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即。21510.6182黄金分割法要求插入两点：)(618.0)()(618.0)(21abaabaabbabb黄金分割法区间消去示意图：3.4黄金分割法（0.618法）2.黄金分割法的搜索过程（1）给出初始搜索区间及收敛精度，将赋以。,ab0.618（2）按坐标点计算公式计算并计算其对应的函数值12和12,ff3.4黄金分割法（0.618法）（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。3.4黄金分割法（0.618法）（4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5。（5）产生新的插入点：如N0=0，则取（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。