31 搜索算法结构

《31 搜索算法结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

3.1搜索算法结构一、下降算法模型考虑（fs）常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。迭代计算：其中为第次迭代的搜索方向，为沿搜索的最佳步长因子（通常也称作最佳步长）。minf(x)s.t.x∈S第三章常用的一维搜索方法

1△可行方向：设∈S，d∈Rn,d≠0,若存在，使，称d为点的可行方向。同时满足上述两个性质的方向称下降可行方向。△下降方向：设∈S，d∈Rn,d≠0,若存在，使，称d为在点的下降方向。

2模型算法线性搜索求，新点使x(k+1)∈S初始x(1)∈S,k=1对x(k)点选择下降可行方向d(k)是否满足停机条件？停k=k+1yesno531

3二、收敛性概念：考虑（fs）设迭代算法产生点列{x(k)}S.1.理想的收敛性：设x*∈S是g.opt(全局最优解).当x*∈{x(k)}或x(k)≠x*，k，满足时，称算法收敛到最优解x*。minf(x)s.t.x∈S

4由于非线性规划问题的复杂性，实用中建立下列收敛性概念：2.实用收敛性：定义解集S*={x|x具有某种性质}例：S*={x|x---g.opt}S*={x|x---l.opt}S*={x|f(x)=0}S*={x|f(x)≤β}(β为给定的实数，称为阈值)

52.实用收敛性（续）▲收敛性：设解集S*≠，{x(k)}为算法产生的点列。下列情况之一成立时，称算法收敛：1°x(k)∈S*;2°x(k)S*，k，{x(k)}的任意极限点∈S*。▲全局收敛：对任意初始点x(1),算法均收敛。局部收敛：当x(1)充分接近解x*时，算法收敛。有限步终止

6三、收敛速度设算法产生点列{x(k)}，收敛到解x*，且x(k)≠x*，k，关于算法的收敛速度，有1.线性收敛：当k充分大时成立。2.超线性收敛：3.二阶收敛：﹥0，是使当k充分大时有

7三、收敛速度（续）定理：设算法点列{x(k)}超线性收敛于x*,且x(k)≠x*，k，那么证明：只需注意|||x(k+1)–x*||-||x(k)–x*|||≤||x(k+1)–x(k)||≤||x(k+1)–x*||+||x(k)–x*||，除以||x(k)–x*||并令k→∞，利用超线性收敛定义可得结果。该结论导出算法的停止条件可用：

8四、二次终结性▲一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，则称该算法具有二次终结性。

9问题描述：已知并且求出了处的可行下降方向从出发，沿方向求如下目标函数的最优解，或者选取使得：常用的一维搜索算法

10设其最优解为（叫精确步长因子），所以线性搜索是求解一元函数的最优化问题（也叫一维最优化问题或一般地，一维优化问题可描述为：于是得到一个新点：一维搜索）。或解

11一般地，线性搜索算法分成两个阶段：第一阶段确定包含理想的步长因子（或问题最优解）的搜索区间；第二阶段采用某种分割技术或插值方法缩小这个区间。

12搜索区间的确定黄金分割法(0.618法)二次插值法Newton法要点：单峰函数的消去性质、进退算法基本思想、黄金分割法基本思想、重新开始、二次插值法要求、极小化框架、Newton法基本思想、方法比较。我们主要介绍如下一些搜索方法：

13学习的重要性：1、工程实践中有时需要直接使用；2、多变量最优化的基础，迭代中经常要用到。方法分类：1、直接法：迭代过程中只需要计算函数值；2、微分法：迭代过程中还需要计算目标函数的导数；

14f(x)xab§3.2搜索区间的确定常用的一维直接法有消去法和近似法两类。它们都是从某个初始搜索区间出发，利用单峰函数的消去性质，逐步缩小搜索区间，直到满足精度要求为止。§3.2.1单峰函数连续单峰函数f(x)xab不连续单峰函数f(x)xab离散单峰函数f(x)xab非单峰函数定义：如果函数f(x)在区间[a,b]上只有一个极值点,则称f(x)为[a,b]上的单峰函数。

15单峰函数具有一个重要的消去性质定理：设f(x)是区间[a,b]上的一个单峰函数，x*∈[a,b]是其极小点，x1和x2是[a,b]上的任意两点，且a

16§3.2.2进退算法(或称成功-失败法)如何确定包含极小点在内的初始区间?（一）基本思想：由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。f(x)xabx*x0x1x2从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。由两边高，中间低的三点，可确定极小点所在的初始区间。

