搜索算法结构教学.ppt

3.1 搜索算法结构,一、下降算法模型 考虑（NP） 常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。迭代计算： 其中 为第 次迭代的搜索方向， 为沿 搜索的最佳步长因子（通常也称作最佳步长）。,第三章 常用的一维搜索方法,可行方向：设 S，dRn,d0,若存在 ，使 ，称d 为 点的可行方向。 同时满足上述两个性质的方向称下降可行方向。,下降方向 ： 设 S，d Rn,d0,若存在 ，使 ，称d 为 在 点的下降方向。,模型算法,线性搜索求 ， 新点 使x(k+1)S,yes,no,5,3,1,二、收敛性概念： 考虑（NP） 设迭代算法产生点列x(k) S. 1. 理想的收敛性：设x*S是g.opt(全局最优解).当x* x(k) 或 x(k) x*， k，满足 时，称算法收敛到最优解 x*。,由于非线性规划问题的复杂性，实用中建立下列收敛性概念 ： 2. 实用收敛性：定义解集 S* = x | x 具有某种性质 例：S*=x|x-g.opt S*=x|x-l.opt S*=x| f(x)=0 S*=x|f(x) (为给定的实数阈值),2.实用收敛性（续） 收敛性：设解集S* ，x(k)为算法产生的点列。下列情况之一成立时，称算法收敛： 1x(k) S*; 2x(k) S*， k，x(k)的任意极限点x* S* 。 全局收敛：对任意初始点x(1),算法均收敛。 局部收敛：当x(1) 充分接近解x*时，算法收敛。,有限步终止,三、收敛速度 设算法产生点列x(k) 收敛到解x*，且x(k)x*, k，关于算法的收敛速度，有 1.线性收敛： 当k充分大时成立。 2.超线性收敛： 3.二阶收敛： 0，是 使当k充分大时有,三、收敛速度（续） 定理：设算法点列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，利用超线性收敛定义可得结果。,该结论导出算法的停止条件可用：,四、二次终结性 一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，则称该算法具有二次终结性。,已知,并且求出了,处的可行下降方向,从,出发，,沿方向,求如下目标函数的最优解，,或者选取,使得：,常用的一维搜索算法,设其最优解为,（叫精确步长因子），,所以线性搜索是求解一元函数,的最优化问,题（也叫一维最优化问题或,一般地，一维优化问题可描述为：,于是得到一个新点：,一维搜索）。,或解,一般地，线性搜索算法分成两个阶段：,第一阶段确定包含理想的步长因子,（或问题最优解）的搜索区间；,第二阶段采用某种分割技术或插值,方法缩小这个区间。,搜索区间的确定 黄金分割法(0.618法) 二次插值法 Newton法,要点：单峰函数的消去性质、进退算法基本思想、黄金分割法基本思想、重新开始、二次插值法要求、极小化框架、Newton法基本思想、方法比较。,我们主要介绍如下一些搜索方法：,学习的重要性：,1、工程实践中有时需要直接使用；,2、多变量最优化的基础，迭代中经常要用到。,方法分类：,1、直接法：迭代过程中只需要计算函数值；,2、微分法：迭代过程中还需要计算目标函数的导数；,3.2 搜索区间的确定,常用的一维直接法有消去法和近似法两类。它们都是从某个初始搜索区间出发，利用单峰函数的消去性质，逐步缩小搜索区间，直到满足精度要求为止。,3.2.1 单峰函数,连续单峰函数,不连续单峰函数,离散单峰函数,非单峰函数,定义：如果函数f(x)在区间a,b上只有一个极值点, 则称f(x)为 a, b上的单峰函数。,单峰函数具有一个重要的消去性质,定理：设f(x)是区间a,b上的一个单峰函数，x*a,b是其极小点， x1 和x2是a, b上的任意两点，且ax1 x2b，那么比较f(x1)与f(x2)的值后，可得出如下结论：,(I) 消去a, x1 ,(II) 消去x2, b,(II) 若f(x1) f(x2), x*a,x2,在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，若再计算另一点的函数值，比较后就可进一步缩小搜索区间 .,（I） 若f(x1)f(x2)，x*x1,b,3.2.2 进退算法 (或称成功-失败法),如何确定包含极小点在内的初始区间 ?,（一）基本思想：,由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。,从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。 由两边高，中间低的三点，可确定极小点所在的初始区间。,（二）算法,1、选定初始点a 和步长h;,2、计算并比较f(a)和f(a+h)；有前进(1)和后退(2)两种情况：,则步长加倍，计算f(a+3h)。若f(a+h) f(a+3h)， 令 a1=a, a2=a+3h, 停止运算；否则将步长加倍，并重复上述运算。,则将步长改为h。计算f(ah), 若f(ah) f(a)， 令 a1=ah, a2=a+h, 停止运算；否则将步长加倍，继续后退。,仅仅找区间！若进一步找最小点，参阅P44!,(三) 几点说明 缺点：效率低； 优点：可以求搜索区间； 注意：h 选择要适当，初始步长不能选得太小；,3.3 区间消去法黄金分割法,消去法的思想：反复使用单峰函数的消去性质，不断缩小包含极小点的搜索区间，直到满足精度为止。,消去法的优点：只需计算函数值，通用性强。,消去法的设计原则：（1）迭代公式简单；（2）消去效率高； （3）对称： x1 a = b-x2 ；（4）保持缩减比：=(保留的区间长度原区间长度) 不变。（使每次保留下来的节点， x1或 x2 ，在下一次的比较中成为一个相应比例位置的节点 ）。,（一）黄金分割,取 “ ”，=0.61803398874189,（二）黄金分割法的基本思想,黄金分割重要的消去性质:,设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法。,（三）算法,开始,x*a, x2,x*x1, b,! 在迭代过程中，四个点的顺序始终应该是 ax1 x2 b,但在计算第二个分割点时使用x1 =a+bx2 或 x2 =a+b x1, 由于舍入误差的影响，可能破坏ax1 x2 b这一顺序，导致混乱。迭代中必须采取一些措施：,(1) 终止限不要取得太小；,(2) 使用双精度运算；,(3) 经过若干次运算后，转到算法中的第3步，重新开始。,(四) 黄金分割法的优缺点,2、缺点：对解析性能好的单峰函数，与后面要介绍的二次插值法、三次 插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。,1、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好， 对多峰函数或强扭曲的，甚至不连续的，都有效;,例3-2 对函数 ，当给定搜索区间 时，试用黄金分割法求极小点。,f(x)=x2, a=-1.5, b=1;精度10-5,a x1 x2 b -3.6034e-005 2.9804e-006 2.7093e-005 6.6107e-005 22 0.618034 0.618034 (x1-a)/(x2-a) (b-x2)/(b-x1) -3.6034e-005 -1.1922e-005 2.9804e-006 2.7093e-005 23 0.618034 0.618034 -1.1922e-005 2.9804e-006 1.219e-005 2.7093e-005 24 0.618035 0.618035 -1.1922e-005 -2.7117e-006 2.9804e-006 1.219e-005 25 0.618032 0.618032 -1.1922e-005 -6.2296e-006 -2.7117e-006 2.9804e-006 26 0.618038 0.618038 x*= -2.7117e-006,若用0.618效果较差,0.61803,f(x)=x2, a=-1.5, b=1;精度10-10,a x1 x2 b -2.1976e-007 -9.7339e-008 -2.4483e-008 9.7933e-008 34 0.626902 0.626902 -9.7339e-008 -2.4483e-008 2.5078e-008 9.7933e-008 35 0.595145 0.595145 -9.7339e-008 -4.7778e-008 -2.4483e-008 2.5078e-008 36 0.680264 0.680264 -4.7778e-008 -2.4483e-008 1.7832e-009 2.5078e-008 37 0.470017 0.470017 -2.4483e-008 1.7832e-009 -1.1888e-009 2.5078e-008 38 1.12758 1.12758 (x1-a)/(x2-a) (b-x2)/(b-x1) 1.7832e-009 -1.1888e-009 2.805e-008 2.5078e-008 39 -0.113146 -0.113146 1.7832e-009 3.1022e-008 -1.1888e-009 2.805e-008 -9.83816 -9.83816 x* = -1.1888e-009(不满足精度),若用0.618效果更差,f(x)=x2, a=-1.5, b=1;精度10-10 重新开始,a x1 x2 b -7.8811e-010 1.9703e-010 8.0587e-010 1.791e-009 44 0.618034 0.618034 (x1-a)/(x2-a) (b-x2)/(b-x1) -7.8811e-010 -1.7926e-010 1.9703e-010 8.0587e-010 45 0.618034 0.618034 -7.8811e-010 -4.1182e-010 -1.7926e-010 1.9703e-010 46 0.618034 0.618034 -4.1182e-010 -1.7926e-010 -3.5532e-011 1.9703e-010 47 0.618034 0.618034 -1.7926e-010 -3.5532e-011 5.3298e-011 1.9703e-010 48 0.618034 0.618034 -1.7926e-010 -9.0432e-011 -3.5532e-011 5.3298e-011 49 0.618034 0.618034 -9.0432e-011 -3.5532e-011 -1.6019e-012 5.3298e-011 50 0.618034 0.618034 x* = -1.6019e-012(满足要求),设 f (x)在 a ,b上可微，且当导数为零时是解。 取 x=(a+b) / 2, 那么 f (x) = 0 时, x 为最小点, x= x* ; f (x) 0 时, x 在上升段, x* x，去掉a, x . (自己画算法框图),3.4 二分法,a,b缩小，当区间a,b的长度充分小时，或者当 充分小时，即可将a,b的中点取做极小点的近似点，这 时有估计：,我们知道，在极小点,处，,，且,时，,递减，即,，而当,，函数递增，即,若找到一个区间a, b, 满足性质,。,，则,a,b内必有,的极小点,，且,，为找此,，,取,，若,，,则在,中有极小点，这时,用,作为新的区间a,b，继续这个过程，逐步将区间,假设 f(x) 是具有极小点的单峰函数，,则必存在区间a, b，使f (a)0。,由f (x)的连续性可知，必有x*(a, b)，使f (x)=0,优点：计算量较少，总能找到最优点,缺点：要计算导数值，收敛速度较慢，收敛速度为一阶,其中区间a, b的确定,一般可采用“进退法”。,3.5 多项式近似法二次插值法,（一）基本思想,对形式复杂的函数，数学运算时不方便,复杂函数 f(x),极小点x*,函数近似， 最优点也应近似,一次多项式 二次多项式 三次多项式,? 如何构造符合要求的多项式 ?,（二）二次插值多项式近似法（抛物线法）的基本原理,设目标函数 f(x)在三点x1 x2 x3 上的函数值分别为f 1 , f2 , f3,相应的二次插值多项式为 P2(x)=a0a1x + a2x2,令P2(x) 和f(x)在三点上的函数值相等,三个待定系数,P2(x)的平稳点是 P2(x)a1 +2a2x =0 的解,（二）二次插值多项式近似法（抛物线法）的基本原理,设目标函数 f(x)在三点x1 x2 x3 上的函数值分别为f 1 , f2 , f3,相应的二次插值多项式为 P2(x)=a0a1x + a2x2,三个待定系数,P2(x)的平稳点是 P2(x)a1 +2a2x =0 的解,简化计算,其他插值公式参阅P51-52 (2)-(4)! 三点二次插值公式最常用.,! 迭代过程要点 ！,若任意取x1 x2 x3 三个点，,则求出的x* 可能位于给定区间之外或误差太大,最初的三个点x1 x2 x3 应构成一个两边高，中间低的“ 极小化框架” ， 即满足f1f2，f3f2 ，且两个等号不同时成立,极小化框架可由进退算法求得,在完成一次计算后，得到近似x*，,要进行搜索区间的收缩，然后在新区间中 重新构造三点组成的“ 极小化框架” ，有两种方法,终止准则：采用目标函数值的相对误差或绝对误差来判断,前进成功,极小化框架 x1 x2 x3,前进失败,x1,x2,极小化框架 x3 x2 x1,后退,h0,2h0,4h0,h0,h0,2h0,4h0,（三）进退算法（用于求“ 极小化框架”或初始搜索区间）,（四）逐次二次插值近似法的算法,初始点x1，h0，精度1，溢出下限2，步长缩短率m,二次插值法的优点：收敛速度较快，约为1.32阶,缺点：对强扭曲或多峰的，收敛慢，甚至会失败，故要求函数具有较好 的解析性能,（五） 二次插值法与黄金分割法的结合,2）用二次插值法逼近极小点 相邻三点的函数值: 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。,在新区间，相邻三点的函数值: 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.0520.2, 迭代终止。 xp*0.607, f*=0.243,由于fp0.2, 应继续迭代。,此例黄金分割法需要5次收缩区间，例,例 3-4 用二次插值法求 的极值点。初始搜索区间 ， 。,图,解：取x2点为区间x1,x3的中点， , 计算x1,x2,x3 3点处的函数值f1=19，f2=-96.9375，f3=124。可见函数值满足“高低高”形态。 以x1,x2,x3为插值点构造二次曲线， 求第一次近似的二次曲线p(x)的极小值点，由公式得。 ， 比较函数值可知 这种情况应消去左边区段 . 然后用 作为x1,x2,x3新3点,重新构造二次曲线p(x)，如此反复计算，直到 为止。整个迭代过程的计算结果列于表2-2. 从表中可见，经7次迭代后， ，终止迭代。故最优点,0.618法, 11次迭代, x*=3.9968; f*=-155.9996 高精度时差异更大！,要求计算导数的插值法,若目标函数f(x)可导，可通过解f (x)0求平稳点，进而求出极值点。 对高度非线性函数，要用逐次逼近求平稳点。,一、 Newton法,要求目标函数f(x)在搜索区间内具有二阶连续导数，且已知f (x)和f “(x)的表达式 。,（一） 基本思想,采用迭代法求(x)=0的根,xk+1,xk+2,(xk)=(xk)/(xk1xk),xk+1=xk(xk)/ (xk),用于求(x) f (x)0的根,xK+1=xkf (xk)/ f ”(xk),0,一点二次插值-切线法,牛顿法程序流程：,例题 用Newton法求解 初始点取 x0 = 1。（迭代三次）,解：f(x) 的一阶和二阶导函数为,迭代公式为 xK+1=xkf (xk)/ f ”(xk),第一次迭代： x0 = 1, f (x0)12, f ”(x0)36 x11(12)/361.33,第二次迭代： x1 = 1.33, f (x1)3.73, f ”(x1)17.6 x21.33(3.73)/17.61.54,(本例精确解为 x* ),第三次迭代： x2 = 1.54, f (x2)0.5865, f ”(x2) 12.76 x31.54(0.587)/12.761.586 f(x2)=15.1191,0.618法1，2上11次 x*=1.5795, f*=15.1194,例1： 求 min f (x)= arctan t d t 解： f (x) =arctan x , f (x)=1(1+ x2) 迭代公式： xk +1= xk - (1+ xk 2) arctan xk 取 x0= 1，计算结果： k xk f (xk) 1f(xk ) 1 1 0.7854 2 2 -0.5708 -0.5187 1.3258 3 0.1169 -0.1164 1.0137 4 -0.001095 -0.001095 5 7.9631e-010 x4 x* =0 取 x0=2，计算结果如下： 2 -3.535713.9510 -279.3441 1.2202e+005 不收敛！,线性收敛,二次收敛,Ex1：,Ex2：,(二) 优缺点,1、优点：收敛速度快；在f(x)=0的单根处，是2阶收敛；在f(x)=0的重根 处，是线性收敛。例,2、缺点：需要求二阶导数，若用数值导数代替，由于舍入误差将影响收敛 速度； 收敛性还依赖于初始点及函数性质。,! 通常在计算程序中规定最大迭代次数，当次数达到K还不能满足精度时， 则认为不收敛，要换一个初始点。,二、二点二次插值,x*,1) 割线法基本思想：用割线代替Newton法中的切线，并与区间消去法相结合。,c,P52 (3-14),P51 (3-12),2) 另一个二点二次插值(f(a)f(b)f(b)较割线法稍好,收敛速度都为1.618阶,通过检查区间两端导数来收缩区间 新区间两端点的导数值异号,基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值） 构造一个三次多项式P3(x)，用P3(x)的极小点近似目标函数的极小点x*,利用函数在两点的函数值和导数值：,三、 三次插值,三次插值法的收敛速度比二次插值法要快，达到2阶收敛速度。,求出：,极值的条件：,极值充分条件为：,将极值点方程带入上式,仅取正号,两种情形(A=0/A0)统一为:,其它形式,二点三次插值法一般流程：,编写程序应用时建议结合教材p55框图编写(嵌入进退法)，其更具普适性、鲁棒性。,教材P56-58的 D.S.C.法、Powell法及其组合法是区间搜索与二次插值法的结合！,P59-P64介绍了有理插值、连分式方法属特殊方法，含教材作者的一些研究成果，大家参阅教材，注意其适应条件，必要时课选用.,方法综述,（1）如目标函数能求二阶导数： 用Newton法 收敛快,（2）如目标函数能求一阶导数 ：首先考虑用三次插值法，收敛较快 对分法、收敛速度慢，但可靠 二次插值如割线法也可选择.,（3）只需计算函数值的方法 ： 首先考虑用二次插值法, 收敛快 黄金分割法收敛速度较慢，但可靠,作业,一、用黄金分割法求函数f(x)=3x