The affine scale invariance of minimization algorithms
HTML articles powered by AMS MathViewer
- by J. N. Lyness PDF
- Math. Comp. 33 (1979), 265-287 Request permission
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
- Richard P. Brent, Algorithms for minimization without derivatives, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. MR 0339493
- R. Fletcher and M. J. D. Powell, A rapidly convergent descent method for minimization, Comput. J. 6 (1963/64), 163–168. MR 152116, DOI 10.1093/comjnl/6.2.163
- R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, Comput. J. 7 (1964), 149–154. MR 187375, DOI 10.1093/comjnl/7.2.149 FLETCHER (1972), "Conjugate direction methods," Numerical Methods for Unconstrained Optimization, (W. Murray, Editor), Academic Press, London, pp. 73-86.
- 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. N. Lyness, A bench mark experiment for minimization algorithms, Math. Comp. 33 (1979), no. 145, 249–264. MR 514822, DOI 10.1090/S0025-5718-1979-0514822-7 MURRAY (1972), "Second derivative methods," Numerical Methods for Unconstrained Optimization, (W. Murray, Editor), Academic Press, London, pp. 57-71.
- 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. J. D. Powell, On the convergence of the variable metric algorithm, J. Inst. Math. Appl. 7 (1971), 21–36. MR 279977
- Barry Spain, Tensor Calculus, Oliver and Boyd, Edinburgh-London; Interscience Publishers, Inc., New York, 1953. MR 0055027
Additional Information
- © Copyright 1979 American Mathematical Society
- 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