Interior methods for constrained optimization

TLDR

Interior methods, once popular in the 1960s and later eclipsed by the simplex method, fell out of favor in the 1970s but were revived in 1984 when Karmarkar introduced a fast polynomial‑time interior method, sparking renewed interest in barrier techniques. The paper surveys major themes in both classical and recent developments of interior methods for optimization. It reviews the theoretical foundations and practical implementations of interior methods, including barrier techniques and their modern extensions. Since 1984, studies have emphasized computational complexity, while implementations have shown high efficiency on large linear programs and success in nonlinear and combinatorial problems.

Abstract

Interior methods for optimization were widely used in the 1960s, primarily in the form of barrier methods. However, they were not seriously applied to linear programming because of the dominance of the simplex method. Barrier methods fell from favour during the 1970s for a variety of reasons, including their apparent inefficiency compared with the best available alternatives. In 1984, Karmarkar's announcement of a fast polynomial-time interior method for linear programming caused tremendous excitement in the field of optimization. A formal connection can be shown between his method and classical barrier methods, which have consequently undergone a renaissance in interest and popularity. Most papers published since 1984 have concentrated on issues of computational complexity in interior methods for linear programming. During the same period, implementations of interior methods have displayed great efficiency in solving many large linear programs of ever-increasing size. Interior methods have also been applied with notable success to nonlinear and combinatorial problems. This paper presents a self-contained survey of major themes in both classical material and recent developments related to the theory and practice of interior methods.