两类下降的非线性共轭梯度法的全局收敛性毕业论文外文翻译.doc

《两类下降的非线性共轭梯度法的全局收敛性毕业论文外文翻译.doc》由会员分享，可在线阅读，更多相关《两类下降的非线性共轭梯度法的全局收敛性毕业论文外文翻译.doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、附录 中文译文两类下降的非线性共轭梯度法的全局收敛性王开荣，刘金魁(重庆大学数理学院信息与计算科学系，重庆，400030)摘要：本文基于文献1中提出的一类共轭梯度法，提出了两类新的非线性下降共轭梯度法。此两类算法能始终保持充分下降性，这一性质与算法所采用的线性搜索无关；对于一般的非凸函数，此两类算法在Wolfe线搜索条件下具有全局收敛性。关键词：无约束最优化；共轭梯度法；充分下降性；Wolfe线搜索；全局收敛性中图分类号：O224 AMS(2000)文章类别：65H10；9OC26文献标识码：A 文章编号：10019847(2008)04-0656-05本文的目的是在非精确线搜索下研究无约束优

2、化问题的两类新的非线性下降共轭梯度法的全局收敛性。考虑无约束优化问题 ， （1）其中 连续可微且梯度为。共轭梯度法求解（1）式的迭代公式： （2） （3）其中, 是搜索步长，是搜索方向，是一参数。参数的不同形式分别构成了FR，PRP共轭梯度法，它们分别为：其中是欧几里得范数。共轭梯度法的收敛性证明，通常使用非精确线搜索，如Wolfe线搜索和强Wolfe线搜索。Wolfe线搜索要求满足： ， （4） ， （5）其中。强Wolfe线搜索要求满足（4）式和 ， （6）其中。本文中提出了两类新的共轭梯度法，并用Wolfe线搜索证明了新方法的全局收敛性。于高航、赵艳林、魏增鑫提出了一种新的非线性共轭梯度

3、公式 其中（在本文中，我们把与有关的方法称为NCG法）。在Wolfe线搜索下证明了NCG算法具有全局收敛性。基于公式，本文提出了两类新的下降共轭梯度法： （7） （8）其中。为下降方向如果满足 ， ， （9）其中是正常数，（9）式表明共轭梯度法的全局收敛性。大多数文献证明了（9）式成立。定理 1 根据（2）式和（3）式，若，满足非精确线搜索，则对于任意的 （10）证明 若或，对于，由（3）式得否则，由（3）式和得由可知对于任意的，（9）式成立。 定理 2 根据（2）式和（3）式，若，满足非精确线搜索，则对于任意的 （11）证明 采用数学归纳法证明因为且，所以当时，结论成立。假设当 （，）时，结

4、论成立。只需证明时，结论仍成立。若对于，或，则由（3）式得否则，由（3）式、和得 鲍威尔定理证明了。基于充分下降的条件，Gilbert和Nocedal在Wolfe线搜索下证明了修正的PRP方法：具有全局收敛性，在新的公式中，同样证明了任一条件下。由的定义得由的定义和（11）式得为了证明新方法的全局收敛性，目标函数满足以下假设：假设（H）是有界集合，是初始点。）是的子集，连续可微且其梯度满足Lipchitz连续，即，存在常数使得 ， （12）由假设（H）可知，存在常数使得 ， （13）用来证明非线性共轭梯度法全局收敛的引理最初是由Zoutendijk给出，通常被称为Zoutendijk条件。引理

5、 1 假设（H）成立，在迭代公式（2）和（3）中满足，满足Wolfe线搜索，则 （14）引理 2 假设（H）成立，在迭代公式（2）和（3）中，满足Wolfe线搜索和（9）式，若存在常数使得 ， (15)则，可得。若令，则也可得引理 3 假设 ， （16）当或满足（*）式 1）存在常数，使得；2）存在常数，使得。证明 由（7）式和（16）式得定义，令，再由（12）式和（16）式得由（8）式、（9）式和（16）式得 定义，令，再由（12）式、（11）式和（16）式得引理 4 假设（H）成立，设和由（2）和（3）式迭代产生，满足Wolfe线搜索和（9）式，若使得（*）式和（15）式成立，则、和存在使

