OPT++: An object-oriented toolkit for nonlinear optimization

ABSTRACT

Object-oriented programming is a relatively new tool in the development of optimization software. The code extensibility and the rapid algorithm prototyping capability enabled by this programming paradigm promise to enhance the reliability, utility, and ease of use of optimization software. While the use of object-oriented programming is growing, there are still few examples of general purpose codes written in this manner, and a common approach is far from obvious. This paper describes OPT++, a C++ class library for nonlinear optimization. The design is predicated on the concept of distinguishing between an algorithm-independent class hierarchy for nonlinear optimization problems and a class hierarchy for nonlinear optimization methods that is based on common algorithmic traits. The interface is designed for ease of use while being general enough so that new optimization algorithms can be added easily to the existing framework. A number of nonlinear optimization algorithms have been implemented in OPT++ and are accessible through this interface. Furthermore, example applications demonstrate the simplicity of the interface as well as the advantages of a common interface in comparing multiple algorithms.

REFERENCES

• 1: Bartlett, R. A. Moocho: Multifunctional object-oriented architecture for optimization, user's guide. http://software.sandia.gov/trilines/packages/docs/dev/packages/moocho/doc/html/ind.
• 2: Bartlett, R. A. 2001. An introduction to rSQP++: An object-oriented framework for reduced-space successive quadratic programming. Report, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA (Oct.).
• 3: Benson, S., McInnes, L. C., Moré, J. J., and Sarich, J. 2005. Tao users manual. Tech. Rep. ANL/MCS-TM-242-Revision 1.8, Argonne National Laboratory.
• 4: Timothy Budd, An introduction to object-oriented programming, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1991
• 5: R. H. Byrd , R. B. Schnabel , G. A. Shultz, Parallel quasi-Newton methods for unconstrained optimization, Mathematical Programming: Series A and B, v.42 n.2, p.273-306, February 1, 1988 [doi>10.1007/BF01589407]
• 6: Couture, G., Audet, C., Dennis, J., and Abramson, M. 2006. Nonlinear optimization for mixed variables and derivatives. Online at http://www.gerad.ca/~couturgiNOMAD.
• 7: Davies, R. B. 2003. NEWMAT09, an experimental matrix package in C++. Online at http://www. robertnz.net/nm_intro.htm.
• 8: Deng, H. L., Gouveia, W., and Scales, J. A. 1996. The CWP object-oriented optimization library. Leading Edge 15, 5, 365--369. Online at http://coool.mines.edu/index.html.old (see also http://coool.mines.edu).
• 9: Dennis, Jr., J. E. and Torczon, V. 1991. Direct search methods on parallel machines. SIAM J. Opt. 1, 4, 448--474.
• 10: A. S. El-Bakry , R. A. Tapia , T. Tsuchiya , Y. Zhang, On the formulation and theory of the Newton interior-point method for nonlinear programming, Journal of Optimization Theory and Applications, v.89 n.3, p.507-541, June 1996 [doi>10.1007/BF02275347]
• 11: E. Michael Gertz , Stephen J. Wright, Object-oriented software for quadratic programming, ACM Transactions on Mathematical Software (TOMS), v.29 n.1, p.58-81, March 2003 [doi>10.1145/641876.641880]
• 12: Mark S. Gockenbach , Matthew J. Petro , William W. Symes, C++ classes for linking optimization with complex simulations, ACM Transactions on Mathematical Software (TOMS), v.25 n.2, p.191-212, June 1999 [doi>10.1145/317275.317280]
• 13: Gondzio, J. and Grothey, A. 2003. Parallel interior point solver for structured quadratic programs: application to financial planning problems. Tech. Rep. MS-03-001, School of Mathematics, The University of Edinburgh.
• 14: Gondzio, J. and Grothey, A. 2004. Solving nonlinear portfolio optimization problems with the primal-dual interior point method. Tech. Rep. MS-04-001, School of Mathematics, The University of Edinburgh.
• 15: Gondzio, J. and Sarkissian, R. 2003. Parallel interior point solver for structured linear programs. Math. Prog. 96, 3, 561--584.
• 16: Gray, G. A. and Kolda, T. G. 2004. APPSPACK 4.0: Asynchronous parallel pattern search for derivative-free optimization. Tech. Rep. SAND2004-6391, Sandia National Laboratories.
• 17: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI: portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1994
• 18: Allen I. Holub, C+ C++: programming with objects in C and C++, McGraw-Hill, Inc., New York, NY, 1992
• 19: P. D. Hough , J. C. Meza, A Class of Trust-Region Methods for Parallel Optimization, SIAM Journal on Optimization, v.13 n.1, p.264-282, 2002 [doi>10.1137/S1052623498343799]
• 20: Howle, V. E., Shontz, S. M., and Hough, P. D. 2000. Some parallel extensions to optimization methods in opt++. Tech. Rep. SAND2000-8877, Sandia National Laboratories.
• 21: Kolda, T. G. 2004. Revisiting asynchronous parallel pattern search. Tech. Rep. SAND2004-8055, Sandia National Laboratories.
• 22: Kolda, T. G., Lewis, R. M., and Torczon, V. 2003. Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45, 3, 385--482.
• 23: 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]
• 24: Long, K. R. 2003. Sundance: A high-level toolkit for parallel pde simulation and optimization. Online at http://csmr.ca.sandia.gov/~klong/sundance.html.
• 25: Meza, J. C. 1994. OPT++: An object oriented class library for nonlinear optimization. Tech. Rep. 94-8225, Sandia National Laboratories.
• 26: Meza, J. C., Judson, R. S., Faulkner, T. R., and Treasurywala, A. M. 1996. A comparison of a direct search method and a genetic algorithm for conformational searching. J. Computat. Chem. 17, 9, 1142--1151.
• 27: J. C. Meza , M. L. Martinez, Direct search methods for the molecular conformation problem, Journal of Computational Chemistry, v.15 n.6, p.627-632, June 1994 [doi>10.1002/jcc.540150606]
• 28: Meza, J. C. and Plantenga, T. D. 1995. Optimal control of a CVD reactor for prescribed temperature behavior. Tech. Rep. 95-8222, Sandia National Laboratories.
• 29: Moen, C. D., Spence, P. A., and Meza, J. C. 1995. Optimal heat transfer design of chemical vapor deposition reactors. Tech. Rep. 95-8223, Sandia National Laboratories.
• 30: Moré, J. J. and Thuente, D. J. 1992. Line search algorithms with guaranteed sufficient decrease. Tech. Rep. MCS-P330-1092, Argonne National Laboratory.
• 31: Jorge J. More , Stephen J. Wright, Optimization Software Guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1993
• 32: Oliva, R. A. 2003. An object-oriented library for molecular dynamics energy computations. Tech. Rep. LBNL-53778, Lawrence Berkeley National Laboratory.
• 33: Padula, A. D., Scott, S. D., and Symes, W. W. 2004. The standard vector library: A software framework for coupling complex simulation and optimization. Tech. Rep. TR04-19, Rice University.
• 34: Padula, A. D., Scott, S. D., and Symes, W. W. 2005. A software framework for abstract expression of coordinate-free linear algebra and optimization algorithms. Tech. Rep. TR05-12, Rice University.
• 35: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization; Quadratic programming methods; Constrained optimization; Gradient methods

General Terms:
Algorithms, Experimentation

Keywords:
Object oriented programming, parallel optimization, scientific computing