第十七章线搜索

1、第十七章直线搜索本章讨论的主要问题是min （t）:R1 R1解决这个问题的方法承为直线搜索或一维搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。在微积分中解min （t）的方法限于方程 （t） 0可以直接求解出来的情况。本章介绍的方法对 不作严格要求，它可以很复杂，数导数可能不存在或者很难 求出。当然对于可以求导数的情况，相应的方法也会简单些。本章将讨论以下四种直线搜索方法：（1）对分法：适用于（t）的一阶导数连续并可以求出的情况。（2） Newton切线法：适用于 的一阶导数和二阶导数都可求出的情况。（3）黄金分割法：适用于一般的函数。（4）抛物线

2、插值法：适用于一般的连续函数。17.1搜索区间的确定定义17.1.1:设：L R1R1 , t*是 在L上的全局极小点。如果对于L上任取的两点t1和t2且t1 t2,均有：当t20t*时，（L） 他），当tt*时，（L）&）则称（t）是区间L上的单谷函数。t1t2,则称此区问定义L,t2L,使 L t*以下假设一元函数 （t）是单谷函数。图 17.1.1t*是（t）在L上的全局极小点。若找到 t1, t2为（t）的极小点的一个搜索区间,记为 t1,t2 。若t1t3 t2,也可将搜索区间t1,t2记为t1,t3,t2单谷函数的性质：设a,b是单谷函数极小点的一个搜索区间。 在（a,b）上任取两

