Extremal Ellipsoids

Question

I'm considering the following problem.

Given a collection of $m$ ellipsoids in $R^n$, compute the maximum volume ellipsoid inscribed in their intersection.

In Boyd & Vandenberghe, Convex Optimization (section 8.4.2) this problem is listed as one of the few special cases of extremal ellipsoids problems that can be solved efficiently.

However I'm struggling to find a reference with an explicit bound on the running time.

Are you aware of any such result? Could you please point me out some specific reference?

Many thanks in advance.

Answer 1

Finding an ellipsoid of maximum volume inscribed in the intersection of given ellipsoids is indeed a special case of extremal ellipsoid problems. This is an instance of convex optimization problem which can be formulated as semidefinite programming (SDP) problem.

The problem of finding a maximum volume inscribed ellipsoid can be solved efficiently by various SDP solvers such as SeDuMi, CVX, MOSEK, etc. The worst-case running time for such SDP problems is typically polynomial in the size of the input.

For theoretical bounds on the running time of semidefinite programming algorithms, the following references might be helpful:

• Nesterov, Y., and Nemirovski, A., "Interior-Point Polynomial Algorithms in Convex Programming", SIAM Studies in Applied Mathematics, 1994. This book provides foundational results on interior point methods for convex optimization, including semidefinite programming.

• Ben-Tal, A., and Nemirovski, A., "Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications", MPS-SIAM Series on Optimization, 2001. This book also contains extensive discussions on semidefinite programming, including complexity analysis of some algorithms.