Skip to main content
SpringerLink
Log in

A dual-active-set algorithm for positive semi-definite quadratic programming

  • Published:
Mathematical Programming Submit manuscript

Abstract

Because of the many important applications of quadratic programming, fast and efficient methods for solving quadratic programming problems are valued. Goldfarb and Idnani (1983) describe one such method. Well known to be efficient and numerically stable, the Goldfarb and Idnani method suffers only from the restriction that in its original form it cannot be applied to problems which are positive semi-definite rather than positive definite. In this paper, we present a generalization of the Goldfarb and Idnani method to the positive semi-definite case and prove finite termination of the generalized algorithm. In our generalization, we preserve the spirit of the Goldfarb and Idnani method, and extend their numerically stable implementation in a natural way.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Boland, C.J. Goh and A.I. Mees, An algorithm for solving quadratic network flow problems,Applied Mathematics Letters 4 (1991) 61–64.

    Article  MATH  MathSciNet  Google Scholar 

  2. N. Boland, C.J. Goh and A.I. Mees, An algorithm for non-linear network programming: implementation, results and comparisons,Journal of the Operational Research Society 43 (1992) 979–992.

    Article  MATH  Google Scholar 

  3. N. Boland, Some problems in network optimization and quadratic programming, PhD Thesis, Department of Mathematics, University of Western Australia (1992).

  4. D. Burton and Ph.L. Toint, On an instance of the inverse shortest paths problem,Mathematical Programming 53 (1992) 45–61.

    Article  MATH  MathSciNet  Google Scholar 

  5. A.R. Conn, N.I.M. Gould, M. Lescrenier and Ph.L. Toint, Performance of a multifrontal scheme for partially separable optimization, Research Report CS-88-04, Computer Science Department, University of Waterloo (1988).

  6. A.R. Conn, N.I.M. Gould and Ph.L. Toint, An introduction to the structure of large scale nonlinear optimization problems and the LANCELOT project, Research Report CS-89-63, Computer Science Department, University of Waterloo (1989).

  7. A.R. Conn, N. Gould and Ph.L. Toint, Large-scale nonlinear constrained optimization, Research Report RAL-92-066, Rutherford Appleton Laboratory (1992).

  8. J. Demmel, Jacobis method is more accurate than QR,SIAM Journal on Matrix Analysis and Applications 13 (1992) 1204–1245.

    Article  MATH  MathSciNet  Google Scholar 

  9. R. Fletcher,Practical Methods of Optimization (Wiley, Chichester, 1987).

    MATH  Google Scholar 

  10. A.T. Ernst, X.Q. Yang and N.L. Boland, Exterior point methods for quadratic cost multicommodity flow, submitted for publication, 1996.

  11. P.E. Gill and W. Murray, Numerically stable methods for quadratic programming,Mathematical Programming 14 (1978) 349–372.

    Article  MATH  MathSciNet  Google Scholar 

  12. P.E. Gill, W. Murray and M. Wright,Practical Optimization (Academic Press, London, 1981).

    MATH  Google Scholar 

  13. P.E. Gill, W. Murray and M. Wright,Numerical Linear Algebra and Optimization (Addison-Wesley, Reading, MA, 1991).

    MATH  Google Scholar 

  14. D. Goldfarb and A. Idnani, A numerically stable dual method for solving strictly convex quadratic programs,Mathematical Programming 27 (1983) 1–33.

    Article  MATH  MathSciNet  Google Scholar 

  15. G.H. Golub and C.F. Van Loan,Matrix Computations (Johns Hopkins University Press, Baltimore, MD, 1989).

    MATH  Google Scholar 

  16. S.P. Han, Superlinearly convergent variable metric algorithms for general nonlinear programming problems,Mathematical Programming 11 (1976) 263–282.

    Article  MathSciNet  Google Scholar 

  17. S.P. Han, A globally convergent method for nonlinear programming,Journal of Optimization Theory and Applications 22 (1977) 297–309.

    Article  MATH  MathSciNet  Google Scholar 

  18. Y.Y. Lin and J.S. Pang, Iterative methods for large convex quadratic programs: a survey,SIAM Journal on Control and Optimization 25 (1987) 383–411.

    Article  MATH  MathSciNet  Google Scholar 

  19. W. Murray and F.J. Prieto, A sequential quadratic programming algorithm using incomplete solution of the subproblem, Technical Report SOL90-12, Operations Research Department, Stanford University (1990).

  20. B.N. Parlett,The Symmetric Eigenvalue Problem (Prentice-Hall, Englewood Cliffs, NJ, 1980).

    MATH  Google Scholar 

  21. M.J.D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, in: G.A. Watson, ed.,Numerical analysis Dundee 1977, Lecture Notes in Mathematics 630 (Springer, Berlin, 1977) 144–157.

    Google Scholar 

  22. M.J.D. Powell, The convergence of variable metric methods for nonlinearly constrained optimization calculations, in: O.L. Magasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming 3 (Academic Press, New York, 1978) 27–63.

    Google Scholar 

  23. M.J.D. Powell, Variable metric methods for constrained optimization, in: A. Bachen, M. Grotschel and B. Korte, eds.,Mathematical Programming: The State of the Art (Springer, Berlin, 1983) 288–311.

    Google Scholar 

  24. M.J.D. Powell, ZQPCVX: a Fortran subroutine for convex quadratic programming, Report DAMTP/1983/NA17, University of Cambridge (1983).

  25. M.J.D. Powell, On the quadratic programming algorithm of Goldfarb and Idnani,Mathematical Programming Study 25 (1985) 46–61.

    MATH  MathSciNet  Google Scholar 

  26. K. Schittkowski, The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function, Part I: convergence analysis,Numerische Mathematik 38 (1981) 83–114.

    Article  MATH  MathSciNet  Google Scholar 

  27. K. Schittkowski, On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function,Mathematische Operationsforschung und Statistik, Ser. Optimization 14 (1983) 197–216.

    MATH  MathSciNet  Google Scholar 

  28. J. Stoer, A dual algorithm for solving degenerate linearly constrained linear least squares problems,Journal of Numerical Linear Algebra with Applications 1 (1992) 103–131.

    MathSciNet  Google Scholar 

  29. Ph.L. Toint and D. Tuyttens, On large scale nonlinear network optimization,Mathematical Programming 48 (1990) 125–159.

    Article  MATH  MathSciNet  Google Scholar 

  30. R.B. Wilson, A simplicial algorithm for concave programming, Ph.D. Dissertation, Graduate School of Business Administration, Harvard University, Boston (1963).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Melbourne, 3052, Parkville, VIC, Australia

    N. L. Boland

Authors
  1. N. L. Boland
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported in part by ATERB, NSERC and the ARC.

Much of this work was done in the Department of Mathematics at the University of Western Australia and in the Department of Combinatorics and Optimization at the University of Waterloo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Boland, N.L. A dual-active-set algorithm for positive semi-definite quadratic programming. Mathematical Programming 78, 1–27 (1996). https://doi.org/10.1007/BF02614503

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02614503

Keywords

Search

Navigation