Symmetric indefinite systems for interior point methods

Robert J. Vanderbei, Tamra J. Carpenter

Research output: Contribution to journalArticlepeer-review

83 Scopus citations

Abstract

We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is {Mathematical expression} instead of reducing to obtain the usual AD2AT system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the product AD2AT when A has dense columns; and (2) it can easily be used to solve nonseparable quadratic programs since it requires only that D be symmetric. We also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense.

Original languageEnglish (US)
Pages (from-to)1-32
Number of pages32
JournalMathematical Programming
Volume58
Issue number1-3
DOIs
StatePublished - Jan 1993

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Keywords

  • Interior point method
  • linear programming
  • quadratic programming

Fingerprint

Dive into the research topics of 'Symmetric indefinite systems for interior point methods'. Together they form a unique fingerprint.

Cite this