An inexact interior-point algorithm for conic convex optimization problems

Abstract

In this dissertation we study an algorithm for convex optimization problems in conic form. (Without loss of generality, any convex problem can be written in conic form.) Our algorithm belongs to the class of interior-point methods (IPMs), which have been associated with many recent theoretical and algorithmic advances in mathematical optimization. In an IPM one solves a family of slowly-varying optimization problems that converge in some sense to the original optimization problem. Each problem in the family depends on a so-called <em>barrier function</em> that is associated with the problem data. Typically IPMs require evaluation of the gradient and Hessian of a suitable (``self-concordant'') barrier function. In some cases such evaluation is expensive; in other cases formulas in closed form for a suitable barrier function and its derivatives are unknown. We show that even if the gradient and Hessian of a suitable barrier function are computed <em>inexactly</em>, the resulting IPM can possess the desirable properties of polynomial iteration complexity and global convergence to the optimal solution set.

In practice the best IPMs are primal-dual methods, in which a convex problem is solved together with its dual, which is another convex problem. One downside of existing primal-dual methods is their need for evaluation of a suitable barrier function, or its derivatives, for the <em>dual</em> problem. Such evaluation can be even more difficult than that required for the barrier function associated with the original problem. Our primal-dual IPM does not suffer from this drawback---it does not require exact evaluation, or even estimates, of a suitable barrier function for the dual problem.

Given any convex optimization problem, Nesterov and Nemirovski showed that there exists a suitable barrier function, which they called the <em>universal barrier function</em>. Since this function and its derivatives may not be available in closed form, we explain how a Monte Carlo method can be used to estimate the derivatives. We make probabilistic statements regarding the errors in these estimates, and give an upper bound on the minimum Monte Carlo sample size required to ensure that with high probability, our primal-dual IPM possesses polynomial iteration complexity and global convergence.