[DMO] Kees Roos: Search directions for primal-dual interior-point methods

15 November 2024 16:00 till 17:00 - Location: Chip | Add to my calendar

Up till 1984 the Simplex method was the only efficient method for solving linear optimization (LO) problems. In 1979 Khachiyan proposed the first polynomial-time method for LO, but it was computationally inferior to the Simplex method. Karmarkar proposed in 1984 a completely new (primal) polynomial-time method which was not only polynomial-time but also efficient in practice. This revolutionized the field of LO. Nowadays the most efficient methods, both in theory and practice, are primal-dual interior-point methods (IPMs). A big surprise was that these methods could also be extended to nonlinear (second-order cone and semidefinite) optimization problems. There exist two wide classes of search directions for IPMs. One is the class of methods that use ’kernel functions’, that have their origin in the well-known logarithmic barrier function, and the other class is based on the ’algebraically equivalent transformation’ (AET-) approach. We discuss the ideas underlying both approaches and their relation.