Object-oriented software for quadratic programming

ABSTRACT

The object-oriented software package OOQP for solving convex quadratic programming problems (QP) is described. The primal-dual interior point algorithms supplied by OOQP are implemented in a way that is largely independent of the problem structure. Users may exploit problem structure by supplying linear algebra, problem data, and variable classes that are customized to their particular applications. The OOQP distribution contains default implementations that solve several important QP problem types, including general sparse and dense QPs, bound-constrained QPs, and QPs arising from support vector machines and Huber regression. The implementations supplied with the OOQP distribution are based on such well known linear algebra packages as MA27/57, LAPACK, and PETSc. OOQP demonstrates the usefulness of object-oriented design in optimization software development, and establishes standards that can be followed in the design of software packages for other classes of optimization problems. A number of the classes in OOQP may also be reusable directly in other codes.

REFERENCES

• 1: Balay, S., Gropp, W., Curfman McInnes, L., and Smith, B. 2001. PETSc Users Manual. Mathematics and Computer Science Division, Argonne National Laboratory, 9700 S. Cass Avenue, Argonne, Ill. 60439, Apr.
• 2: Bartlett, R. 1996. An introduction to rSQP++: An object-oriented framework for reduced-space successive quadratic programming. Report, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Oct.
• 3: Benson, S., Curfman McInnes, L., and Moré, J. J. 2001. TAO users manual. Technical Memorandum ANL/MCS-TM-249, Argonne National Laboratory, Argonne, Ill. Mar.
• 4: Are Magnus Bruaset , Hans Petter Langtangen, Object-oriented design of preconditioned iterative methods in diffpack, ACM Transactions on Mathematical Software (TOMS), v.23 n.1, p.50-80, March 1997 [doi>10.1145/244768.244776]
• 5: Edmond Chow , Michael A. Heroux, An object-oriented framework for block preconditioning, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.159-183, June 1998 [doi>10.1145/290200.287639]
• 6: Czyzyk, J., Mehrotra, S., Wagner, M., and Wright, S. J. 1999. PCx: An interior-point code for linear programming. Optimization Methods and Software 11/12, 397--430.
• 7: Demmel, J. W., Gilbert, J. R., and Li, X. S. 1999. SuperLU User's Guide. Available from www. nersc.gov/xiaoye/SuperLU/.
• 8: Deng, H. L., Gouveia, W., and Scales, J. 1994. The CWP object-oriented optimization library. Technical report, Center for Wave Phenomena, Colorado School of Mines, June.
• 9: Dobrian, F., Kumfert, G., and Pothen, A. 2000. The design of sparse direct solvers using object-oriented techniques. In Modern Tools in Scientific Computing A. M. Bruaset, H. P. Langtangen, and E. Quak, Ed., Springer-Verlag, New York.
• 10: Dobrian, F. and Pothen, A. 2000. Oblio: A sparse direct solver library for serial and parallel computations. Tech. Rep. Department of Computer Science, Old Dominion Univ.
• 11: Duff, I. S. and Reid, J. K. 1982. MA27 -- A set of Fortran subroutines for solving sparse symmetric sets of linear equations. Tech. Rep. AERE R10533, AERE Harwell Laboratory, London, England.
• 12: Michael C. Ferris , Todd S. Munson, Interior-Point Methods for Massive Support Vector Machines, SIAM Journal on Optimization, v.13 n.3, p.783-804, 2002 [doi>10.1137/S1052623400374379]
• 13: Roland W. Freund, A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM Journal on Scientific Computing, v.14 n.2, p.470-482, March 1993 [doi>10.1137/0914029]
• 14: Freund, R. and Nachtigal, N. 1991. QMR: A quasi-minimal residual method for non-Hermitian linear systems. Numer. Math. 60, 315--339.
• 15: Gertz, E. M. and Wright, S. J. 2001. OOQP User Guide. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill., September 2001. Available from http://www.cs.wisc.edu/∼swright/OOQP/.
• 16: Gockenbach, M. and Symes, W. 1999. An overview of HCL1.0. ACM Trans. Math. Softw. 25, 191--212.
• 17: Jacek Gondzio, Multiple centrality corrections in a primal-dual method for linear programming, Computational Optimization and Applications, v.6 n.2, p.137-156, Sept. 1996
• 18: Gondzio, J. and Sarkissian, R. 2002. Parallel interior-point solver for structured linear programs. Tech. Rep. MS-2000-025, Department of Mathematics and Statistics, The University of Edinburgh, Edinburgh, U.K., to appear in Math. Prog.
• 19: HSL: A collection of Fortran codes for large scale scientific computation, 2000. Full details in http://www.numerical.rl.ac.uk/hsl.
• 20: Kelley, C. T. 1995. Iterative Methods for Linear and Nonlinear Equations. Frontiers in Applied Mathematics, No. 16. SIAM Publications, Philadelphia, Pa.
• 21: W. Li , J. J. Swetits, The Linear l₁ Estimator and the Huber M-Estimator, SIAM Journal on Optimization, v.8 n.2, p.457-475, 1998 [doi>10.1137/S1052623495293160]
• 22: Olvi L. Mangasarian , David R. Musicant, Robust Linear and Support Vector Regression, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.9, p.950-955, September 2000 [doi>10.1109/34.877518]
• 23: Maros, I. and Mészáros, C. 1999. A repository of convex quadratic programming problems. Optim. Meth. Softw. 11, and 12(Dec.) 671--681.
• 24: Mehrotra, S. 1992. On the implementation of a primal-dual interior point method. SIAM J. Optim. 2, 575--601.
• 25: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 26: Homer F. Walker, Implementation of the GMRES method using householder transformations, SIAM Journal on Scientific and Statistical Computing, v.9 n.1, p.152-163, January 1988 [doi>10.1137/0909010]
• 27: Stephen J. Wright, Primal-dual interior-point methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 28: Wright, S. J. 2001. On reduced convex QP formulations of monotone LCPs. Math. Prog. 90, 459--473.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Quadratic programming methods
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design

Keywords:
Interior-Point Methods, Object-Oriented Software, Quadratic Programming