Interior Point Methods (as seen by Renegar)

Interior point methods or IPMs are a class of iterative algorithms in optimization that follow an interior path (unlike the simplex method which follows the boundary). Von Neumann proposed an IPM for linear programming (LP) way back in 1948. Later IPMs were generalized for convex optimization, before their reappearance as fast LP solvers with Karmarkar's algorithm. Subsequently, Nesterov-Nemirovskii proved fast convergence of IPMs for convex optimization using "self-concordant barrier" functions.

In his book, Renegar revisits this very creative but mysterious work of Nesterov-Nemirovskii, and tries to demystify it from a mathematical viewpoint. I will try to explain this approach in my talk. The talk will be self-contained and assume only basic knowledge of linear algebra and vector calculus.