6、得，其中，表示的量。引理 5 假设（H）成立，设和由（2）和（3）式迭代产生，满足Wolfe线搜索和（9）式，若使得（*）式成立，则。引理2、引理4和引理5的证明在文献9中已给出，通过上述定理和引理，可得以下新方法的收敛结论。定理 3 假设（H）成立，设和由（2）和（3）式迭代产生，满足Wolfe线搜索和（10）式，由（7）式表示，则定理 4 假设（H）成立，设和由（2）和（3）式迭代产生，满足Wolfe线搜索和（11）式，由（8）式表示，则参考文献1 Yu Gaohang，Zhao Yanlin，Wei ZengxinA descent nonlinear conjugate gradien

7、t method for large-scale unconstrained optimizationJApplied Mathematics and Computation，2007，183：6366432 Fletcher R，Reeves CFunction minimization by conjugate gradientsJComputer Journal。1964，7：1491543 Polak E，Ribire GNote sulfa convergence de directions conjugatesJRev Francaise informat Recherche Op

8、eratinelle 3e Annee，1969，16：35 434 Polak B TThe conjugate gradient method in extreme problemsJUSSR ComputeMathMathPhys，19699：94 ll25 A1一Baali MDescent property and global convergence of the Fletcher-Reeves method with inexact line searchJIMAJNumerAna1，1985，5，121l246 Powell M J DNonconvex minimizatio

9、n calculations and the conjugate gradient methodALecture notes in Mathematics，1066CBerlin：Springer，1984：1221417 Gilbert J C，Nocedal JGlobal convergence properties of conjugate gradient methods for optimizationJSIAMJOptimization，19921：21428 Zoutendijk GNonlinear Programming，Computational Methods，in：I

10、nteger and Nonlinear ProgrammingM(Abadie Jed)，Amsterdam：North-Holland，1970：37869 Dai Y H，Yuan YNonlinear Conjugate Gradient Method(in Chinese)M。Shanghai：Shanghai Scientific8L Technical Publishers，2000，10：38 43附录 英文原文Global Convergence of Two Class of Descent Nonlinear Conjugate Gradient MethodsWANG

11、Kai-rong(王开荣)，LIU Jin-kui(刘金魁)(College of Mathematics and Physics, Chongqing University, Chongqing400030, china)Abstract：Based on a new nonlinear conjugate gradient method proposed in1，two classes of new nonlinear conjugate gradient methods are proposed to solve general unconstrained optimization pr

12、oblems which produce sufficient descent search direction at every iteration without any line searchUnder the Wolfe line searchwe prove the global convergence of the new methods for general no convex functionsKey words：Unconstrained optimization；Conjugate gradient method；Wolfe linesearch；Sufficient d

13、escent property；Global convergenceCLC Number：0224 AMS(2000)Subject Classification：65H10；9OC26Document code：A Article ID：10019847(2008)04-0656-05The object of this paper is to study the global convergence properties of two classes of new descent nonlinear Conjugate gradient methods for unconstrained

14、optimization problems with inexact line searchesW e consider the unconstrained optimization problem ， （1）whereis continuously differentiable and its gradient is denoted by gConjugate gradient methods for solving (1) are iterative formulas of the form: ， （2） （3）where, is a step length which is determ

15、ined by some line search, is the search direction andis a scalarWellknown formulas for are called FletcherReeves(FR)formula, PolakRibifrePolyak(PRP)formula，and they are given byRespectively, where is the Euclidean normIn the convergence analyses and implementations of conjugate gradient methods, one

16、 often requires the inexact line search such as the Wolfe line search of the strong Wolfe line search. The Wolfe line search requires satisfying: ， （4） ， （5）where.The strong Wolfe line search requires at satisfying(4)and ， （6）where.In this paper，we will propose two classes of new conjugate gradient

17、methods，and prove the globa1 convergence of the new methods with the Wolfe line searchGaohang Yu, Yanlin Zhao, Zengxin Wei1 proposed a new nonlinear conjugate gradient formula such as In which (in this paper，we call the corresponding method ofas the NCG method)They proved the global convergence of t

18、he NCG method with the Wolfe line searchBased on the formula , we propose two new descent conjugate gradient formulas such as （7） （8）where . is said sufficient descent if it satisfies , （9）where c is a positive constant(9) plays a vital role in guaranteeing the global convergence of conjugate gradie

19、nt methodsIn most references，we can see that(9)was always ensuredTheorem 1 Consider any method(2)and(3), where, satisfies some inexact line searchThen for all （10）Proof If or,for , then from (3)，we have0therwise。from (3)and ，we haveFrom ，we can deduce that(9)holds for all .Theorem 2 Consider any met

