A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations

In this work we develop a primal-dual short-step interior point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the barrier function is either impossible or too expensive. As our main contribution, we show that if approximate gradients and Hessians can be computed, and the relative errors in such quantities are not too large, then our algorithm has polynomial worst-case iteration complexity. As a special case, polynomial iteration complexity is proven when the gradient and Hessian can be evaluated exactly. Our algorithm requires no evaluation---or even approximate evaluation---of any quantities related to the barrier function for the dual cone, even for problems in which the cone is not self-dual.

Article

Download

View A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations