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 Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a general objective function and let . 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 and 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.

**[R]**Richard P. Brent,*Algorithms for minimization without derivatives*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. Prentice-Hall Series in Automatic Computation. MR**0339493****[R]**R. Fletcher and M. J. D. Powell,*A rapidly convergent descent method for minimization*, Comput. J.**6**(1963/1964), 163–168. MR**0152116****[R]**R. Fletcher and C. M. Reeves,*Function minimization by conjugate gradients*, Comput. J.**7**(1964), 149–154. MR**0187375****[R]**FLETCHER (1972), "Conjugate direction methods,"*Numerical Methods for Unconstrained Optimization*, (W. Murray, Editor), Academic Press, London, pp. 73-86.**[M]**Magnus R. Hestenes and Eduard Stiefel,*Methods of conjugate gradients for solving linear systems*, J. Research Nat. Bur. Standards**49**(1952), 409–436 (1953). MR**0060307****[J]**J. N. Lyness,*A bench mark experiment for minimization algorithms*, Math. Comp.**33**(1979), no. 145, 249–264. MR**514822**, 10.1090/S0025-5718-1979-0514822-7**[W]**MURRAY (1972), "Second derivative methods,"*Numerical Methods for Unconstrained Optimization*, (W. Murray, Editor), Academic Press, London, pp. 57-71.**[E]**E. Polak and G. Ribière,*Note sur la convergence de méthodes de directions conjuguées*, Rev. Française Informat. Recherche Opérationnelle**3**(1969), no. 16, 35–43 (French, with Loose English summary). MR**0255025****[M]**M. J. D. Powell,*On the convergence of the variable metric algorithm*, J. Inst. Math. Appl.**7**(1971), 21–36. MR**0279977****[B]**Barry Spain,*Tensor Calculus*, Oliver and Boyd, Edinburgh and London; Interscience Publishers, Inc., New York, 1953. MR**0055027**

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

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

Additional Information

DOI:
http://dx.doi.org/10.1090/S0025-5718-1979-0514823-9

Keywords:
Numerical software evaluation,
affine scale invariance,
minimization algorithms,
optimization algorithms

Article copyright:
© Copyright 1979
American Mathematical Society