17（二）算法1、选定初始点a和步长h;f(x)x2、计算并比较f(a)和f(a+h)；有前进(1)和后退(2)两种情况：(1)前进运算：若f(a)≥f(a+h),(2)后退运算：若f(a)

18(三)几点说明缺点：效率低；优点：可以求搜索区间；注意：h选择要适当，初始步长不能选得太小；

19§3.3区间消去法－黄金分割法消去法的思想：反复使用单峰函数的消去性质，不断缩小包含极小点的搜索区间，直到满足精度为止。消去法的优点：只需计算函数值，通用性强。消去法的设计原则：（1）迭代公式简单；（2）消去效率高；（3）对称：x1–a=b-x2；（4）保持缩减比：λ=(保留的区间长度／原区间长度)不变。（使每次保留下来的节点，x1或x2，在下一次的比较中成为一个相应比例位置的节点）。（一）黄金分割xabLλL(1－λ)L取“＋”，λ=0.61803398874189

20（二）黄金分割法的基本思想黄金分割重要的消去性质:x2abLλL(1－λ)Lx1λL(1－λ)L设x1，x2为[a,b]中对称的两个黄金分割点，x1为[a,x2]的黄金分割点x2为[x1,b]的黄金分割点在进行区间消去时，不管是消去[a,x1]，还是消去[x2，b]，留下来的区间中还含一个黄金分割点，只要在对称位置找另一个黄金分割点，又可以进行下一次区间消去。每次消去后，新区间的长度是原区间的0.618倍，经过n次消去后，保留下来的区间长度为0.618nL，需计算函数值的次数为n+1。黄金分割比λ0.618，所以此法也称为0.618法。

21（三）算法开始b-x1<x2–a<给定a0,b0,a=a0,b=b0,=0.618034x2=a+(b-a),x1=a+b－x2f2=f(x2),f1=f(x1)f1f2是否a=x1,x1=x2,f1=f2x2=a+b-x1,f2=f(x2)否b=x2,x2=x1,f2=f1x1=a+b-x2,f1=f(x1)否x*∈[a,x2]x*∈[x1,b]x*=x1,f*=f1结束是x*=x2,f*=f2是abx2x1x1＋x2=a＋b

22!!!在迭代过程中，四个点的顺序始终应该是a

23f(x)=x2,a=-1.5,b=1;精度10-5ax1x2b-3.6034e-0052.9804e-0062.7093e-0056.6107e-005220.6180340.618034(x1-a)/(x2-a)(b-x2)/(b-x1)-3.6034e-005-1.1922e-0052.9804e-0062.7093e-005230.6180340.618034-1.1922e-0052.9804e-0061.219e-0052.7093e-005240.6180350.618035-1.1922e-005-2.7117e-0062.9804e-0061.219e-005250.6180320.618032-1.1922e-005-6.2296e-006-2.7117e-0062.9804e-006260.6180380.618038x*=-2.7117e-006若用0.618效果较差

24f(x)=x2,a=-1.5,b=1;精度10-10ax1x2b-2.1976e-007-9.7339e-008-2.4483e-0089.7933e-008340.6269020.626902-9.7339e-008-2.4483e-0082.5078e-0089.7933e-008350.5951450.595145-9.7339e-008-4.7778e-008-2.4483e-0082.5078e-008360.6802640.680264-4.7778e-008-2.4483e-0081.7832e-0092.5078e-008370.4700170.470017-2.4483e-0081.7832e-009-1.1888e-0092.5078e-008381.127581.12758(x1-a)/(x2-a)(b-x2)/(b-x1)1.7832e-009-1.1888e-0092.805e-0082.5078e-00839-0.113146-0.1131461.7832e-0093.1022e-008-1.1888e-0092.805e-008-9.83816-9.83816x*=-1.1888e-009(不满足精度)若用0.618效果更差

25f(x)=x2,a=-1.5,b=1;精度10-10重新开始ax1x2b-7.8811e-0101.9703e-0108.0587e-0101.791e-009440.6180340.618034(x1-a)/(x2-a)(b-x2)/(b-x1)-7.8811e-010-1.7926e-0101.9703e-0108.0587e-010450.6180340.618034-7.8811e-010-4.1182e-010-1.7926e-0101.9703e-010460.6180340.618034-4.1182e-010-1.7926e-010-3.5532e-0111.9703e-010470.6180340.618034-1.7926e-010-3.5532e-0115.3298e-0111.9703e-010480.6180340.618034-1.7926e-010-9.0432e-011-3.5532e-0115.3298e-011490.6180340.618034-9.0432e-011-3.5532e-011-1.6019e-0125.3298e-011500.6180340.618034x*=-1.6019e-012(满足要求)

