《无约束优化问题的最速下降方向的步长计算》由会员分享，可在线阅读，更多相关《无约束优化问题的最速下降方向的步长计算（4页珍藏版）》请在金锄头文库上搜索。
1、无约束优化问题的最速下降方向的步长计算吴淑芳(长春光学精密机械学院计算机系)摘 要 一般地,无约束优化问题的最速下降方向的步长计算由近似估计得到。本 文给出一种计算步长的方法,此方法的优点为:若在此下降方向上解存在,那么新 方法以较少的计算量确定解的存在区间(基于01618法) ;及在局部计算时,用约2/ 3的一维差分Newton法的计算量求得在下降方向上误差精度充分高的近似解 (基于二次多项式逼近法)。关键词 无约束优化;最速下降法;二次多项式逼近法考虑无约束优化问题minxRnf ( x)(1)这里xRn为自变量, f : RnR为充分光滑函数。问题(1)的主要数值求解方法为 最速下降法。
2、若给定下降方向d = -f ( x) ,步长t+为min t 0f ( x + td)的解的计算很重要。 由于问题(1)的函数性质不好,步长的选取可能直接影响求解问题(1)的算法的收敛性。 但一般地,由于精确计算步长的计算量较大,因此均用近似法估计步长。若在Rn上任取一 点x ,给定一个下降方向d ,如何以较少的计算量计算步长t+使之为min t 0f ( x + td)的解是一 个不很清楚的问题。 本文对一般的函数f ( x)及任给Rn上的初始点x ,给出一种计算步长t+ 的解区间估计及快速局部求解t+的技巧。 算法1 (最速下降迭代法) (0)给定初始点x及误差精度0,计算最速下降方向d(
3、 x) = -f ( x); (1)计算步长t+使之为min t 0f ( x + td( x) )的解;(2)设x= x + t+d( x) ;(3)若x为问题(1)的近似解,则停止;否则计算最速下降方向d (x) ,转(1)。 设g( t) = f ( x + td( x) ) ,那么t+的求解,转化为一维优化问题。 首先我们用外推01618 法估计min t 0g( t)的一个局部解存在区间,然后用01618法收缩其解存在区间(亦可类似地用Fibonacci方法)。在节3中,我们比较割线法与二次多项式拟合法的效率,指出对于大型的 问题(1)宜用快速的二阶多项式拟合方法局部计算min t
4、0g( t)的解t+。在节4中,我们给出数值例子,发现Newton法比割线法调用的函数值个数略多,而二次多项式法约为上述二种 方法调用函数值个数的2/3,这对f ( x)的计算量大的问题是非常有价值的。收稿日期: 1997 - 09 - 20第22卷第1期长春光学精密机械学院学报Vol. 22 No. 11 9 9 9年3月J. CHANGCHUN INST. OPT.若k 1,取解区间为 tk-2, tk 。命题2 若g(t1)g(t0) ,那么min t 0g(t)在t0,t1 上存在解;若g(tk)g(tk+1)且g(tk+1)g(tk+2) ,那么min t 0g(t)在区间tk,tk
5、+2 上存在解。算法3 (01618法)(0)给定误差精度0及t00g( t)下面讨论二次多项式逼近法,若g( t)为三次连续可微函数,任给t00g( t)的二次多项式逼近算法。算法4(二次多项式逼近法)(0)给定点t00;(1)由式(3)计算参数a , b , c及t =-b 2c及计算 ?g = g( t) ;(2)取( t0, t1, t2) = ( t1, t2,?t)及( g0, g1, g2) = ( g1, g2,?g) ,若| t1- t2| , |g1-g2 t1-t2| 0g(t)的一个解在t3点达到g(t3)0 ,且g(t)在t3上连续有界,任给t3附近三个点(ti ,g
6、i) ,i = 0 ,1 ,2为初始点满足式(4) ,即| t2- t3| | t1- t3| 2| t0- t3|其中 (0 ,1)为一常数。那么由算法4得到的迭代点tk k = 0收敛到t3,且其收敛速度为2步平方收敛。 证明 由(3)知?t =-b 2c=-g2-g1 t2-t1 2c+t2+ t1 2=t2+ t1 2-g2-g1 t2-t1 2 t1-t0g2-g1 t2-t1-g2-g0 t2-t0利用Taylor展开及g( t3) =0有g0= g3+1 2g( t3) ( t0-t3)2+1 6g(0) ( t0-t3)3g1= g3+1 2g( t3) ( t1-t3)2+1
7、 6g(1) ( t1-t3)3g2= g3+1 2g( t3) ( t2-t3)2+1 6g(2) ( t2-t3)3这里i t3+( ti-t3) 0,1 ,于是有g2-g1 t2-t1=1 2g( t3) ( t1+ t2-2t3) + R2114第1期吴淑芳:无约束优化问题的最速下降方向的步长计算g2-g0 t2-t0=1 2g( t3) ( t2+ t0-2t3) + R20这里R21=g(2) ( t2-t3)3-g(1) ( t1-t3)3t2-t1,R20=g(2) ( t2-t3)3-g(0) ( t0-t3)3t2-t0整理后得 g2-g1 t2-t1-g2-g0 t2-t
8、0=1 2g( t3) ( t1-t0) + R21-R20因此有 ?t =t1+ t2 2=1 2g( t3) ( t1+ t2-2t3) + R21g( t3) +2 t1-t0( R21-R20)若 0,)使| t2-t3| t1-t3|2| t0-t3| ,那么R21= O ( t1-t3)2, R20= O ( t0-t3)2。此时有 ?t =t1+ t2 2-1 2( t1+ t2-2t3) + O | t1-t3|2,故有 | t -t3| = O | t1-t3|2(5)式(5)亦说明当ti, i =0,1,2充分接近t3时,由算法4得到的点列tk k =0具有Q -线性收敛到
9、解t3的性质,此外存在0使得| tk+3- t3| | tk+1- t3|2,即2-步平方收敛到t3。参考文献1 Dennis J E , Schnabel R B. Numeri cal Methods for Unconstrained Optimization and Nonlinear EquationsPrentice - Hall ,Inc Englewood ,New Tersey ,19832 刘光辉,韩继业.带一类非精确搜索的Broyden族的全局收敛性.计算数学,1996(3) ,234240 Solving Step - length of Large - Operati
10、on Minimazation ProblemsW u Shuf ang( Dep. of Computer , Changchun Inst. Optics and Fine Mech. )Abstract In this paper. we present a method for solving step2length in a decrease direction ofLarge - operation minimization problems ,the method possesses two properties; (i) if there existsolutions in t
11、his decrease direction ,then we can find a solution interval (based on 01618 method ) ;(ii) this method using two2times polynonial approximation for finding a local solution in thisdecrease dorection ,and we showthe operations of new method the operations of difference Nowton method=2 3.Key words Large2operation minimization problem; Decrease diraction ; Two2times polynomialmethod24长春光学精密机械学院学报1999年
