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$.
Citation
Working paper, Dept. of Management Sciences, University of Iowa, June 2001
Article
View Improved complexity for maximum volume inscribed ellipsoids