Abstract
We study the self-scaling BFGS method of Oren and Luenberger (1974) for solving unconstrained optimization problems. For general convex functions, we prove that the method is globally convergent with inexact line searches. We also show that the directions generated by the self-scaling BFGS method approach Newton's direction asymptotically. This would ensure superlinear convergence if, in addition, the search directions were well-scaled, but we show that this is not always the case. We find that the method has a major drawback: to achieve superlinear convergence it may be necessary to evaluate the function twice per iteration, even very near the solution. An example is constructed to show that the step-sizes required to achieve a superlinear rate converge to 2 and 0.5 alternately.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T.M. Apostol,Mathematical Analysis (Addison-Wesley, Reading, MA, 1957).
R.H. Byrd, D.C. Liu and J. Nocedal, “On the behavior of Broyden's class of quasi-newton methods,” Report No. NAM 01, Department of Electrical Engineering and Computer Science, Northwestern University (Evanston, IL, 1990).
R.H. Byrd and J. Nocedal, “A tool for the analysis of quasi-Newton methods with application to unconstrained minimization,”SIAM Journal on Numerical Analysis 26 (1989) 727–739.
R.H. Byrd, J. Nocedal and Y. Yuan, “Global convergence of a class of variable metric algorithms,”SIAM Journal on Numerical Analysis 24 (1987) 1171–1190.
J.E. Dennis and J.J. Moré, “A characterization of superlinear convergence and its application to quasi-Newton methods,” Mathematics of Computation 28 (1974) 549–560.
J.E. Dennis and H. Wolkowicz, “Sizing and least change secant methods,” Technical Report, Department of Mathematical Sciences, Rice University (Houston, TX, 1991).
M. Lalee and J. Nocedal, “Automatic column scaling strategies for quasi-Newton methods,” Report No. NAM 04, Department of Electrical Engineering and Computer Science, Northwestern University (Evanston, IL, 1991).
D.G. Luenberger,Linear and Nonlinear Programming (Addison-Wesley, Reading, MA, 1984, 2nd ed.).
J.J. Moré, B.S. Garbow and K.E. Hillstrom, “Testing unconstrained optimization software,”ACM Transactions on Mathematical Software 7 (1981) 17–41.
S.S. Oren, “Perspectives on self-scaling variable metric algorithms,”Journal of Optimization Theory and Applications 37 (1982) 137–147.
S.S. Oren and D.G. Luenberger, “Self-scaling variable metric (SSVM) algorithms, part I: Criteria and sufficient conditions for scaling a class of algorithms,”Management Science 20 (1974) 845–862.
J.D. Pearson, “Variable metric methods for minimization,”Computer Journal 12 (1969) 171–178.
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. IX (SIAM, Philadelphia, PA, 1976) pp. 53–72.
M.J.D. Powell, “Update conjugate directions by the BFGS formula,”Mathematical Programming 38 (1987) 29–46.
D.F. Shanno and K.H. Phua, “Matrix conditioning and nonlinear optimization,”Mathematical Programming 14 (1978) 149–160.
D. Siegel, “Modifying the BFGS update by a new column scaling technique,” Technical Report, Department of Applied Mathematics and Theoretical Physics, Cambridge University (Cambridge, UK, 1991).
P. Wolfe, “Convergence conditions for ascent methods,”SIAM Review 11 (1969) 226–235.
P. Wolfe, “Convergence conditions for ascent methods II: some corrections,”SIAM Review 13 (1971) 185–188.
G. Zoutendijk, “Nonlinear programming, computational methods,” in: J. Abadie, ed.,Integer and Nonlinear Programming (North-Holland, Amsterdam, 1970) pp. 37–86.
Author information
Authors and Affiliations
Additional information
This work was supported by National Science Foundation Grant CCR-9101359, and by the Department of Energy Grant DE-FG02-87ER25047.
This work was performed while the author was visiting Northwestern University.
Rights and permissions
About this article
Cite this article
Nocedal, J., Yuan, Yx. Analysis of a self-scaling quasi-Newton method. Mathematical Programming 61, 19–37 (1993). https://doi.org/10.1007/BF01582136
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582136