Journal article
Improved Complexity for Maximum Volume Inscribed Ellipsoids
SIAM journal on optimization, Vol.13(2), pp.309-320
01/01/2002
DOI: 10.1137/S1052623401390902
Abstract
Let ${\cal P}=\{x \,\vert\, Ax\le b\}$, where A is an m × n matrix. We assume that ${\cal P}$ contains a ball of radius one centered at the origin and is itself contained in a ball of radius R centered at the origin. We consider the problem of approximating the maximum volume ellipsoid inscribed in ${\cal P}$. Such ellipsoids have a number of interesting applications, including the inscribed ellipsoid method for convex optimization. We describe an optimization algorithm that obtains an ellipsoid whose volume is at least a factor $e^{-\epsilon}$ of the maximum possible in $O(m^{3.5}\ln(mR/\epsilon))$ operations. Our result provides an alternative to a saddlepoint-based approach with the same complexity, developed by Nemirovskii. We also show that a further reduction in complexity can be obtained by first computing an approximation of the analytic center of ${\cal P}$.
Details
- Title: Subtitle
- Improved Complexity for Maximum Volume Inscribed Ellipsoids
- Creators
- Kurt M Anstreicher
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.13(2), pp.309-320
- Publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.1137/S1052623401390902
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Language
- English
- Date published
- 01/01/2002
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380557802771
Metrics
3 Record Views