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

Simon P. Schurr (spschurruwaterloo.ca)
Dianne P. O'Leary (olearycs.umd.edu)
Andr\'e Tits (andreumd.edu)

Abstract: 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.

Keywords: Conic optimization, self-concordant barrier function, interior-point method, inexact algorithm, polynomial time complexity

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization

Citation:

Download: [PDF]

Entry Submitted: 07/31/2007
Entry Accepted: 07/31/2007
Entry Last Modified: 04/29/2008

Modify/Update this entry