A Look at the Tool of BYRD and NOCEDAL

Linghua Huang, Guoyin Li, Gonglin Yuan
DOI: 10.4236/ajcm.2011.14028                

Abstract

A power tool for the analysis of quasi-Newton methods has been proposed by Byrd and Nocedal ([1], 1989). The purpose of this paper is to make a study to the basic property (BP) given in [1]. As a result of the BP, a sufficient condition of global convergence for a class of quasi-Newton methods for solving unconstrained minimization problems without convexity assumption is given. A modified BFGS formula is designed to match the requirements of the sufficient condition. The numerical results show that the proposed method is very encouraging.

Keywords

Quasi-Newton Method, Unconstrained Minimization, Nonconvex Problem, Global Convergence

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. Byrd and J. Nocedal, “A Tool for the Analysis of Quasi-Newton Methods with Application to Unconstrained Minimization,” SIAM Journal on Numerical Analysis, Vol. 26, No. 3, 1989, pp. 727-739. doi:10.1137/0726042
[2]	M. J. D. Powell, “Some Global Convergence Properties of a variable Metric Algorithm for Minimization without Exact Line Searches,” In: R.W. Cottle and C. E. Lemke, Eds., Nonlinear Programming, SIAM-AMS Proceedings, Vol. 4, American Mathematical Society, Providence, 1976, pp.53-72.
[3]	J. Werner, “über die Globale Knovergenz von Variable- Metric-Verfahre mit Nichtexakter Schrittweitenbestim- mung,” Numerische Mathematik, Vol. 31, No. 3, 1978, pp. 321-334. doi:10.1007/BF01397884
[4]	R. Byrd, J. Nocedal and Y. Yuan, “Global Convergence of a Class of Quasi-Newton Methods on Convex Prob- lems,” SIAM Journal on Numerical Analysis, Vol. 24, No. 5, 1987, pp. 1171-1189. doi:10.1137/0724077
[5]	D. Li and M. Fukushima, “A Global and Superlinear Con- vergent Gauss-Newton-Based BFGS Method for Sym- metric Nonlinear Equations,” SIAM Journal on Numeri- cal Analysis, Vol. 37, No. 1, 1999, pp. 152-172. doi:10.1137/S0036142998335704
[6]	D. Li and M. Fukushima, “A Modified BFGS Method and Its Global Convergence in Nonconvex Minimiza- tion,” Journal of Computational and Applied Mathemat- ics, Vol. 129, No. 1-2, 2001, pp. 15-35. doi:10.1016/S0377-0427(00)00540-9
[7]	D. Li and M. Fukushima, “On the Global Convergence of the BFGS Method for Nonconvex Unconstrained Optimi- zation Problems,” SIAM Journal on Optimization, Vol. 11, No. 4, 2001, pp. 1054-1064. doi:10.1137/S1052623499354242
[8]	Z. Wei, G. Yu, G. Yuan and Z. Lian, “The Superlinear Convergence of a Modified BFGS-Type Method for Un- constrained Optimization,” Computational Optimization and Applications, Vol. 29, No. 3, 2004, pp. 315-332. doi:10.1023/B:COAP.0000044184.25410.39
[9]	G. Yuan and Z. Wei, “Convergence Analysis of a Modi- fied BFGS Method on Convex Minimizations,” Compu- tational Optimization and Applications, Vol. 47, No. 2, 2010, pp. 237-255. doi:10.1007/s10589-008-9219-0
[10]	E. G. Birgin and J. M. Martínez, “Structured Minimal- Memory Inexact Quasi-Newton Method and Secant Pre- conditioners for Augmented Lagrangian Optimization,” Computational Optimization and Applications, Vol. 39, No. 1, 2008, pp. 1-16. doi:10.1007/s10589-007-9050-z
[11]	G. Yuan and Z. Wei, “The Superlinear Convergence Ana- lysis of a Nonmonotone BFGS Algorithm on Convex Ob- jective Functions,” Acta Mathematics Sinica, Vol. 24, No. 1, 2008, pp. 35-42. doi:10.1007/s10114-007-1012-y
[12]	A. Griewank, “On Automatic Differentiation,” In: M. Iri and K. Tanabe, Eds., Mathematical Programming: Re- cent Developments and Applications, Academic Publish- ers, Cambridge, 1989, pp. 84-108.
[13]	Y. Dai and Q. Ni, “Testing Different Conjugate Gradient Methods for Large-Scale Unconstrained Optimization,” Journal of Computational Mathematics, Vol. 21, No. 3, 2003, pp. 311-320.