CUTE: constrained and unconstrained testing environment

ABSTRACT

The purpose of this article is to discuss the scope and functionality of a versatile environment for testing small- and large-scale nonlinear optimization algorithms. Although many of these facilities were originally produced by the authors in conjunction with the software package LANCELOT, we believe that they will be useful in their own right and should be available to researchers for their development of optimization software. The tools can be obtained by anonymous ftp from a number of sources and may, in many cases, be installed automatically. The scope of a major collection of test problems written in the standard input format (SIF) used by the LANCELOT software package is described. Recognizing that most software was not written with the SIF in mind, we provide tools to assist in building an interface between this input format and other optimization packages. These tools provide a link between the SIF and a number of existing packages, including MINOS and OSL. Additionally, as each problem includes a specific classification that is designed to be useful in identifying particular classes of problems, facilities are provided to build and manage a database of this information. There is a Unix and C shell bias to many of the descriptions in the article, since, for the sake of simplicity, we do not illustrate everything in its fullest generality. We trust that the majority of potential users are sufficiently familiar with Unix that these examples will not lead to undue confusion.

REFERENCES

• 1: AVERICK, B. M. AND MOR~, J. J. 1991. The Minpack-2 test problem collection. Tech. Rep.
• 2: ANL/MCS-TM-157, Argonne National Laboratory, Argonne, Ill.
• 3: AVERICK, B. M., CARTER, R. G., AND MoRli, J.J. 1991. The Minpack-2 test problem collection (preliminary version). Tech. Rep. ANL/MCS-TM-150, Argonne National Laboratory, Argonne, Ill.
• 4: Paul T. Boggs , Jon W. Tolle, A strategy for global convergence in a sequential quadratic programming algorithm, SIAM Journal on Numerical Analysis, v.26 n.3, p.600-623, June 1989 [doi>10.1137/0726036]
• 5: A. G. Buckley, ALGORITHM 709; testing algorithm implementations, ACM Transactions on Mathematical Software (TOMS), v.18 n.4, p.375-391, Dec. 1992 [doi>10.1145/138351.138378]
• 6: BUCKLEY, A.G. 1989. Test functions for unconstrained minimization. Tech. Rep. CS-3, Computing Science Division, Dalhousie Univ., Dalhousie, Halifax, Nova Scotia, Canada.
• 7: Bus, J. C.P. 1977. A proposal for the classification and documentation of test problems in the field of nonlinear programming. Tech. Rep., Mathematisch Centrum, Amsterdam.
• 8: CONN, A. R., GOULD, N., AND TOINT, PH. L. 1994. A note on using alternative second-order models for the subproblems arising in barrier function methods for minimization. Numerische Mathematik 68, 1, 17-33.
• 9: A. R. Conn , N. I. M. Gould , Ph L. Toint, Lancelot: A FORTRAN Package for Large-Scale Nonlinear Optimization (Release A), Springer-Verlag New York, Inc., Secaucus, NJ, 1992
• 10: CONN, A. R., GOULD, N. I. M., AND TOINT, PH. L. 1992b. Numerical experiments with the LANCELOT package (Release A) for large-scale nonlinear optimization. Tech. Rep. 92-16, FUNDP, Namur, Belgium. Available via anonymous ftp from thales.math.fundp.ac.be (Internet i.d. 138.48.4.14), in directory pub/reports.
• 11: Cor~N, A. R., GOULD, N. I. M., AND TOINT, PH. L. 1992c. Intensive numerical tests with LANCELOT (Release A): The complete results. Tech. Rep. 92-15, FUNDP, Namur, Belgium. Available via anonymous ftp from thales.math.fundp.ac.be (Internet i.d. 138.48.4.14), in directory pub/reports.
• 12: CONN, A. R., GOULD, N. I. M., AND TOINT, PH. L. 1990. An introduction to the structure of large-scale nonlinear optimization problems and the LANCELOT project. In Computing Methods in Applied Sciences and Engineering, R. Glowinski and A. Lichnewsky, Eds. SIAM, Philadelphia, Pa., 42-54.
• 13: DEMBO, R. S. 1984. A primal truncated-Newton algorithm with application to large-scale nonlinear network optimization. Tech. Rep. 72, Yale School of Management, Yale Univ., New Haven, Conn.
• 14: DENNIS, J. E. AND SCHNABEL, R.B. 1983. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, N.J.
• 15: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 16: GAY, D. M. 1985. Electronic mail distribution of linear programming test problems. Math. Program. Soc. COAL Newsl., 13 (Dec.), 10-12.
• 17: GILL, P. E., MURRAY, W., SAUNDERS, M. A., AND WmGHT, M.H. 1986. User's guide for NPSOL (version 4.0): A Fortran package for nonlinear programming. Tech. Rep. SOL86-2, Dept. of Operations Research, Stanford Univ., Stanford, Calif.
• 18: GOULD, N. I.M. 1991. An algorithm for large-scale quadratic programming. IMA J. Numer. Anal. 11, 3, 299 324.
• 19: GRIEWANK, A. AND TOINT, PH. L. 1982. On the unconstrained optimization of partially separable functions. In Nonlinear Optimization 1981, M. J. D. Powell, Ed. Academic Press, New York, 301-312.
• 20: GULLIKSSON, M. 1990. Algorithms for nonlinear least squares with applications to orthogonal regression. Ph.D. thesis, Inst. of Information Processing, Univ. of Ume~, Ume~, Sweden.
• 21: HARWELL. 1993. A Catalogue of Subroutines (Release 11). Advanced Computing Dept., Harwell Laboratory, HarwelL U.K.
• 22: Willi Hock , K. Schittkowski, Test Examples for Nonlinear Programming Codes, Springer-Verlag New York, Inc., Secaucus, NJ, 1981
• 23: IBM. 1990. Optimization Subroutine L~brary: Guide and Reference. 2nd ed., SC23-0519-1. IBM Corp., Armonk, N.Y.
• 24: IBM. 1978. Mathematical programming system extended (MPSX) and generalized upper bounding (GUB). SH20-0968-1, MPSX Standard, IBM Corp., Armonk, N.Y.
• 25: Robert B. Schnabel , John E. Koonatz , Barry E. Weiss, A modular system of algorithms for unconstrained minimization, ACM Transactions on Mathematical Software (TOMS), v.11 n.4, p.419-440, Dec. 1985 [doi>10.1145/6187.6192]
• 26: D. C. Liu , J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming: Series A and B, v.45 n.3, p.503-528, Dec. 1989 [doi>10.1007/BF01589116]
• 27: MATLAB. 1993. High-Performance Numeric Computation and Vzsualzzatzon Software, Release 4. The MathWorks, Inc., Natick. Mass.
• 28: MoR~. J. J. AND TOP~LDO, G. 1991. On the solution of large quadratic programming problems with bound constraints. SIAM J. Optzm. 1, 1, 93-113.
• 29: 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]
• 30: MURTAGH, B. A. AND SAUNDERS, M.A. 1993. MINOS 5 4 User's Guide. Tech. Rep. SOL 83-20R, Dept. of Operations Research, Stanford University, Stanford, Calif.
• 31: MURTACH, B. A. AND SAUNDERS, M.A. 1978. Large-scale linearly constrained optimization. Math. Program. 14, 41 72.
• 32: POWELL, M. J. D. 1994. A direct search optimization method that models the objective and constraint functions by linear interpolation. In Advances in Optimization and Numerical Analysis, Proceedings of the 6th Workshop on Optimization and Numerical Analysis (Oaxaca, Mexico). Mathematics and its Applications, vol. 275. Kluwer Academic, New York, 51-67.
• 33: POWELL, M. J.D. 1982. Extensions to subroutine VF02. In Systems Modelling' and Optimizatwn. Lecture Notes in Control and Information Sciences, vol. 38. Springer-Verlag, Berlin, 529-538.
• 34: Klaus Schittkowski, More test examples for nonlinear programming codes, Springer-Verlag New York, Inc., New York, NY, 1987
• 35: SCHNABEL, R. B. AND CHOW, T.-T. 1991. Tensor methods for unconstrained optimization using second derivatives. SIAM J. Optim. 1, 3, 293-315.
• 36: TOINT, PH. L. 1983. Test problems for partially separable optimization and results for the routine PSPMIN. Tech. Rep. 83/4, Dept. of Mathematics, FUNDP, Namur, Belgium.
• 37: P. L. Toint , D. Tuyttens, On large scale nonlinear network optimization, Mathematical Programming: Series A and B, v.48 n.1, p.125-159, Mar. 1990 [doi>10.1007/BF01582254]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization; Nonlinear programming
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness; Verification**

General Terms:
Algorithms, Performance

Keywords:
test problems