Abstract:

We consider convex optimization problems in conic form. That is, the feasible set is the intersection of an affine subspace and a pointed closed convex cone K having nonempty interior. Nesterov and Nemirovskii showed that a self-concordant barrier function F exists for any such K, and one can use F to design primal-dual interior-point methods having polynomial iteration complexity. Such interior-point methods require the solution of linear systems of equations involving the gradient and Hessian of F. We show that if the gradient and Hessian are only known approximately, one can still apply an interior-point method to generate an ε-optimal solution in a polynomial number of iterations, provided the errors in the approximations are not too large.

We present two applications, including that of estimating the gradient and Hessian of the universal barrier function of Nesterov and Nemirovskii, which is written in terms of a multidimensional integral, by a Monte Carlo method.