Improved complexity for maximum volume inscribed ellipsoids

K.M. Anstreicher (kurt-anstreicheruiowa.edu)

Abstract: Let $\Pcal=\{x | Ax\le b\}$, where $A$ is an $m\times n$ matrix. We assume that $\Pcal$ contains a ball of radius one centered at the origin, and is contained in a ball of radius $R$ centered at the origin. We consider the problem of approximating the maximum volume ellipsoid inscribed in $\Pcal$. Such ellipsoids have a number of interesting applications, including the inscribed ellipsoid method for convex optimization. We reduce the complexity of finding an ellipsoid whose volume is at least a factor $e^{-\epsilon}$ of the maximum possible to $O(m^{3.5}\ln(mR/\epsilon))$ operations, improving on previous results of Nesterov and Nemirovskii, and Khachiyan and Todd. A further reduction in complexity is obtained by first computing an approximation of the analytic center of $\Pcal$.

Keywords: Maximum volume inscribed ellipsoid, inscribed ellipsoid method

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Working paper, Dept. of Management Sciences, University of Iowa, June 2001

Download: [Postscript]

Entry Submitted: 06/14/2001
Entry Accepted: 06/14/2001
Entry Last Modified: 06/14/2001

Modify/Update this entry