Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Self-scaling variable metric algorithms without line search for unconstrained minimization


Author: Shmuel S. Oren
Journal: Math. Comp. 27 (1973), 873-885
MSC: Primary 65K05
DOI: https://doi.org/10.1090/S0025-5718-1973-0329259-8
Corrigendum: Math. Comp. 28 (1974), 887.
Corrigendum: Math. Comp. 28 (1974), 887.
MathSciNet review: 0329259
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Y. Bard, "On a numerical instability of Davidon-like methods," Math. Comp., v. 22, 1968, pp. 665-666. MR 38 #858. MR 0232533 (38:858)
  • [2] C. G. Broyden, "Quasi-Newton methods and their applications to function minimization," Math. Comp., v. 21, 1967, pp. 368-381. MR 36 #7317. MR 0224273 (36:7317)
  • [3] C. G. Broyden, "The convergence of a class of double-rank minimization algorithms 2: The new algorithm," J. Inst. Math. Appl., v. 6, 1970, pp. 222-231. MR 0433870 (55:6841)
  • [4] A. R. Colville, A Comparative Study on Nonlinear Programming Codes, IBM Tech. Rep. No. 320-2949, 1968.
  • [5] W. C. Davidon, Variable Metric Method for Minimization, A.E.C. Research and Development Rep. ANL-5990 (Rev.), 1959.
  • [6] W. C. Davidon, "Variance algorithm for minimization," Comput. J., v. 10, 1968, pp. 406-410. MR 36 #4790. MR 0221738 (36:4790)
  • [7] L. C. W. Dixon, "Variable metric algorithms: Necessary and sufficient conditions for identical behavior of non-quadratic functions," J. Optimization Theory Appl., v. 10, 1972, pp. 34-40. MR 0309305 (46:8415)
  • [8] R. Fletcher & M. J. D. Powell, "A rapidly convergent descent method for minimization," Comput. J., v. 6, 1964, pp. 163-168. MR 27 #2096. MR 0152116 (27:2096)
  • [9] R. Fletcher, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317-322.
  • [10] P. E. Gill & W. Murray, "Quasi-Newton methods for unconstrained optimization," J. Inst. Math. Appl., v. 9, 1972, pp. 91-108. MR 0300410 (45:9456)
  • [11] A. A. Goldstein, "On steepest descent," J. Soc. Indust. Appl. Math. Ser. A Control, v. 3, 1965, pp. 147-151. MR 32 #2249. MR 0184777 (32:2249)
  • [12] J. Greenstadt, "Variations on variable metric methods," Math. Comp., v. 24, 1970, pp. 1-22. MR 41 #2895. MR 0258248 (41:2895)
  • [13] A. S. Householder, The Theory of Matrices in Numerical Analysis, Blaisdell, New York, 1964. MR 30 #5475. MR 0175290 (30:5475)
  • [14] H. Y. Huang, "Unified approach to quadratically convergent algorithms for function minimization," J. Optimization Theory Appl., v. 5, 1970, pp. 405-423. MR 44 #6134. MR 0288939 (44:6134)
  • [15] L. V. Kantorovič & G. P. Akilov, Functional Analysis in Normed Spaces, Fizmatgiz, Moscow, 1959; English transl., Internat. Series of Monographs in Pure and Appl. Math., vol. 46, Macmillan, New York, 1964. MR 22 #9837; MR 35 #4699. MR 0119071 (22:9837)
  • [16] D. G. Luenberger, Introduction to Linear and Nonlinear Programming, Addison-Wesley, Reading, Mass., 1973.
  • [17] B. A. Murtagh & R. W. H. Sargent, A Constrained Minimization Method With Quadratic Convergence, Optimization (Sympos., Univ. Keele, 1968), Academic Press, London, 1969, pp. 215-245. MR 44 #1442. MR 0284213 (44:1442)
  • [18] S. S. Oren, Self-Scaling Variable Metric Algorithms for Unconstrained Minimization, Ph.D. Thesis, Department of Engineering-Economic Systems, Stanford University, Stanford, Calif., 1972.
  • [19] S. S. Oren & D. G. Luenberger, The Self-Scaling Variable Metric Algorithm, Proc. Fifth Hawaii International Conference on System Sciences, January, 1972.
  • [20] S. S. Oren & D. G. Luenberger, "Self-scaling variable metric (SSVM) algorithms. I: Criteria and sufficient conditions for scaling a class of algorithms," Management Sci. (To appear.) MR 0388773 (52:9607)
  • [21] S. S. Oren, "Self-scaling variable metric (SSVM) algorithms. II: Implementation and experiments," Management Sci. (To appear.) MR 0426427 (54:14370)
  • [22] M. J. D. Powell, "Rank one methods for unconstrained optimization," in Integer and Nonlinear Programming, J. Abadie (Editor), North-Holland, Amsterdam, 1970, pp. 139-156. MR 0436589 (55:9532)
  • [23] M. J. D. Powell, Recent Advances in Unconstrained Optimization, Report No. T. P., 430, A. E. R. E., Harwell, 1970. MR 0305596 (46:4726)
  • [24] H. H. Rosenbrock, "An automatic method for finding the greatest or least value of a function," Comput. J., v. 3, 1961, pp. 175-184. MR 24 #B2081. MR 0136042 (24:B2081)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65K05

Retrieve articles in all journals with MSC: 65K05


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1973-0329259-8
Keywords: Function minimization, unconstrained minimization, quasi-Newton methods, variable metric methods, self-scaling variable metric algorithms, scaling, quasi-Newton algorithms with line search, gradient methods, Hessian matrix inverse approximation, conditioning of search methods, convergence rates
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society