20、hod (2) and (3), where ，satisfies some inexact line search .Then for all , （11）Proof The conclusion can be proved by inductionSinceand，then the conclusion holds for . Now we assume that the conclusion is true for, for and. 0We need to prove that the result holds for .If or，for ,then from (3)，we have

21、 Otherwise, form（3）,and,we havePowell6 suggested that should not be less than zeroThis suggestion is useful to the PRP methodUnder the sufficient descent condition，Gilbert and Nocedal7 proved that the modified PRP methodis globally convergent with the Wolfe line searchFor the new formulas，we also pr

22、ove that they are always not less than zero under any conditionForm the definition of, we haveForm the definition of and（11）,we haveIn order to establish the global convergence result for the new methods，we assume that the objective function satisfies the following assumption：Assumption (H)i)The lev

23、el set is bounded，where is the starting pointii)In a neighborhood of,z)is continuously differentiable and its gradient g is Lipchitz continuous，namely，there exists a constant such that ， （12）From Assumption (H)，there exists a constant ，such that ， （13）The conclusion of the following lemma，often call

24、ed the Zoutendijk condition, is used to prove the global convergence of nonlinear conjugate gradient methods It was originally given by Zoutendij 8Lemma 1 Suppose that Assumption(H)holdsConsider any iteration of(2)and (3)，wheresatisfiesforandsatisfies the Wolfe line search. Then （14）Lemma 2 Suppose

25、that Assumption (H )holds Consider the method(2)and (3)，where , andsatisfies the Wolfe line search and(9)If there exists a constant, such that, for allThen we have.Let,then we also have.Lemma 3 Suppose that , for all (16)Then or has property (*), i.e.1) There exists a constant, such that;2) There ex

26、ists a constant, such that.Proof Firstly, form (7) and (16), we haveDefine, let,then from（12）and（16）, we also have .Secondly, form (8), (11) and (16), we haveDefine , let, then from（12）,（11）and（16）, we also have Lemma 4 Suppose that Assumption(H)holds Letandbe generated by (2) and (3), in which sati

27、sfies the Wolfe line search and (9). If has the property(*)and(15)holds, then，there exits , for any and for all , such that, where , denotes the number of the .Lemma 5 Suppose that Assumption(H)holdsLetandbe generated by (2)and(3)，in whichsatieties the Wolfe line search and(9)If 0 has the property(*

28、)，then .The proofs of Lemmas 2，4 and 5 had been given in9By the above theorems and lemmas，we have the following convergence results of the new methodsTheorem 3 Suppose that Assumption(H)holdsLetandbe generated by(2)and(3), in which a satisfies the Wolfe line search and (10), is computed by(7)，then.T

29、heorem 4 Suppose that Assumption(H)holdsLetandbe generated by(2)and(3)，in which a satisfies the Wolfe line search and(11)，is computed by(8)，thenReferences：1 Yu Gaohang，Zhao Yanlin，Wei ZengxinA descent nonlinear conjugate gradient method for large-scale unconstrained optimizationJApplied Mathematics

30、and Computation，2007，183：6366432Fletcher R，Reeves CFunction minimization by conjugate gradientsJComputer Journal。1964，7：1491543Polak E，Ribire GNote sur la convergence de directions conjugatesJRev Francoise informant Recherch Operationally 3e Annee，1969，16：35 434Polak B TThe conjugate gradient method

31、 in extreme problemsJUSSR ComputeMathMathPhys，19699：94 ll25A1一Baali MDescent property and global convergence of the Fletcher-Reeves method with inexact line searchJIMAJNumerAna1，1985，5，121l246Powell M J DNonconvex minimization calculations and the conjugate gradient methodALecture notes in Mathemati

32、cs，1066CBerlin：Springer，1984：1221417Gilbert J C，Nocedal JGlobal convergence properties of conjugate gradient methods for optimizationJSIAMJOptimization，19921：21428Zoutendijk GNonlinear Programming，Computational Methods，in：Integer and Nonlinear ProgrammingM(Abadie Jed)，Amsterdam：North-Holland，1970：37869Dai Y H，Yuan YNonlinear Conjugate Gradient Method(in Chinese)M。Shanghai：Shanghai Scientific & Technical Publishers，2000，10：38 43