第二章最优化方法——直线搜索

第二章直线搜索本章讨论的主要问题是解决这个问题的方法承为直线搜索或一维搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。在微积分中解的方法限于方程可以直接求解出来的情况。本章介绍的方法对不作严格要求，它可以很复杂，其导数可能不存在或者很难求出。当然对于可以求导数的情况，相应的方法也会简单些。)(mint1Rt11:RR)(mint0)(t本章将讨论以下四种直线搜索方法：（1）对分法：适用于的一阶导数连续并可以求出的情况。（2）Newton切线法：适用于的一阶导数和二阶导数都可求出的情况。（3）黄金分割法：适用于一般的函数。（4）抛物线插值法：适用于一般的连续函数。)(t)(t§1搜索区间的确定0tt*0tt*)(t定义1：设，t*是在L上的全局极小点。如果对于L上任取的两点t1和t2且t1t2,均有：当t2≤t*时，，当t1≥t*时，则称是区间L上的单谷函数。以下假设一元函数是单谷函数。)(t)()(21tt)()(21tt11:RRL)(t单谷函数的性质：设是单谷函数极小点的一个搜索区间。在(a,b)上任取两点t1，t2，使t1t2,若则是极小点的一个搜索区间；若，则是极小点的一个搜索区间。12()()tt)(t)()(21ttbt,1)(t2,taba,定义2：，t*是在L上的全局极小点。若找到,则称此区间[t1，t2]为的极小点的一个搜索区间，记为。若t1t3t2,也可将搜索区间记为)(t2121*,,tttLtLt使)(t21,tt21,tt231,,ttt11:LRR证明：利用反证法证明。对于后一种情况，即。若不是搜索区间，即的极小点必在（a,t1)中。此时有t*≤t1t2,根据单谷函数定义知：矛盾。故（t1,b)是搜索区间，同样可证前种情形。)()(21ttbt,1)(t)()(21tt单谷函数的这一性质可用来将搜索区间无限缩小，以至求到极小点。本章下面就介绍的直线搜索法，第一步就是要找一个初始搜索区间，下面就介绍一种有效的找初始搜索区间的方法。〈2〉比较的值，转3，4)()(00htt和〈3〉若，比较，转5，6。)()(00htt)()(00htt和)(t算法1：（搜索区间的确定）已知目标函数。〈1〉选择初始点t0和步长h.令μ=t0+(2m-1-1)h,ν=t0+(2m-1)h,ω=t0+(2m+1-1)h,2,1),)12((0hhtk〈4〉若，计算)()(00htt))12(())12(())12((10010hththtmmm直到有某个m≥1使确定了搜索区间{μ，ν，ω}（实际应该为{ν，ω}放大）。但区间[ν，ω]是[μ，ν]的两倍长。（ω-ν=2（ν-μ））0tμνγω（a)ν0tμγω(b)t0t0-ht0t0+h(c)因此只需比较ν和区间[ν，ω]的中点的对应函数值，即可将区间[μ，ω]缩短1/3。由图(a),(b)可2见，当时，取{μ，ν，γ}为搜索区间（图（a））。当{ν，γ，ω}为搜索区间。（图(b)))()()()(5当，取{t0-h,t0,t0+h}为搜索区间。)()(00tht6当，与〈4〉类似，计算，直到有某个m（≥1）使令μ=t0-(2m-1-1)h,ν=t0-(2m-1)h,ω=t0-(2m+1-1)h,γ=(μ+ν)/2,比较：若,取{ω,γ,ν}为搜索区间(图(d))若,取{γ,ν,ω}为搜索区间。)()(00tht,...2,1),)12((0khtk))12(())12(())12((10010hththtmmm)(),(rv)()(rv)()(rv(图(e))νt0μγω(d)t0μνγω(e)上述过程的关键是开始时怎样选择步长h，如选得太小,需迭代多次才能找到搜索区间，而若选得太大，虽然一次就能找到搜索区间，但给下一步找极小点过程增加了负担。下面将介绍选择初始步长h的一种方法。)(t设具有连续二阶偏导数，且。现在要从t0出发确定一个搜索区间。在t0附近将二次Taylor展开：令)(t0)(,0)(00tt)1())((21))(()()(~)(200000ttttttttt)2(0))(()(,0)(~000ttttt则由此解得…..(3)这是的唯一极小点，可作为极小点t*的一个近似。因此想到用作为初始步长h。但中要计算二阶导数。一般来说计算二阶导数比较困难，而一阶导数即使较困难，也可用差分近似，因此，要想办法避免二阶导数的计算。)(/)(~000tttt)(~0t0~tt)(tt~假设的极小值可以估计出来，如为，即若对某个，使得，则将作为t*的一个近似。)(teet*)(t~et)~(~t~)5(0)~)(()(000tttt:)~(21)5()4(0tt)())((2~000tttte)6()())((2~000tttthe则可取步长2000001()()()()()(4)2ettttttt由（1）：这样就避免了二阶导数的计算。)7()(min)(1kkkkkkkkkptzztpzfptzf在多维最优化问题时，若采用迭代计算法时，每次迭代要用直线搜索来确定下一个迭代点，每次迭代需要确定直线搜索的初始步长，如下面考察由Zk到Zk+1迭代的情况。设已获得迭代点Zk，并按某种规则选定了向量Pk为下降方向，并设，则下一迭代点Zk+1由下述直线搜索确定的：1kP令，则则上述直线搜索（7）就是从t=0出发的直线搜索，因而可按（6）确定初始步长h，但此时公式（6）中应令t0=0,应该取f(z)极小值的估计值fe，即f(z*)≈fe，又从而)()(kktpzftkTkkptpzft)()()(tekTkkpzfzf)()0(),()0()8()(/)]([2kTkkepzfzffh公式中没有绝对值符号，这是因为：首先：下降方向Pk应选择满足其次：估计值fe一般比真实值f(z*)偏小，从而fef(zk),即分子也为负值，故h0.0)(kTkpzf实际操作时可采用两种方案：一是下降迭代算法每次迭代均用（8）来确定初始步长，二是在第一次迭代算法时用（8）而以后每次迭代初始步长均用来计算。这是因为一般是接近的。因而用前依次迭代所走的距离作为下一次迭代的初始步长是合适的，计算经验表明，后一种方案更有效些。)9(1kkzzh11kkkkzzzz与我们知道，在极小点处，，且时，递减，即，而当，函数递增，即。若找到一个区间[a,b],满足性质则[a,b]内必有的极小点，且为找此取，若则在中有极小点，这时用作新的区间[a,b]，继续这个过程，逐步将区间[a,b]缩小，当区间[a,b]的长度充分小时，或者当充分小时，即可将[a,b]的中点取做极小点的近似点，*t0*t*ttt0*t*tt0t0,0bat*t0*t*t20bat00t0,tb0,tb0t§2对分法这个方法的特点是计算量较少，而且总能收敛到一个局部极小点，但收敛速度较慢。这时有估计：。至于区间[a,b]的确定，一般可采用下述方法：22*abbat有用。注意这种方法不仅对于对分法有用，在后面方法中也首先取初始点，若，则在右方取点，（也是事先给定的步长）；若则令；若仍然有，则取（或将放大一倍，即取）若则以作区间[a,b]；否则继续下去。对于的情况，可类似于上面在左侧取点。0t00tttt0101t10,tbta01ttttt21221,tt00t21ttt20t0tt0t2.。ttt013.若，则，若，则，转6；若，则01t1*tt01t10,,ttba01t01:tt，转2。ttt:1.若，则终止。若转2，3若，转4，5。00t0*tt00t00t下面将对分法的过程叙述一下：0,0,,,0tttt已知10,*4.5.,42,ttttttabbatt*11，110，110若（t）=0,则t=t;若(t)0,则[a,b]=[t,t],转6，若(t)0,tt,转。6.t=若则求出驻点，终止；否则转7,,432,320,,07.若(t)0,则t:a;若(t)0,则t:b,转6.例：用对分法求下面问题的极小值点：min(t)=3t-16t+30t-24t+8解：(t)=12(t-4t+5t-2)取t=0,t=1,=0.001(t)=(0)=-240,,((1)0),,101,,212,令t=t+t=1,(t)=(1)=0仅为驻点，令t=t+2t=3,(t)=(3)=480[a,b]=[0,3]a+bt==1.5,(t)=-1.50,2则[a,b]=[1.5,3],*,,,则[a,b]=[1.5,3]a+bt==2.25,(t)=4.68750,2则[a,b]=[1.5,2.25]...则[a,b]=[1.9921875,2.0039062]a+bt==2.0011392(精确极小点：t=2,(2)=0,(2)0)11设：RR,在已获得的搜索区间{a,b}内具有连续二阶导数,并且已得出其一阶二阶导数的表达式，此时利用高等数学学过的切线法将能很快地求出,（t）=0的一个根。3Newton切线法,,(),(),(),,()ttkktktktkNewton切线法的迭代公式是：取初始点t,令k=00,1.计算2.求tk+1*3.若t-t,则得近似最优点:t=t，终止计算，否则转4。k+1kk+14.k+1:k,转1.Newton迭代公式的推导：方法一：设已给定极小点附近的一个点t，因为一个二次0连续可微函数在其极小点附近与二次函数很接近，则在t附近用二次函数逼近(t)01(2,,()0,,()0tt,,,2(t)t)=(t)+(t)(t-t)+(t)(t-t)00000然后以(t)的极小点作为极小点的一个新的近似点t1由极值必要条件:(t)=01,,,即:(t)+(t)(t-t)=0即:t=t-001010此式正好为迭代公式。.,kk+1方法二：Newton法的几何解释如图：y=(t)在t处的切线与t轴交点的下一个点作为新的迭代点tt,(t)k+1tktk-1t,点敛点：1在每次迭代时均要计算二阶导数，增加了工作量，而且用数值微分代替二阶导数时，舍入误差会影响收敛速度，特别是(t)很小时，更加严重。对于多元最优化问题，计算二阶导数涉及到Hesse阵，计算起来比较困难。Newton法的最大优是收速度快，但有不少缺2方法对初始点的依赖性很强，初始点不能选得离极小点太远，否则所得极小化序列是发散的，或收敛到非极小点。另外：要求函数二阶导数正定，,,即（t）0k3()[,].4()[,].ytabytab当曲线在中有较复杂的弯曲时，这种方法往往失效即使曲线比较正常，在中或上凹或下凹，初始点也必须选择适当黄金分割法适应于区间[a,b]上的任何单谷函数(t)求极小点的问题.对函数除“单谷”外