The Interior-Point Revolution in Constrained Optimization: History, Recent Developments, and Lasting Consequences

Professor Margaret H Wright ( Silver Professor of Computer Science and chair of the Computer Science Department, Courant Institute of Mathematical Sciences, New York University )

Constrained optimization---finding the best value of an objective function subject to constraints---has undergone a sweeping change, often called the "interior-point revolution", starting in 1984 with Karmarkar's announcement of a genuinelyfast polynomial-time algorithm for linear programming. Interior-point methods have since provided a fascinating mixture of old and new ideas, with applications ranging from linear programming to approximation algorithms for NP-hard problems. This talk will describe the evolution of interior methods from the controversies of 1984 to the present, hoping to convey the excitement that remains after almost 20 years of intense, at times frenzied, research. In honour of the occasion, I shall try to indicate how research in optimization supports Christopher Strachey's famous comment that "the separation of practical and theoretical work is artificial and injurious".