26设f(x)在[a,b]上可微，且当导数为零时是解。取x=(a+b)/2,那么f'(x)=0时,x为最小点,x=x*;f'(x)>0时,x在上升段,x*x，去掉[a,x].(自己画算法框图)axbαtgα>0f′(x)αaxbtgα<0f′(x)§3.4二分法

27[a,b]缩小，当区间[a,b]的长度充分小时，或者当充分小时，即可将[a,b]的中点取做极小点的近似点，这时有估计：我们知道，在极小点处，，且时，递减，即，而当，函数递增，即若找到一个区间[a,b],满足性质。，则[a,b]内必有的极小点，且，为找此，取，若，则在中有极小点，这时用作为新的区间[a,b]，继续这个过程，逐步将区间

28假设f(x)是具有极小点的单峰函数，则必存在区间[a,b]，使f'(a)<0,f'(b)>0。由f'(x)的连续性可知，必有x*(a,b)，使f'(x)=0f'(x)xaba1b1a2b2优点：计算量较少，总能找到最优点缺点：要计算导数值，收敛速度较慢，收敛速度为一阶其中区间[a,b]的确定,一般可采用“进退法”。

29§3.5多项式近似法－二次插值法（一）基本思想对形式复杂的函数，数学运算时不方便找一个近似的、解析性能好、便于计算的简单函数来代替。用近似函数的极小点作为原函数极小点的近似复杂函数f(x)极小点x**简单函数P(x)极小点x*函数近似，最优点也应近似一次多项式二次多项式三次多项式?如何构造符合要求的多项式?

30f(x)P2(x)（二）二次插值多项式近似法（抛物线法）的基本原理设目标函数f(x)在三点x1

31!迭代过程要点！f(x)P2(x)x1x2x3x1x2x3x**x*x**若任意取x1

32在完成一次计算后，得到近似x*，比较f(x*)与f(x2)，以函数值较小的x为起点，缩短步长近似x*进退算法构造“极小化框架”x1

33f(x)xx1x2x3f(x)xx1x2x4前进成功x5极小化框架x1x2x3前进失败x1x2x3x4x5x6极小化框架x3x2x1后退h02h04h0h0h02h04h0（三）进退算法（用于求“极小化框架”或初始搜索区间）

34（四）逐次二次插值近似法的算法初始点x1，h0，精度ε1，溢出下限ε2，步长缩短率m进退算法即“极小化框架”x1

35二次插值法的优点：收敛速度较快，约为1.32阶缺点：对强扭曲或多峰的，收敛慢，甚至会失败，故要求函数具有较好的解析性能（五）二次插值法与黄金分割法的结合黄金分割法二次插值法迭代收敛时迭代不收敛时

362）用二次插值法逼近极小点相邻三点的函数值: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。

37在新区间，相邻三点的函数值: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.052<0.2,迭代终止。xp*＝0.607,f*=0.243由于fp0.2,应继续迭代。此例黄金分割法需要5次收缩区间，例

38例3-4用二次插值法求的极值点。初始搜索区间，。图解：取x2点为区间[x1,x3]的中点，,计算x1,x2,x33点处的函数值f1=19，f2=-96.9375，f3=124。可见函数值满足“高－低－高”形态。以x1,x2,x3为插值点构造二次曲线，求第一次近似的二次曲线p(x)的极小值点，由公式得。，比较函数值可知这种情况应消除左边区段。然后用作为x1,x2,x3新3点,重新构造二次曲线p(x)，如此反复计算，直到为止。整个迭代过程的计算结果列于表2-2.从表中可见，经7次迭代后，　　　　　　，终止迭代。故最优点

39

40

41要求计算导数的插值法若目标函数f(x)可导，可通过解f'(x)＝0求平稳点，进而求出极值点。对高度非线性函数，要用逐次逼近求平稳点。一、Newton法要求目标函数f(x)在搜索区间内具有二阶连续导数，且已知f‘(x)和f“(x)的表达式。（一）基本思想采用迭代法求φ(x)=0的根xkφ(x)xxk+1xk+2φ’(xk)=－φ(xk)/(xk＋1－xk)xk+1=xk－φ(xk)/φ’(xk)用于求φ(x)＝f'(x)＝0的根xK+1=xk－f’(xk)/f”(xk)0——一点二次插值

