Abstract
This paper studies the convergence properties of algorithms belonging to the class of self-scaling (SS) quasi-Newton methods for unconstrained optimization. This class depends on two parameters, say θ k and τ k , for which the choice τ k =1 gives the Broyden family of unscaled methods, where θ k =1 corresponds to the well known DFP method. We propose simple conditions on these parameters that give rise to global convergence with inexact line searches, for convex objective functions. The q-superlinear convergence is achieved if further restrictions on the scaling parameter are introduced. These convergence results are an extension of the known results for the unscaled methods. Because the scaling parameter is heavily restricted, we consider a subclass of SS methods which satisfies the required conditions. Although convergence for the unscaled methods with θ k ≥ 1 is still an open question, we show that the global and superlinear convergence for SS methods is possible and present, in particular, a new SS-DFP method.
Similar content being viewed by others
References
M. Al-Baali, “Analysis of a family of self-scaling quasi-Newton Methods,” Dept. of Mathematics and Computer Science, United Arab Emirates University, Tech. Report, 1993.
M. Al-Baali, “Variational quasi-Newton methods for unconstrained optimization,” JOTA, vol. 77 pp. 127–143, 1993.
R.H. Byrd, D.C. Liu and J. Nocedal, “On the behaviour of Broyden's class of quasi-Newton methods,” SIAM J. Optimization, vol. 2 pp. 533–557, 1992.
R.H. Byrd, J. Nocedal and Y. Yuan, “Global convergence of a class of quasi-Newton methods on convex problems,” SIAM J. Numer. Anal., vol. 24 pp. 1171–1190, 1987.
R.H. Byrd and J. Nocedal, “A tool for the analysis of quasi-Newton methods with application to unconstrained minimization,” SIAM J. Numer. Anal., vol. 26 pp. 727–739, 1989.
M. Contreras and R.A. Tapia, “Sizing the BFGS and DFP updates: A numerical study,” JOTA, vol. 78 pp. 93–108, 1993.
J.E. Dennis and J.J. Moré, “A characterization of superlinear convergence and its application to quasi-Newton methods,” Math. Comp., vol. 28 pp. 549–560, 1974.
J.E. Dennis and J.J. Moré, “Quasi-Newton methods, motivation and theory,” SIAM Rev., vol. 19 pp. 46–89, 1977.
R. Fletcher, Practical methods of optimization, Wiley, Chichester, England, 1987.
J. Nocedal and Y. Yuan, “Analysis of a self-scaling quasi-Newton method,” Math. Prog., vol. 61 pp. 19–37, 1993.
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,” Manage. Sci., vol. 20 pp. 845–862, 1974.
M.J.D. Powell, “Some global convergence properties of a variable metric algorithm for minimization without exact line searches,” in Nonlinear Programming, SIAM-AMS Proceedings vol. IX (R.W. Cottle and C.E. Lemke, eds.), SIAM Publications, 1976.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Al-Baali, M. Global and Superlinear Convergence of a Restricted Class of Self-Scaling Methods with Inexact Line Searches, for Convex Functions. Computational Optimization and Applications 9, 191–203 (1998). https://doi.org/10.1023/A:1018315205474
Issue Date:
DOI: https://doi.org/10.1023/A:1018315205474