A modular system of algorithms for unconstrained minimization

ABSTRACT

We describe a new package, UNCMIN, for finding a local minimizer of a real valued function of more than one variable. The novel feature of UNCMIN is that it is a modular system of algorithms, containing three different step selection strategies (line search, dogleg, and optimal step) that may be combined with either analytic or finite difference gradient evaluation and with either analytic, finite difference, or BFGS Hessian approximation. We present the results of a comparison of the three step selection strategies on the problems in More, Garbow, and Hillstrom in two separate cases: using finite difference gradients and Hessians, and using finite difference gradients with BFGS Hessian approximations. We also describe a second package, REVMIN, that uses optimization algorithms identical to UNCMIN but obtains values of user-supplied functions by reverse communication.

REFERENCES

• 1: John E. Dennis, Jr. , David M. Gay , Roy E. Walsh, An Adaptive Nonlinear Least-Squares Algorithm, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.348-368, Sept. 1981 [doi>10.1145/355958.355965]
• 2: DENNIS, J. E., JR., AND MEI, H. H.W. Two new unconstrained optimization algorithms which use function and gradient values. J. Optimization Theory and Its Applications 28 (1979), 453-482.
• 3: DENNIS, J. E., JR., AND SCHNABEL, R. B. Numerical Methods for Nonlinear Equations and Unconstrained Optimization. Prentice-Hall, Englewood Cliffs, N. J., 1983.
• 4: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 5: GAY, D.M. Some tips for writing portable software. Tech. Rept. TR-14, Center for Computational Research in Economics and Management Science, Massachusetts Institute of Technology, Cambridge, Mass., 1980.
• 6: GAY, D.M. Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput. 2, (1981), 186-197.
• 7: David M. Gay, Algorithm 611: Subroutines for Unconstrained Minimization Using a Model/Trust-Region Approach, ACM Transactions on Mathematical Software (TOMS), v.9 n.4, p.503-524, Dec. 1983 [doi>10.1145/356056.356066]
• 8: GILL, P. E., AND MURRAY, W. Newton-type methods for unconstrained and linearly constrained optimization. Math. Program. 28 (1974), 311-350.
• 9: Philip E. Gill , Walter Murray , Susan M. Picken , Maragret H. Wright, The Design and Structure of a Fortran Program Library for Optimization, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.259-283, Sept. 1979 [doi>10.1145/355841.355844]
• 10: GILL, P. E., MURRAY, W., AND WRIGHT, M.H. Praztical Optimization. Academic Press, New York, 1981.
• 11: GOLDFARB, D. Factorized variable metric methods for unconstrained optimization. Math. Comput. 30 (1976), 796-811.
• 12: Richard W. Hamming, Introduction to applied numerical analysis, Taylor & Francis/Hemisphere, Bristol, PA, 1989
• 13: Harwell Subroutine Library, A Catalogue of Subroutines (M. J. Hopper, Ed.), Computer Science and Systems Division, A.E.R.E. Harwell, Oxon., England.
• 14: IMSL Library Reference Manual, International Mathematical and Statistical Libraries, Houston, Tex.
• 15: KROGH, F. T. VODQ/SVDQ/DVDQwVariable order integrators for numerical solution of ordinary differential equations. Subroutine Write-Up, Section 314, Jet Propulsion Laboratory, Pasadena, Calif.
• 16: LAwsoN, C., BLOCK, N., AND GARRETT, R. Fortran IV subroutines for contour plotting. Technical Memo 106, Section 314, Jet Propulsion Laboratory, Pasadena, Calif.
• 17: MINPACK Documentation, Applied Mathematics Division, Argonne National Laboratory, Argonne, Ill.
• 18: MOR~, J.J. The Levenberg-Marquardt algorithm: Implementation and theory. In G. A. Watson, Numerical Analysis, Dundee 1977, Lecture Notes in Mathematics 630. Ed., Springer-Verlag, Berlin, pp. 105-116.
• 19: MOR~, J. J. On the design of optimization software. In S. Incerti and G. Treccani, Eds., Otimazzazione Nonlineare e Applicazioni. Pitagora Editrice, Bologna, Italy, 1980.
• 20: MOR~:, J.J. Notes on optimization software. In M. J. D. Powell, Ed., Nonlinear Optimization 1981, Academic Press, New York, 1982, pp. 339-352.
• 21: Jorge J. Moré , Burton S. Garbow , Kenneth E. Hillstrom, Testing Unconstrained Optimization Software, ACM Transactions on Mathematical Software (TOMS), v.7 n.1, p.17-41, March 1981 [doi>10.1145/355934.355936]
• 22: MOR~:, J. J., AND SORENSEN, D.C. Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, (1983), 553-572.
• 23: NAG Fortran Library Manual, The Numerical Algorithms Group (USA), Downers Grove, Ill.
• 24: OSTERWEIL, L. J., AND FOSDICK, L.D. DAVE--A validation error detection and documentation system for Fortran programs. Softw. Pract. Exp. 6, (1976), 473-486.
• 25: RYDER, B.G. The PFORT verifier. Softw. Pract. Exp. 4, (1974), 359-377.
• 26: D. F. Shanno , K. H. Phua, Algorithm 500: Minimization of Unconstrained Multivariate Functions [E4], ACM Transactions on Mathematical Software (TOMS), v.2 n.1, p.87-94, March 1976 [doi>10.1145/355666.355673]
• 27: SHULTZ, G. A., SCHNABEL, R. B., AND BYRD, R.H. A family of trust region based algorithms for unconstrained minimization with strong global convergence properties. SIAM J. Numer. Anal. 22, (1985), 47-67.
• 28: SORENSEN, D.C. Newton's method with a model trust region modification. SIAM Jo Numer. Anal. 19, {1982), 409-426.
• 29: Jerrold L. Wagener, Status of work toward revision of programming language Fortran, ACM SIGNUM Newsletter, v.19 n.3, p.1-42, July 1984
• 30: WEISS, B.E. A modular software package for solving unconstrained nonlinear optimization problems. M. S. thesis, Department of Computer Science, University of Colorado at Boulder, 1980.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization
  G.4 MATHEMATICAL SOFTWARE

      Nouns: UNCMIN

General Terms:
Algorithms