Abstract
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.
Key words: Interior Point Methods, Linear Programming, Quadratic Programming, Worst-case Complexity Analysis, Implementation, Matrix-Free Methods.