Interior Point Methods for Mathematical Programming
Clovis C. Gonzaga

Interior point methods have been used to treat constrained nonlinear programming problems for about fifty years. These algorithms generate sequences of points which satisfy strictly the inequality constraints, as opposed to simplex like methods, which typically evolve on the boundary of the feasible set. They were initially based on the use of barrier functions to deal with the inequalities, and were applied to nonlinear problems with a small number of variables. In 1985, Karmarkar showed how to use interior points to solve the Linear Programming problem in polynomial time,for the first time challenging the supremacy of the simplex method in practical applications. This started a revolution in mathematical programming, which coincided with the decrease in cost of computation, which made powerful workstations accessible to all researchers. Interior point methods were then implemented for linear programming, and its realm spread to linear complementarity problems, semi-definite programming, conical problems and back to nonlinear programming. The problem sizes for linear programming grew from a maximum of some thousands of variables in 1980 to the 2008 record of one billion variables with hundreds of millions of constraints.

In this talk we present the basic ideas of interior point methods and a brief survey of their
evolution and state of the art.