3、点t1, t2,使t1 t2,若（t） &）则a,t2是（t）极小点的一个搜索区间；若（t） &）,则t1,b 是 极小点的一个搜索区间。证明：利用反证法证明。对于后一种情况，即（3）心）。若b不是搜索区间，即（t）的极小点必在（a,t1）中。此时有t*&t1t2,根据单谷函数定义知:(tl) (t2)矛盾故(t1,b)是搜索区间，同样可证前种情形。单谷函数的这一性质可用来将搜索区间无限缩小，以至求到极小点。本章下 面就介绍的直线搜索法，第一步就是要找一个初始搜索区间，下面就介绍一种有 效的找初始搜索区间的方法。算法1：(搜索区间的确定)已知目标函数 (t)1选择初始点to和步长h.2比较(t

4、o)和(to h)的值，转 , 3若(to)(toh),比较 (to)和(to h),转,。4若(to)(toh),计算(to (2k1)h),h 1,2,，直到有某个m1 使(to (2m1 1)h) (to (2m 1)h) (to (2m1 1)h)令尸to (2m1 1)h, v= to (2m 1)h,co=to (2m 1 1)h放大)。但区间V ,就确定了搜索区间 & V,(实际应该为 V ,的两倍长。(-V =2 ( v - N)(b)图 17.1.2(c)因此只需比较V和区间 卜，的中点 的对应函数值，即可将区间2g缩短1/3。由图(a),(b)可见，当()()时，取山丫的搜

5、索区间(图(a)。当()()v, 丫为搜索区间。(图(b)当(toh)(to),取t0-h, t0, t0+h为搜索区间。当(toh)(to),与4类似，计算(to (2k1)h),k 1,2,.,直到有某个 m(1)使(to (2m1 1)h)(to (2m 1)h) (to (2m1 1)h)0令尸to (2m1 1)h,v=t (2m 1)h,co=to (2m 1 1)h y=(n+v)/2,比较(v), (r)：若(v)(r),取，t,v为搜索区间(图(d)若(v)(r),取 丫，v e为搜索区间。(图(e)1,(d)(e)图 17.1.3上述过程的关键是开始时怎样选择步长h ,如选

6、得太小，需迭代多次才能找到搜索区间，而若选得太大，虽然一次就能找到搜索区间，但给下一步找极小点 过程增加了负担。下面将介绍选择初始步长h的一种方法。设(t)具有连续二阶偏导数，且(to) 0, (to) 00现在要从t0出发确定一个搜索区间。在to附近将(t)二次Taylor展开：(to)(t to)2(1) TOC o 1-5 h z 1 HYPERLINK l bookmark10 o Current Document (t)(t0)(t0)(tt0) 2令 (t) 0,则(to) (to)(tto)0 (2)由此解得 t0(t0)/ (t0) .(3)这是(to)的唯一极小点，可作为 (

7、t)极小点t*的一个近似。因此想到用 t to作为初始步长h但to中要计算二阶导数。一般来说计算二阶导数比较困难，而一阶导数即使 较困难，也可用差分近似，因此，要想办法避免二阶导数的计算。假设(t)的极小值可以估计出来,如为e,即(t*) e若对某个 ，使得(t) e，则将作为t*的一个近似由(1):(to)1(to)(t%to) 2(to)(% to)2eL (4)(to) (to)(tto)0 (5)(4) (5)2(tto)： tto2( e(to)则可取步长ht to2(to)e (to)(to)(6)这样就避免了二阶导数的计算。在多维最优化问题时，若采用迭代计算法时，每次迭代要用直线

8、搜索来确定 下一个迭代点，每次迭代需要确定直线搜索的初始步长，如下面考察由Zk到Zk+1 迭代的情况。设已获得迭代点Zk,并按某种规则选定了向量 Pk为下降方向，并设|Pk 则下一迭代点Zk+1由下述直线搜索确定的：f(Zk tkPk) min f(Zk tpj k Pk令(t) f(Zk tpk) ,则 (t)f (Zk tPk)T Pk则上述直线搜索(7)就是(t)从t=0出发的直线搜索，因而可按(6)确定 初始步长h,但此时公式(6)中应令t0=0, e应该取f(z)极小值的估计值fe, 即 f(z*)= fe , 又 (0) f(zj (0)f (Zk)T pk从 而h 2fe g/

9、f(Zk)T Pk(8)公式中没有绝对值符号，这是因为：首先：下降方向Pk应选择满足f(Zk)T Pk 0其次：估计值fe一般比真实值f(Z*)偏小，从而fe0.实际操作时可采用两种方案：一是下降迭代算法每次迭代均用(8)来确定初始步长，二是在第一次迭代算法时用(8)而以后每次迭代初始步长均用h| ZkZki|(9)来计算。这是因为| Zkiz与Zk一般是接近的。因而用前依次迭代所走的距离作为下一次迭代的初始步长是合适的，计算经验表明，后一种方案更有效些。17.2 对分法这个方法的特点是计算量较少，而且总能收敛到一个局部极小点，但收敛速 度较慢。我们知道，在极小点t*处，t*0,且t t*时，

10、t递减，即t*0,而当t t* ,函数递增，即 t 0。若找到一个区间a,b,满足性质 a 0, b 0。则a,b内必有 t的极小点t* ,且t*0为找此t* ,取t。b ,若2t00则在a,t0中有极小点，这时用a,t0作新的区间a,b,继续这个过程，逐步将区间a,b缩小，当区间a,b的长度充分小时，或者当t0充分小时，即可将a,b的中点取做极小点的近似点，这时有估计:至于区间a,b的确定，一般可采用下述方法：首先取初始点to ,若 t0 0 ,则在t0右方取点ti t0 t , ( t也是事先给 定的步长)；若ti 0,则令a t0,b ti；若仍然有 t0 0,则取t2 ti t(或 将

11、t放大一倍，即取12 t1 2 t),若 t2 0则以ti,t2作区间a,b;否则继 续下去。对于t00的情况，可类似于上面在t左侧取点。注意这种方法不仅对于对分法有用，在后面方法中也有用。下面将对分法的 过程叙述一下：已知：t , t ,t0, t 0,01)若 t 0,则t t0终止。若t00转2), 3)若t00,转 4), 5)。2) ti t t 3)右 t 0 ,则 tti ,右 ti 0 ,则 a,bt0,ti ,转 6);若 ti 0 ,则 ti : to; t t: t,转 2) 04 ti t0t5)若(3) =0,则t*二t1；若(t i)0,t i t0, t tt,转

12、4)。a bt=，则求出驻点t* t,终止；否则转7)若b7)若若2(t)0,则 t: b,转6。例i7.2.i：用对分法求下面问题的极小值点: min (t)=3t 4-i6t 3+30t 2-24t+8解： ,(t)=i2(t 3-4t 2+5t-2)取 t0=0, t=i, =0.00i(t 0)= (0)=-240a,b=0,3a+bt= =i.5,(t)=-i.50,则a,b=i.5,2.25 贝 U a,b=i.992i875,2.0039062* a+b 一 一t =- =2.00ii392( 精确极小点：t=2,(2)=0,(2)0)17.3 Newton 切线法设：R1R1,

13、在已获得的搜索区间a,b内具有连续二阶导数，并且已得出其一阶二阶导数的表达式，此时利用高等数学学过的切线法将能很快地求 出(t) =0的一个根。Newton线法的迭代公式是：取初始点品,令k=0t计算,(tk),求 t k+1 tk若t*=tk+1 -t k1),&),(tk)，则得近似最优点k+1,终止计算，否则转k+1: k,转1)。4) oNewton迭代公式的推导：方法一：设已给定极小点附近的一个点 极小点附近与二次函数很接近，则在t0,因为一个二次连续可微函数在其10附近用二次函数逼近 12(t)一(t)= (t 0)+ ,(t 0)(t-t 0)+ 万 ,(t 0)(t-t 0)2

