Abstract
In a series of recent papers, Oren, Oren and Luenberger, Oren and Spedicato, and Spedicato have developed the self-scaling variable metric algorithms. These algorithms alter Broyden's single parameter family of approximations to the inverse Hessian to a double parameter family. Conditions are given on the new parameter to minimize a bound on the condition number of the approximated inverse Hessian while insuring improved step-wise convergence.
Davidon has devised an update which also minimizes the bound on the condition number while remaining in the Broyden single parameter family.
This paper derives initial scalings for the approximate inverse Hessian which makes members of the Broyden class self-scaling. The Davidon, BFGS, and Oren—Spedicato updates are tested for computational efficiency and stability on numerous test functions, with the results indicating strong superiority computationally for the Davidon and BFGS update over the self-scaling update, except on a special class of functions, the homogeneous functions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C.G. Broyden, “Quasi-Newton methods and their application to functional minimization”,Mathematics of Computation 21 (1967) 368–381.
C.G. Broyden, “The convergence of a class of double rank minimization algorithms. 2. The new algorithm”,Journal of the Institute of Mathematics and its Applications 6 (1970) 222–231.
W.C. Davidon, “Optimally conditioned optimization algorithms without line searches”,Mathematical Programming 9 (1975) 1–30.
J.E. Dennis and J. More, “Quasi-Newton methods, motivation and theory”, Computer Science Report TR74-217, Cornell University (1974).
R. Fletcher, “A new approach to variable metric algorithms”,The Computer Journal 13 (1970) 317–322.
D. Goldfarb, “A family of variable-metric method derived by variational means”,Mathematics of Computation 24 (1970) 23–26.
D.H. Jacobson and W. Oksman, “An algorithm that minimizes homogeneous functions ofn variables inN + 2 iterations and rapidly minimizes general functions”, Technical Report 618, Division of Engineering and Applied Physics, Harvard University, Cambridge, MA, (1970).
G.P. McCormick and K. Ritter, “Methods of conjugate directions versus quasi-Newton methods”,Mathematical Programming 3 (1972) 101–116.
S.S. Oren, “Self-scaling variable metric algorithm. Part II”,Management Science 20 (1974) 863–874.
S.S. Oren, “On the selection of parameters in self-scaling variable metric algorithms”,Mathematical Programming 3 (1974) 351–367.
S.S. Oren and D.G. Luenberger, “Self-scaling variable metric algorithm. Part I”,Management Science 20 (1974) 845–862.
S.S. Oren and E. Spedicato, “Optimal conditioning of self-scaling variable metric algorithms”,Mathematical Programming 10 (1976) 70–90.
D.F. Shanno, “Conditioning of quasi-Newton methods for function minimization”,Mathematics of Computation 24 (1970) 647–656.
D.F. Shanno and K.H. Phua, “Minimization of unconstrained multivariate functions”,TOMS 2 (1976) 87–94.
E. Spedicato, “Computational experience with quasi-Newton algorithms for minimization problems of moderately large size”, Report CISE-N-175, CISE Documentation Service, Segrate (Milano) (1975).
D.F. Shanno and K.H. Phua, “Numerical comparison of several variable metric algorithms”, MIS Tech. Rept 21, University of Arizona (1977).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Shanno, D.F., Phua, K.H. Matrix conditioning and nonlinear optimization. Mathematical Programming 14, 149–160 (1978). https://doi.org/10.1007/BF01588962
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588962