第二章直线搜索

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

2、割法：适用于一般的函数。 （4）抛物线插值法抛物线插值法：适用于一般的连续函数。)(t)(t1 搜索区间的确定0tt*0tt*)(t 定义定义1：设 ，t*是 在L 上的 全局极小点。如果对于L上任取的两点t1和t2且t1 t2,均有：当t2t*时， ，当t1t*时， 则称 是区间L上的单谷函数单谷函数。 以下假设一元函数 是单谷函数。)(t)()(21tt)()(21tt11:RRL)(t单谷函数的性质单谷函数的性质： 设 是单谷函数极小点的一个搜索区间。在 (a,b)上任取两点t1，t2，使t1 t2,若 则 是 极小点的一个搜索区间；若 ，则 是 极小点的一个搜索区间。12( )()tt

3、)(t)()(21ttbt ,1)(t2,taba, 定义定义2： ，t*是 在L上的全局极小点。若找到 ,则称此区间t1，t2 为 的极小点的一个搜索区间搜索区间，记为 。 若t1t3 t2,也可将搜索区间 记为)(t2121*,tttLtLt使)(t21,tt21,tt231,ttt11:LRR 证明证明：利用反证法证明。对于后一种情况，即 。若 不是搜索区间，即 的极小点必在（a,t1)中。此时有t*t1t2, 根据单谷函数定义知： 矛盾。 故（t1,b)是搜索区间，同样可证前种情形。)()(21ttbt ,1)(t)()(21tt 单谷函数的这一性质可用来将搜索区间无限缩小，以至求到极

4、小点。 本章下面就介绍的直线搜索法，第一步就是要找一个初始搜索区间，下面就介绍一种有效的找初始搜索区间的 方法。2 比较 的值，转，)()(00htt和3若 ，比较 ，转 ， 。)()(00htt)()(00htt和)(t算法算法1：（搜索区间的确定）已知目标函数 。1 选择初始点t0和步长 h.令=t0+(2m-1-1)h,=t0+(2m-1)h,=t0+(2m+1-1)h, 2 , 1),) 12(0hhtk 4若 ，计算)()(00htt) 12() 12() 12(10010hththtmmm直到有某个m1使 确定了搜索区间，（实际应该为，放大）。但区间，是，的两倍长。（-=2（-）0

5、t （a)0t(b)t0 t0-h t0t0+h(c)因此只需比较和区间，的中点 的对应函数值，即可将区间，缩短1/3。由图(a),(b)可2 见，当 时，取，为搜索区间（图（a）。当 ，为搜索区间。（图(b)()()()( 当 ，取t0-h, t0, t0+h为搜索区间。)()(00tht 当 ，与4类似，计算 ， 直到有某个m（1）使 令=t0-(2m-1-1)h,=t0-(2m-1)h,=t0-(2m+1-1)h, =(+)/2,比较 ： 若 , 取,为搜索区间(图(d) 若 ,取,为搜索区间。)()(00tht,.2 , 1),) 12(0khtk)12()12()12(10010ht

6、hthtmmm)(),(rv)()(rv)()(rv(图(e)t0(d)t0(e) 上述过程的关键是开始时怎样选择步长h ，如选得太小,需迭代多次才能找到搜索区间，而若选得太大，虽然一次就能找到搜索区间，但给下一步找极小点过程增加了负担。 下面将介绍选择初始步长下面将介绍选择初始步长h的一种方法的一种方法。)(t 设 具有连续二阶偏导数，且 。现在要从t0出发确定一个搜索区间。在t0附近将 二次Taylor 展开： 令 )(t0)(, 0)(00 tt) 1 ()(21)()()()(200000ttttttttt ) 2(0)()(, 0)(000 ttttt则 由此解得 .(3) 这是 的

7、唯一极小点，可作为 极小点t*的一个近似。因此想到用 作为初始步长h。 但 中要计算二阶导数。一般来说计算二阶导数比较困难，而一阶导数即使较困难，也可用差分近似，因此，要想办法避免二阶导数的计算。)(/)(000tttt )(0t0tt )(tt 假设 的极小值可以估计出来，如为 ，即 若对某个 ，使得 ，则将 作为t*的一个近似。)(teet*)(tet)(t) 5 (0)()(000 tttt:)(21)5()4(0tt )()(2000tttte)6()()(2000tttthe则可取步长2000001( )( )()( )()(4)2ettt ttt t由（1）：这样就避免了二阶导数的

8、计算。) 7()(min)(1kkkkkkkkkptzztpzfptzf 在多维最优化问题时，若采用迭代计算法时，每次迭代要用直线搜索来确定下一个迭代点，每次迭代需要确定直线搜索的初始步长，如下面考察由Zk到Zk+1迭代的情况。 设已获得迭代点Zk，并按某种规则选定了向量Pk 为下降方向，并设 ，则 下一迭代点Zk+1由下述直线搜索确定的：1kP 令 ，则 则上述直线搜索（7）就是 从t=0出发的直线搜索，因而可按（6）确定初始步长h，但此时公式（6）中应令t0=0, 应该取f(z)极小值的估计值fe，即f(z*)fe，又 从而)()(kktpzftkTkkptpzft)()()(tekTkk

9、pzfzf)() 0(),() 0()8()(/)( 2kTkkepzfzffh 公式中没有绝对值符号，这是因为： 首先：下降方向Pk应选择满足 其次：估计值fe一般比真实值f(z*)偏小，从而 fe0.0)(kTkpzf 实际操作时可采用两种方案实际操作时可采用两种方案：一是一是下降迭代算法每次迭代均用（8）来确定初始步长，二是二是在第一次迭代 算法时用（8）而以后每次迭代初始步长均用 来计算。这是因为 一般是接近的。 因而用前依次迭代所走的距离作为下一次迭代的初始步长是合适的，计算经验表明，后一种方案更有效些。)9(1kkzzh11kkkkzzzz与 我们知道，在极小点 处， ，且 时，

10、递减，即 ，而当 ，函数递增，即 。若找到一个区间a,b,满足性质 则a,b内必有 的极小点 ，且 为找此 取 ，若 则在 中有极小点，这时用 作新的区间a,b，继续这个过程，逐步将区间a,b缩小，当区间a,b的长度充分小时，或者当 充分小时，即可将a,b的中点取做极小点的近似点，*t 0* t*tt t 0*t*tt 0t 0, 0ba t*t 0* t*t20bat 00 t0,t b0,t b 0t2 对分法 这个方法的特点是计算量较少，而且总能收敛到一个局部极小点，但收敛速度较慢。 这时有估计： 。至于区间a,b的确定，一般可采用下述方法： 22*abbat 有用。注意这种方法不仅对于

11、对分法有用，在后面方法中也 首先取初始点 ，若 ，则在 右方取点 ，（ 也是事先给定的步长）；若 则令 ；若仍然有 ，则取 （或将 放大一倍，即取 ）若 则以 作区间a,b；否则继续下去。 对于 的情况，可类似于上面在 左侧取点。0t 00 tttt01 01 t10,tbta 01 ttttt21221,tt 00t21ttt 20t0tt0t2. 。ttt013.若 ，则 ，若 ，则 ，转6；若 ，则 01 t1*tt 01 t10,ttba 01 t01:tt ，转2 。ttt:1.若 ，则 终止。若 转2，3 若 ，转4，5。 00t0*tt 00 t 00 t下面将对分法的过程叙述一

12、下： 0, 0,0tttt已知10,*4.5.,42,ttttttabbatt *11，110，110若 （t）=0,则t =t; 若 (t )0,tt ,转 。6.t=若则求出驻点，终止；否则转7,432,320,07.若 (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 a,b=0,3a+b t=1.5, (t)=-1.50,2 则a,b=1.5,2.25 . 则a,b=1.9921875,2.0039062a+

13、b t =2.0011392 (精确极小点：t=2,(2)=0,(2)0)11设： RR,在 已 获 得 的 搜 索 区 间 a,b内 具 有 连续 二 阶 导 数 ,并 且 已 得 出 其 一 阶 二 阶 导 数 的 表 达 式 ， 此时 利 用 高 等 数 学 学 过 的 切 线 法 将 能 很 快 地 求 出,（ t） =0的 一 个 根 。3Newton 切线法 ,(),(),(),()ttkktktktkNewton切 线 法 的 迭 代 公 式 是 ： 取 初 始 点 t,令 k=00, 1 .计 算 2 .求 tk+1* 3 .若 t-t,则 得 近 似 最 优 点 :t=t，

14、终 止 计 算 ， 否 则 转 4。k+1kk+1 4 .k+1:k,转 1.Newton迭代公式的推导： 方法一：设已给定极小点附近的一个点t ，因为一个二次0 连续可微函数在其极小点附近与二次函数很接近，则在 t 附近用二次函数逼近 (t)0 1(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 此 式 正 好 为 迭 代 公 式 。 .

15、,kk+1方法二：Newton法的几何解释如图： y= (t)在t 处的切线与t轴交点的 下一个点作为新的迭代点tt,(t)k+1tktk-1t,点敛点：1 在每次迭代时均要计算二阶导数，增加了工作量，而且用数值微分代替二阶导数时，舍入误差会影响收敛速度，特别是(t)很小时，更加严重。对于多元最优化问题，计算二阶导数涉及到Hesse阵，计算起来比较困难。Newton法的最大优是收速度快，但有不少缺2 方 法 对 初 始 点 的 依 赖 性 很 强 ， 初 始 点 不 能 选 得 离极 小 点 太 远 ， 否 则 所 得 极 小 化 序 列 是 发 散 的 ， 或 收敛 到 非 极 小 点 。

16、另 外 ： 要 求 函 数 二 阶 导 数 正 定 ，, ,即（ t） 0k3 ( ) ,.4 ( ) , .yta byta b当曲线在中有较复杂的弯曲时，这种方法往往失效即使曲线比较正常，在中或上凹或下凹，初始点也必须选择适当 黄金分割法适应于区间a,b上的任何单谷函数 (t)求极小点的问题.对函数除“单谷”外不作其他要求，甚至可以不连续，因此这种方法的适应面极广。其特点是只需要计算一个点的位置及其函数值,从而极大地减少了工作量.4 黄金分割法（0.618法）()2黄：在a,b内适当插入两点t ，t (t t ),1212将a,b分为三段，通过比较t )=， (t便可断定112极小点是在a

17、,t 内或者是在t ,b内，从而可用此小区间21取代a,b，将此缩小了的新区间记为a ,b .11 金分割的思路是()()又可在新的区间内取两点t t ,通过比较函数值t3433和t，即可得新的区间a ,b 如此做下去，最后便4422可定出近似的极小点. 怎样选择t ,t 呢?因为每次比较两点函数值区间都将缩小，12如果缩小的区间中保留的一点仍然用,那么除开始的区间要算两点的函数值外后面每一步只须计算一个函数值即可这样就节省了计算。,2,4)tt 假定每次迭代区间的长度按比例 缩小，(0 1)则经过一次迭代后的区间或者为:a,a+(b-a) ，或者为b-(b-a) ,b.由上面的分析知：应取t

18、 =b-(b-a)=a+(b-a)若下一个1新区间为a,a+(b-a) ,则:=a +(b -a )111 t =b -(b -a )a +(1-(b -a )31111112)4)t因:a =a,b =a+(b-a)则:t =a+ (1-(b-a),=a+(b-a) 113由于我们缩小区间是通过割去（t ,b而得到的,所以t 保留21在a,t 内. 又由于 (t )=a+(1-(b-a), 因而在新的21区间a ,b 中自然希望t 或t 与t 重合以便减少计算一个函数值.11341242)1,.15251012t 1331314141 因: t =a+(1-(b-a) t =a+ (1-(b

19、-a) =a+(b-a)那么 t 与t 重合便是1-= (1-不合理.故不能取t =t t 与t 重合便是1-= 0.618033988 此时t 与t 重合.)512)51232kk2k+12k+22k+1kkk2k+2kkk对于下一个新区间是a+(1-(b-a)，b的情形也可类似推出： 0.618033988 此时t 与t 重合.因此不管哪种情形，我们都有结论：在a ,b 确定后,就按下面方式取t,t t= a +(1-(b -a ) ta + (b -a )(其中0.618)():,:1():2():b ab a黄骤1 求：t =a+(1-(b-a)，t =a+ (b-a) t )= ，t

20、 )=121122a+b*2 若,求得近似极小点t =;若转323 若t ) (t则ta,bb,tt ,转5121211,若t )= (t则ta,tb转11212金分割法步：)(4 求t =a+(1-(b-a),t )=转21115 求t =a+ (b-a), t )=转22222.0015525432*例：min (t)=3t -16t +30t -24t+8 取 a,b=0,3 =0.618034 =0.001a+b 经9次迭代可得：t =25 抛物线插值法 上 面 我 们 介 绍 的 方 法 仅 对 诸 点 函 数 值 大 小 进 行 比 较 ， 而 函 数值 本 身 没 有 得 到 充

21、 分 利 用 ， 因 而 即 使 对 简 单 函 数 如 二 次 函 数 也 不得 不 像 一 般 函 数 一 样 进 行 同 样 多 的 函 数 值 计 算 ， 下 面 介 绍 抛 物 线插 值 法 ， 二 次 插 值 法 ， 利 用 函 数 在 已 知 点 的 值 来 确 定 新 的 迭 代 点 ，当 函 数 有 比 较 好 的 解 析 性 （ 如 连 续 可 微 ） 这 往 往 比 对 分 法 、 黄 金分 割 法 效 果 好 些 。 样抛线数数数点为点 与 Newton法 一，物法 也 是 用 二 次 函逼 近 原 函， 并 取二 次 函的 极 小 值作新 的 近 似，处点 处数阶 导

22、 数来数抛线个 点数来数不 同 之在 于 ： Newton法利 用 前 一的 函值 和 一 、 二值构 造 二 次 函，物法 利 用 前 三的 函值 构 造构 造 二 次 函。0011(), ()( ), ()()()()( )()()()()()( )()()()(ttttttttt012012010201212012021020首先，像黄金分割法一样，找点t ,t ,t 并使tt ,ttttt t ,t ,t 的确定按黄金分割法中求a,b的公式定，然后利用Lagrange插值公式构造二次函数：tt tttttt +tttt +22)()()()(), ( )(, ()ttt1201001122tttt 这是由三个点：（t ，t ）、(tt ）、tt定出的抛物线。222222001202211( )0() ( ) () ( ) () ( )2() ( ) () ( ) () ( )( ).,ttttttttt，12