Name
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}$. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1137/S1052623401390902 | SIAM Journal on Optimization |
Keywords | Field | DocType |
optimization algorithm,n matrix,maximum volume,cal p,maximum volume ellipsoid,inscribed ellipsoid method,radius r,improved complexity,convex optimization,saddlepoint-based approach,inscribed ellipsoids,analytic center,interesting application | Discrete mathematics,Ellipsoid,Mathematical optimization,Matrix (mathematics),Inscribed figure,Optimization algorithm,Ellipsoid method,Convex optimization,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 2 | 1052-6234 |
Citations | PageRank | References |
6 | 1.71 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kurt M. Anstreicher | 1 | 633 | 86.40 |