Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An interior point method for general large-scale quadratic programming problems

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper, we present an interior point algorithm for solving both convex and nonconvex quadratic programs. The method, which is an extension of our interior point work on linear programming problems efficiently solves a wide class of largescale problems and forms the basis for a sequential quadratic programming (SQP) solver for general large scale nonlinear programs. The key to the algorithm is a three-dimensional cost improvement subproblem, which is solved at every interation. We have developed an approximate recentering procedure and a novel, adaptive big-M Phase I procedure that are essential to the sucess of the algorithm. We describe the basic method along with the recentering and big-M Phase I procedures. Details of the implementation and computational results are also presented.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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. P.D. Domich, P.T. Boggs, J.E. Rogers and C. Witzgall, Optimizing over three-dimensional subspaces in an interior-point method for linear programming, Linear Algebra and its Applications 152 (1991).

  2. P.T. Boggs, P.D. Domich, J.E. Rogers and C. Witzgall, An interior point method for linear and quadratic programming problems. Mathematical Programming Society Committee on Algorithms Newsletter 19 (1991) 32–40.

    Google Scholar 

  3. P.T. Boggs, JW. Tolle and A.J. Kearsley, A practical algorithm for general large-scale nonlinear optimization problem, NISTIR 5407, National Institute of Standards and Technology (1994), to appear in SIAM Journal of Optimization.

  4. P.T. Boggs, J.W. Tolle and A.J. Kearsley, A truncated SQP algorithm for large-scale nonlinear programming problems, in:Advances in Optimization and Numerical Analysis: Proc 6th Workshop on Optimization and Numerical Analysis, Oaxaco, Mexico (Kluwer Academic Dordrecht, The Netherlands, 1994).

    Google Scholar 

  5. R. Fletcher,Practical Methods of Optimization, 2nd ed. (Wiley, New York, 1987).

    Google Scholar 

  6. P. Huard, Resolution of mathematical programming with nonlinear constraints by the method of centres, in:Nonlinear Programming, ed. J. Abadie (North-Holland Amsterdam, 1967) pp. 209–219.

    Google Scholar 

  7. R.J. Vanderbeei, Interior-point methods: Algorithms and formulations, ORSA Journal of Computing 6 (1994) 32–34.

    Google Scholar 

  8. R.J. Vanderbei and T.J. Carpenter, Symmetric indefinite systems for interior-point methods Mathematical Programming 58 (1993) 1–32.

    Google Scholar 

  9. D.F. Shanno, private communication (1991).

  10. K.M. Anstreicher, D. den Hertog and C. Roos, A long step barrier method for convex quadratic programming, Algorithmica 10 (1993) 365.

    Google Scholar 

  11. K.M. Anstriecher, On long step path following and SUMT for linear and quadratici programming, Manuscript, Yale School of Organization and Management (August 1990).

  12. T.F. Coleman and J. Liu, An interior Newton method for quadratic programming, Technical Report TR 93-1388, Cornell University (October 1993).

  13. I. Adler, M.G.C. Resende and G. Veiga, An implementatio of Karmarkar's algorithm for linear programming, Mathematical Programming 44 (1989) 297–335.

    Google Scholar 

  14. R.H.F. Jackson and G.P. McCormick, The polyadic structure of factorable function tensors with applications to higher-order minimization techniques. Journal of Optimization Theory and Applications 51 (1986) 63–93.

    Google Scholar 

  15. T. Ishihara and M. Kojima, On the bigM in the affine scaling algorithm, Mathematical Protramming 62 (1993) 85–94.

    Google Scholar 

  16. M. Kojima, S. Mizuno and A. Yoshise, A little theorem of the bigM in interior point algorithms, Mathematical Programming 59 (1993) 361–375

    Google Scholar 

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

  18. A.V. Fiacco and G.P. McCormick,Nonlinear Programming Sequential Unconstrained Minimization Techniques (Wiley, New York, 1968).

    Google Scholar 

  19. J. Vlach and K. Singhal,Computer Methods for Circuit Analysis and Design (Van Nostrand Reinhold, New York, 1983).

    Google Scholar 

  20. SMPAK User's Guide Version 1.0 (1985).

  21. P.T. Boggs, P.D. Domich, J.R. Donaldson and C. Witzgall, Algorithmic enhancements to the method of centers for linear programming, ORSA Journal on Computing 1 (1989) 159–171.

    Google Scholar 

  22. J.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a primal-dual interior point method for linear programming, Linear Algebra and its Applications 152 (1991) 191–222.

    Google Scholar 

  23. R.E. Marsten, M.J. Saltzman, D.F. Shanno, G.S. Pierce and J.F. Ballintijn, Implementation of a dual affine interior point algorithm for linear programmin, ORSA Journal on Computing 1 (1990) 287–297.

    Google Scholar 

  24. A. Marxen, Primal barrier methods for linear programming, Ph.D. Thesis, Department of Operations Research, Stanford University, Stanford, CA (1989).

    Google Scholar 

  25. D.M. Gay, Electronic mail distribution of linear programming test problems, Mathematical Programming Society COAL Newsletter 13 (December 1985).

Download references

Author information

Authors and Affiliations

  1. Applied and Computational Mathematics Divison, National Institute of Standards and Technology, 20899, Gaithersburg, MD, USA

    Pault T. Boggs

  2. Applied and Computational Mathematics Division, National Institute of Standards and Technology, 80303-3328, Boulder, CO, USA

    Paul D. Domich & Janet E. Rogers

Authors
  1. Pault T. Boggs
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paul D. Domich
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Janet E. Rogers
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Contribution of the National Institute of Standards and Tedchnology and not subject to copyright in the United States. This research was supported in part by ONR Contract N-0014-87-F0053.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Boggs, P.T., Domich, P.D. & Rogers, J.E. An interior point method for general large-scale quadratic programming problems. Ann Oper Res 62, 419–437 (1996). https://doi.org/10.1007/BF02206825

Download citation

  • Issue Date:

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

Key words

Search

Navigation