The affine scale invariance of minimization algorithms
Author:
J. N. Lyness
Journal:
Math. Comp. 33 (1979), 265287
MSC:
Primary 65K05; Secondary 90C30
MathSciNet review:
514823
Fulltext 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 wellknown algorithms are discussed.
 [R]
Richard
P. Brent, Algorithms for minimization without derivatives,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1973. PrenticeHall Series in
Automatic Computation. MR 0339493
(49 #4251)
 [R]
R.
Fletcher and M.
J. D. Powell, A rapidly convergent descent method for
minimization, Comput. J. 6 (1963/1964),
163–168. MR 0152116
(27 #2096)
 [R]
R.
Fletcher and C.
M. Reeves, Function minimization by conjugate gradients,
Comput. J. 7 (1964), 149–154. MR 0187375
(32 #4827)
 [R]
FLETCHER (1972), "Conjugate direction methods," Numerical Methods for Unconstrained Optimization, (W. Murray, Editor), Academic Press, London, pp. 7386.
 [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
(15,651a)
 [J]
J.
N. Lyness, A bench mark experiment for
minimization algorithms, Math. Comp.
33 (1979), no. 145, 249–264. MR 514822
(80m:65050a), http://dx.doi.org/10.1090/S00255718197905148227
 [W]
MURRAY (1972), "Second derivative methods," Numerical Methods for Unconstrained Optimization, (W. Murray, Editor), Academic Press, London, pp. 5771.
 [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
(40 #8232)
 [M]
M.
J. D. Powell, On the convergence of the variable metric
algorithm, J. Inst. Math. Appl. 7 (1971),
21–36. MR
0279977 (43 #5698)
 [B]
Barry
Spain, Tensor Calculus, Oliver and Boyd, Edinburgh and London;
Interscience Publishers, Inc., New York, 1953. MR 0055027
(14,1017f)
 [R]
 P. BRENT (1973), Algorithms for Minimization without Derivatives, PrenticeHall, 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. 163168. MR 0152116 (27:2096)
 [R]
 FLETCHER & C. M. REEVES (1964), "Function minimization by conjugate gradients," Comput. J., v. 7, pp. 149154. MR 0187375 (32:4827)
 [R]
 FLETCHER (1972), "Conjugate direction methods," Numerical Methods for Unconstrained Optimization, (W. Murray, Editor), Academic Press, London, pp. 7386.
 [M]
 R. HESTENES & E. STIEFEL (1952), "Methods of conjugate gradients for solving linear systems," J. Res. Nat. Bur. Standards, v. 49, pp. 409436. MR 0060307 (15:651a)
 [J]
 N. LYNESS (1979), "A bench mark experiment for minimization algorithms," Math. Comp., v. 33, pp. 249264. MR 514822 (80m:65050a)
 [W]
 MURRAY (1972), "Second derivative methods," Numerical Methods for Unconstrained Optimization, (W. Murray, Editor), Academic Press, London, pp. 5771.
 [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. 2136. 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
DOI:
http://dx.doi.org/10.1090/S00255718197905148239
PII:
S 00255718(1979)05148239
Keywords:
Numerical software evaluation,
affine scale invariance,
minimization algorithms,
optimization algorithms
Article copyright:
© Copyright 1979
American Mathematical Society
