The affine scale invariance of minimization algorithms

Author:
J. N. Lyness

Journal:
Math. Comp. **33** (1979), 265-287

MSC:
Primary 65K05; Secondary 90C30

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

MathSciNet review:
514823

Full-text PDF

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]**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)**

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

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

Additional Information

DOI:
https://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