14、然后以7t)的极小点作为极小点的一个新的近似点t1由极值必要条件：-(t 1)=0即： (t 0)+ ,(t 0)(t 1-t 0)=0即：t1=t-T,(t。)此式正好为迭代公式。方法二：Newton法的几何解释如图：图 17.3.1y= ，(t)在tk处的切线与t轴交点的下一个点作为新的迭代点t k+1.Newton法的最大优点是收敛速度快，但也有不少缺点：1 ) 在每次迭代时均要计算二阶导数，增加了工作量，而且用数值微分代替二阶导数时，舍入误差会影响收敛速度，特别是,(t) 很小时，更加严重。对于多元最优化问题，计算二阶导数涉及到Hesse阵，计算起来比较困难。2)方法对初始点的依赖性很

15、强，初始点不能选得离极小点太远，否则所得极小化序列是发散的，或收敛到非极小点。另外：要求函数二阶导数正定，即 (, t k) 0。3)当曲线 y= ,(t) 在 a,b 中有较复杂的弯曲时，这种方法往往失效。4 )即使曲线y=,(t)比较正常，在 a,b 中或上凹或下凹，初始点也必须选择适当。17.4黄金分割法黄金分割法适应于区间 a,b 上的任何单谷函数(t) 求极小点的问题 .对函数除 “ 单谷” 外不作其他要求，甚至可以不连续，因此这种方法的适应面极广。其特点是只需要计阵一个点的位置及其函数值, 从而极大地减少了工作量。黄金分割的思路是：在a,b内适当插入两点3, t2(tit2),将a

16、,b分为三段，通过比较(t1)= 1， (t 2)2便可断定极小点是在a,t 2 内或者是在t 1,b 内，从而可用此小区间取代a,b ，将此缩小了的新区间记为 a 1,b1.又可在新的区间内取两点 t 3t4, 通过比较函数值(t 3)3和 (t4)4，即可得新的区间 a2,b2 如此做下去，最后便可定出近似的极小点 .怎样选择 t 1,t 2呢?因为每次比较两点函数值区间都将缩小，如果缩小的区间中保留的一点仍然用 , 那么除开始的空间要阵两点的函数值外后面每一步只须计阵一个函数值即可这样就节省了计阵。假定每次迭代区间的长度按比例 缩小， (0 D，则t： a,b ：b,t 2:3，2 ：1

17、,转5)若(t1)= (t 2),则t1 ： a,t 2:b转 1)4)求t1二a+(1- )(b-a), (t)=转2 )5)求t2=a+ (b-a), (t2)= 2转2)。例 17.4.1: min (t)=3t 4-16t 3+30t 2-24t+8解：取a,b=0,3经过9次迭代可得:=0.618034=0.001* a+bt =2.001552517.5抛物线插值法上面我们介绍的方法仅对诸点函数值大小进行比较，而函数值本身没有得到充分利用，因而即使对简单函数如二次函数也不得不像一般函数一样进行同样多 的函数值计算，下面介绍抛物线插值法，二次插值法，利用函数在已知点的值来 确定新的迭

18、代点，当函数有比较好的解析性(如连续可微)这往往比对分法，黄 金分割法效果好些。与Newton法一样，抛物线法也是用二次函数逼近原函数，并取二次函数的极小值点作为新的近似点，不同之处在于：Newton法利用前一点处的函数值和一、二阶导数值来构造二次函数，抛物线法利用前三个点的函数值构造 来构造二次函数。 TOC o 1-5 h z 首先，像黄金分割法一样，找点 10,t 1,t 2并使t0 (t1,t 2),(t 0)(t1),(t0) (t2)； t0，t 1，t 2的确定按黄金分割法中求a,b的公式定，然后利用Lagrange插值公式构造二次函数：飞)(tt1)(t(t0)+(tt。)(t

19、i)+ (tt0)(t t1)(t2)(tot 1 )(t0t 2) (tlt o)(tl t 2) (t2t 0)(t2 t 1 )这是由三个点：(t0, (t。)、(t 1, (t1)、(t2, (t2)定出的抛物线。求其极小点：f(t) 0t 2t 2tt 2t 2 tt 2t 2t设：t= (t1t2)(to)(t2t0) (t1)(t0t1)(t2)作为(t)的近似极小点。2(tl t2) (to) (t2 to) (t1) (to t1) (t2)若区间长度t2 t1充分小，则lt-t 密若 tot,取 t1,=t1.t o=t.t 2,=to 即可若 toT 取 t1,=to.t o,=ft 2,=t2 即可)若(to) 取 t1,=t o,=to，t2,=t2若 to o :2t：to,： o,转2,o： o,t： ti,：，转 2)若to