42

43牛顿法程序流程：

44例题用Newton法求解初始点取x0=1。（迭代二次）解：f(x)的一阶和二阶导函数为迭代公式为xK+1=xk－f’(xk)/f”(xk)第一次迭代：x0=1,f’(x0)＝－12,f”(x0)＝36x1＝1－(－12)/36＝1.33第二次迭代：x1=1.33,f’(x1)＝－3.73,f”(x1)＝17.6x2＝1.33－(－3.73)/17.6＝1.54(本例精确解为x*)第三次迭代：x2=1.54,f’(x2)＝－0.5865,f”(x1)＝12.76x2＝1.54－(－0.587)/12.76＝1.586

45例1：求minf(x)=arctantdt解：f′(x)=arctanx,f″(x)=1／(1+x2)迭代公式：xk+1=xk-(1+xk2)arctanxk取x1=1，计算结果：kxkf′(xk)1／f″(xk)110.785422-0.5708-0.51871.325830.1169-0.11641.01374-0.001095-0.00109557.9631e-010x4≈x*=0取x1=2，计算结果如下：2-3.535713.9510-279.34411.2202e+005不收敛！

46

47(二)优缺点1、优点：收敛速度快；在f'(x)=0的单根处，是2阶收敛；在f'(x)=0的重根处，是线性收敛。2、缺点：需要求二阶导数，若用数值导数代替，由于舍入误差将影响收敛速度；收敛性还依赖于初始点及函数性质。f’(x)x!!!通常在计算程序中规定最大迭代次数，当次数达到K还不能满足精度时，则认为不收敛，要换一个初始点。

48二、二点二次插值af’(x)xbx*1)割线法——基本思想：用割线代替Newton法中的切线，并与区间消去法相结合。cP52(3-14)P51(3-12)2)另一个二点二次插值——较割线法稍好收敛速度都为1.618阶通过检查区间两端导数来收缩区间——新区间两端点的导数值异号

49基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）构造一个三次多项式P3(x)，用P3(x)的极小点近似目标函数的极小点x*利用函数在两点的函数值和导数值：三、三次插值三次插值法的收敛速度比二次插值法要快，达到2阶收敛速度。

50求出：

51极值的条件：

52极值充分条件为：将极值点方程带入上式仅取正号

53

54

55二点三次插值法一般流程：编写程序应用时建议结合教材框图编写，其更具普适性、鲁棒性。

56教材P56-58的D.S.C.法、Powell法及其组合法是区间搜索一二次插值法的结合！P59-P64介绍了有理插值、连分式方法属特殊方法，含教材作者的一些研究成果，大家参阅教材，注意其适应条件，必要时课选用.

57方法综述（1）如目标函数能求二阶导数：用Newton法收敛快（2）如目标函数能求一阶导数：首先考虑用三次插值法，收敛较快对分法、收敛速度慢，但可靠二次插值如割线法也可选择.（3）只需计算函数值的方法：首先考虑用二次插值法,收敛快黄金分割法收敛速度较慢，但可靠

58作业一、用黄金分割法求函数f(x)=3x4-4x2+2的极小点，给定x0=-2,h=1,ε=0.1(x0=2,h=1,ε=0.1)。二、ch33.13.7-9课件见http://web.ee.xidian.edu.cn/sszhou/--课程教学

59解：1)确定初始区间x1=x0=0,f1=f(x1)=2x2=x0+h=0+1=1,f2=f(x2)=1由于f1>f2,应加大步长继续向前探测。x3=x0+2h=0+2=2,f3=f(x3)=18由于f20.2例3-1用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定x0=0,h=1,ε=0.2。

60第三次缩小区间：令x1=x2=0.764,f1=f2=0.282x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f10.2,应继续缩小区间。第二次缩小区间：令x2=x1=0.764,f2=f1=0.282x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1>f2,故新区间[a,b]=[x1,b]=[0.472,1.236]因为b-a=1.236-0.472=0.764>0.2,应继续缩小区间。

61第四次缩小区间：令x2=x1=0.764,f2=f1=0.282x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f10.2,应继续缩小区间。第五次缩小区间：令x2=x1=0.652,f2=f1=0.223x1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新区间[a,b]=[x1,b]=[0.584,0.764]因为b-a=0.764-0.584=0.18<0.2,停止迭代。极小点与极小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222返回