Self-scaling variable metric algorithms without line search for unconstrained minimization
HTML articles powered by AMS MathViewer
- by Shmuel S. Oren PDF
- Math. Comp. 27 (1973), 873-885 Request permission
Corrigendum: Math. Comp. 28 (1974), 887.
Corrigendum: Math. Comp. 28 (1974), 887.
Abstract:
This paper introduces a new class of quasi-Newton algorithms for unconstrained minimization in which no line search is necessary and the inverse Hessian approximations are positive definite. These algorithms are based on a two-parameter family of rank two, updating formulae used earlier with line search in self-scaling variable metric algorithms. It is proved that, in a quadratic case, the new algorithms converge at least weak superlinearly. A special case of the above algorithms was implemented and tested numerically on several test functions. In this implementation, however, cubic interpolation was performed whenever the objective function was not satisfactorily decreased on the first "shot" (with unit step size), but this did not occur too often, except for very difficult functions. The numerical results indicate that the new algorithm is competitive and often superior to previous methods.References
- Yonathan Bard, On a numerical instability of Davidon-like methods, Math. Comp. 22 (1968), 665–666. MR 232533, DOI 10.1090/S0025-5718-1968-0232533-5
- C. G. Broyden, Quasi-Newton methods and their application to function minimisation, Math. Comp. 21 (1967), 368–381. MR 224273, DOI 10.1090/S0025-5718-1967-0224273-2
- C. G. Broyden, The convergence of a class of double-rank minimization algorithms. II. The new algorithm, J. Inst. Math. Appl. 6 (1970), 222–231. MR 433870 A. R. Colville, A Comparative Study on Nonlinear Programming Codes, IBM Tech. Rep. No. 320-2949, 1968. W. C. Davidon, Variable Metric Method for Minimization, A.E.C. Research and Development Rep. ANL-5990 (Rev.), 1959.
- William C. Davidon, Variance algorithm for minimization, Comput. J. 10 (1967/68), 406–410. MR 221738, DOI 10.1093/comjnl/10.4.406
- L. C. W. Dixon, Variable metric algorithms: necessary and sufficient conditions for identical behavior of nonquadratic functions, J. Optim. Theory Appl. 10 (1972), 34–40. MR 309305, DOI 10.1007/BF00934961
- R. Fletcher and M. J. D. Powell, A rapidly convergent descent method for minimization, Comput. J. 6 (1963/64), 163–168. MR 152116, DOI 10.1093/comjnl/6.2.163 R. Fletcher, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317-322.
- P. E. Gill and W. Murray, Quasi-Newton methods for unconstrained optimization, J. Inst. Math. Appl. 9 (1972), 91–108. MR 300410
- A. A. Goldstein, On steepest descent, J. SIAM Control Ser. A 3 (1965), 147–151. MR 184777
- J. Greenstadt, Variations on variable-metric methods. (With discussion), Math. Comp. 24 (1970), 1–22. MR 258248, DOI 10.1090/S0025-5718-1970-0258248-4
- Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0175290
- H. Y. Huang, Unified approach to quadratically convergent algorithms for function minimization, J. Optim. Theory Appl. 5 (1970), 405–423. MR 288939, DOI 10.1007/BF00927440
- L. V. Kantorovič and G. P. Akilov, Funktsional′nyĭ analiz v normirovannykh prostranstvakh, Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow, 1959 (Russian). MR 0119071 D. G. Luenberger, Introduction to Linear and Nonlinear Programming, Addison-Wesley, Reading, Mass., 1973.
- B. A. Murtagh and R. W. H. Sargent, A constrained minimization method with quadratic convergence, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 215–245. MR 0284213 S. S. Oren, Self-Scaling Variable Metric Algorithms for Unconstrained Minimization, Ph.D. Thesis, Department of Engineering-Economic Systems, Stanford University, Stanford, Calif., 1972. S. S. Oren & D. G. Luenberger, The Self-Scaling Variable Metric Algorithm, Proc. Fifth Hawaii International Conference on System Sciences, January, 1972.
- Shmuel S. Oren and David G. Luenberger, Self-scaling variable metric (SSVM) algorithms. I. Criteria and sufficient conditions for scaling a class of algorithms, Management Sci. 20 (1973/74), 845–862. Mathematical programming. MR 388773, DOI 10.1287/mnsc.20.5.845
- Shmuel S. Oren, Self-scaling variable metric (SSVM) algorithms. II. Implementation and experiments, Management Sci. 20 (1973/74), 863–874. Mathematical programming. MR 426427, DOI 10.1287/mnsc.20.5.863
- M. J. D. Powell, Rank one methods for unconstrained optimization, Integer and nonlinear programming, North-Holland, Amsterdam, 1970, pp. 139–156. MR 0436589
- M. J. D. Powell, Recent advances in unconstrained optimization, Math. Programming 1 (1971), no. 1, 26–57. MR 305596, DOI 10.1007/BF01584071
- H. H. Rosenbrock, An automatic method for finding the greatest or least value of a function, Comput. J. 3 (1960/61), 175–184. MR 136042, DOI 10.1093/comjnl/3.3.175
Additional Information
- © Copyright 1973 American Mathematical Society
- Journal: Math. Comp. 27 (1973), 873-885
- MSC: Primary 65K05
- DOI: https://doi.org/10.1090/S0025-5718-1973-0329259-8
- MathSciNet review: 0329259