An inexact interior-point algorithm for conic convex optimization problems

An inexact interior-point algorithm for conic convex optimization problems

##### Files

##### Publication or External Link

##### Date

2006-10-02

##### Authors

Schurr, Simon Peter

##### Advisor

Tits, Andre L

O'Leary, Dianne P

O'Leary, Dianne P

##### Citation

##### DRUM DOI

##### 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.