Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



The affine scale invariance of minimization algorithms

Author: J. N. Lyness
Journal: Math. Comp. 33 (1979), 265-287
MSC: Primary 65K05; Secondary 90C30
MathSciNet review: 514823
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ f(x)$ be a general objective function and let $ \bar f(x) = h + mf(Ax + d)$. An analytic estimation of the minimum of one would resemble an analytic estimation of the other in all nontrivial respects. However, the use of a minimization algorithm on either might or might not lead to apparently unrelated sequences of calculations.

This paper is devoted to providing a general theory for the affine scale invariance of algorithms. Key elements in this theory are groups of transformations T whose elements relate $ \bar f(x)$ and $ f(x)$ given above. The statement that a specified algorithm is scale invariant with respect to a specified group T is defined. The scale invariance properties of several well-known algorithms are discussed.

References [Enhancements On Off] (What's this?)

  • [R] P. BRENT (1973), Algorithms for Minimization without Derivatives, Prentice-Hall, Englewood Cliffs, N. J. MR 0339493 (49:4251)
  • [R] FLETCHER & M. J. D. POWELL (1963), "A rapidly convergent descent method for minimization," Comput. J., v. 6, pp. 163-168. MR 0152116 (27:2096)
  • [R] FLETCHER & C. M. REEVES (1964), "Function minimization by conjugate gradients," Comput. J., v. 7, pp. 149-154. MR 0187375 (32:4827)
  • [R] FLETCHER (1972), "Conjugate direction methods," Numerical Methods for Unconstrained Optimization, (W. Murray, Editor), Academic Press, London, pp. 73-86.
  • [M] R. HESTENES & E. STIEFEL (1952), "Methods of conjugate gradients for solving linear systems," J. Res. Nat. Bur. Standards, v. 49, pp. 409-436. MR 0060307 (15:651a)
  • [J] N. LYNESS (1979), "A bench mark experiment for minimization algorithms," Math. Comp., v. 33, pp. 249-264. MR 514822 (80m:65050a)
  • [W] MURRAY (1972), "Second derivative methods," Numerical Methods for Unconstrained Optimization, (W. Murray, Editor), Academic Press, London, pp. 57-71.
  • [E] POLAK & G. RIBIERE (1969), Note sur la Convergence de Méthodes des Directions Conjugées, Dept. of Electrical Engineering and Computer Sciences, University of California, Berkeley, working paper. MR 0255025 (40:8232)
  • [M] J. D. POWELL (1971), "On the convergence of a variable metric algorithm," J. Inst. Math. Appl., v. 7, pp. 21-36. MR 0279977 (43:5698)
  • [B] SPAIN (1953), Tensor Calculus, Oliver and Boyd, Edinburgh and London. MR 0055027 (14:1017f)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65K05, 90C30

Retrieve articles in all journals with MSC: 65K05, 90C30

Additional Information

Keywords: Numerical software evaluation, affine scale invariance, minimization algorithms, optimization algorithms
Article copyright: © Copyright 1979 American Mathematical Society

American Mathematical Society