Interior Point Methods 25 Years Later

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Interior point methods for optimization have been around for more than 25 years now. Their presence has shaken up the field of optimization. Interior point methods for linear and (convex) quadratic programming display several features which make them particularly attractive for very large scale optimization. Among the most impressive of them are their low-degree polynomial worst-case complexity and an unrivalled ability to deliver optimal solutions in an almost constant number of iterations which depends very little, if at all, on the problem dimension. Interior point methods are competitive when dealing with small problems of dimensions below one million constraints and variables and are beyond competition when applied to large problems of dimensions going into millions of constraints and variables.

In this survey we will discuss several issues related to interior point methods including the proof of the worst-case complexity result, the reasons for their amazingly fast practical convergence and the features responsible for their ability to solve very large problems. The ever-growing sizes of optimization problems impose new requirements on optimization methods and software. In the final part of this paper we will therefore address a redesign of interior point methods to allow them to work in a matrix-free regime and to make them well-suited to solving even larger problems.
Original languageEnglish
Pages (from-to)587-601
Number of pages15
JournalEuropean Journal of Operational Research
Volume218
Issue number3
DOIs
Publication statusPublished - May 2012

Keywords / Materials (for Non-textual outputs)

  • Interior point methods
  • Linear programming
  • Quadratic programming
  • Worst-case complexity analysis
  • Implementation
  • Matrix-free methods

Fingerprint

Dive into the research topics of 'Interior Point Methods 25 Years Later'. Together they form a unique fingerprint.

Cite this