GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization

ABSTRACT

We describe the design of version 1.0 of GALAHAD, a library of Fortran 90 packages for large-scale nonlinear optimization. The library particularly addresses quadratic programming problems, containing both interior point and active set algorithms, as well as tools for preprocessing problems prior to solution. It also contains an updated version of the venerable nonlinear programming package, LANCELOT.

REFERENCES

• 1: Benson, H., Shanno, D. F., and Vanderbei, R. J. 2001. A comparative study of large-scale nonlinear optimization algorithms. Tech. Rep. ORFE 01-04, Operations Research and Financial Engineering, Princeton University, New Jersey.
• 2: Bischof, Chr., Carle, A., Corliss, G., Griewank, A., and Hovland, P. 1992. ADIFOR---generating derivative codes from Fortran programs. Scientific Programming 1, 1--29.
• 3: I. Bongartz , A. R. Conn , Nick Gould , Ph. L. Toint, CUTE: constrained and unconstrained testing environment, ACM Transactions on Mathematical Software (TOMS), v.21 n.1, p.123-160, March 1995 [doi>10.1145/200979.201043]
• 4: Richard H. Byrd , Mary E. Hribar , Jorge Nocedal, An Interior Point Algorithm for Large-Scale Nonlinear Programming, SIAM Journal on Optimization, v.9 n.4, p.877-900, 1999 [doi>10.1137/S1052623497325107]
• 5: Chin, C. M. 2001. Numerical results of SLPSQP, filterSQP and LANCELOT on selected CUTE test problems. Numerical Analysis Report NA/203, Department of Mathematics, University of Dundee, Scotland.
• 6: 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
• 7: A. R. Conn , Nick Gould , Ph. L. Toint, Numerical experiments with the LANCELOT package (release A) for large-scale nonlinear optimization, Mathematical Programming: Series A and B, v.73 n.1, p.73-110, April 30, 1996 [doi>10.1007/BF02592099]
• 8: Andrew R. Conn , Nicholas I. M. Gould , Philippe L. Toint, Trust-region methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 9: Conn, A. R., Gould, N. I. M., Orban, D., and Toint, Ph. L. 2000b. A primal-dual trust-region algorithm for non-convex nonlinear programming. Mathematical Programming 87, 2, 215--249.
• 10: A. R. Conn , Nick Gould , A. Sartenaer , Ph. L. Toint, Convergence Properties of Minimization Algorithms for Convex Constraints Using a Structured Trust Region, SIAM Journal on Optimization, v.6 n.4, p.1059-1086, 1996 [doi>10.1137/S1052623492236481]
• 11: Joseph Czyzyk , Michael P. Mesnier , Jorge J. Moré, The NEOS Server, IEEE Computational Science & Engineering, v.5 n.3, p.68-75, July 1998 [doi>10.1109/99.714603]
• 12: Dolan, E. D. and Moré, J. J. 2000. Benchmarking optimization software with COPS. Tech. Rep. ANL/MCS-246, Argonne National Laboratory, Illinois, USA.
• 13: Dolan, E. D. and Moré, J. J. 2002. Benchmarking optimization software with performance profiles. Math. Program. 91, 2, 201--213.
• 14: Duff, I. S. 2002. MA57---a new code for the solution of sparse symmetric definite and indefinite systems. Tech. Rep. RAL-TR-2002-024, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England.
• 15: Duff, I. S. and Reid, J. K. 1982. MA27: A set of Fortran subroutines for solving sparse symmetric sets of linear equations. Report R-10533, AERE Harwell Laboratory, Harwell, UK.
• 16: Fletcher, R. and Leyffer, S. 2002. Nonlinear programming without a penalty function. Math. Program. 91, 2, 239--269.
• 17: Fourer, R., Gay, D. M., and Kernighan, B. W. 2003. AMPL: A Modeling Language for Mathematical Programming, (2nd. edn.). Brooks/Cole--Thompson Learning, Pacific Grove, California, USA.
• 18: Philip E. Gill , Walter Murray , Michael A. Saunders, SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization, SIAM Journal on Optimization, v.12 n.4, p.979-1006, 2002 [doi>10.1137/S1052623499350013]
• 19: Gould, N. I. M. and Toint, Ph. L. 2002a. Numerical methods for large-scale non-convex quadratic programming. In Trends in Industrial and Applied Mathematics (A. H. Siddiqi and M. Kočvara, eds.). Kluwer Academic Publishers, Dordrecht, The Netherlands, 149--179.
• 20: Gould, N. I. M. and Toint, Ph. L. 2002b. Preprocessing for quadratic programming. Tech. Rep. RAL-TR-2002-001, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England.
• 21: Nicholas I. M. Gould , Mary E. Hribar , Jorge Nocedal, On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization, SIAM Journal on Scientific Computing, v.23 n.4, p.1376-1395, 2001 [doi>10.1137/S1064827598345667]
• 22: Nicholas I. M. Gould , Stefano Lucidi , Massimo Roma , Philippe L. Toint, Solving the Trust-Region Subproblem using the Lanczos Method, SIAM Journal on Optimization, v.9 n.2, p.504-525, 1999 [doi>10.1137/S1052623497322735]
• 23: Gould, N. I. M., Orban, D., and Toint, Ph. L. 2002a. CUTEr (and SifDec), a constrained and unconstrained testing environment, revisited. Tech. Rep. RAL-TR-2002-009, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England.
• 24: Gould, N. I. M., Orban, D., and Toint, Ph. L. 2002b. Results from a numerical evaluation of LANCELOT B. Numerical Analysis Group Internal Report 2002-1, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England.
• 25: Nicholas I. M. Gould , Dominique Orban , Annick Sartenaer , Philippe L. Toint, Superlinear Convergence of Primal-Dual Interior Point Algorithms for Nonlinear Programming, SIAM Journal on Optimization, v.11 n.4, p.974-1002, 2000 [doi>10.1137/S1052623400370515]
• 26: Willi Hock , K. Schittkowski, Test Examples for Nonlinear Programming Codes, Springer-Verlag New York, Inc., Secaucus, NJ, 1981
• 27: HSL. 2002. A collection of {F}ortran codes for large-scale scientific computation. See http://www.cse.clrc.ac.uk/Activity/HSL.
• 28: Chih-Jen Lin , Jorge J. Moré, Incomplete Cholesky Factorizations with Limited Memory, SIAM Journal on Scientific Computing, v.21 n.1, p.24-45, Aug.-Sept. 1999 [doi>10.1137/S1064827597327334]
• 29: Chih-Jen Lin , Jorge J. Moré, Newton's Method for Large Bound-Constrained Optimization Problems, SIAM Journal on Optimization, v.9 n.4, p.1100-1127, 1999 [doi>10.1137/S1052623498345075]
• 30: Moré, J. J. and Toraldo, G. 1991. On the solution of large quadratic programming problems with bound constraints. SIAM J. Optimization, 1, 1, 93--113.
• 31: Pryce, J. D. and Reid, J. K. 1998. AD01, a Fortran 90 code for automatic differentiation. Tech. Rep. RAL-TR-1998-057, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England.
• 32: Philippe L. Toint, Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints, Mathematical Programming: Series A and B, v.77 n.1, p.69-94, April 1997
• 33: Robert J. Vanderbei , David F. Shanno, An Interior-Point Algorithm for Nonconvex Nonlinear Programming, Computational Optimization and Applications, v.13 n.1-3, p.231-252, April 1999 [doi>10.1023/A:1008677427361]
• 34: Zhang, Y. 1994. On the convergence of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optimization, 4, 1, 208--227.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms

Keywords:
Fortran 90, GALAHAD, LANCELOT, large-scale nonlinear optimization, large-scale quadratic programming