Title of Presentation:Interior Point Methods for Mathematical Programming
26th European Conference on Operational Research
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.
Clóvis Gonzaga was born in Brazil in 1944. He is a full Professor at the Federal University of Santa Catarina, Brazil, having formerly been a professor at the Federal Univ. of Rio de Janeiro for 24 years. He had visiting positions at the University of California at Berkeley, at INRIA – France and at the Delft Technical University in Holland. He is a SIAM Fellow, Member of the Brazilian Academy of Sciences, of TWAS, and of the Brazilian National Order of Scientific Merit. He obtained a BSc in Electronic Engineering in 1967, DSc in Systems and Computation in 1973, and has been working on Continuous Optimization, both theoretical and applied to power systems planning. He has worked actively in the development of interior point methods for mathematical programming, and more recently on complexity based methods for continuous optimization.