<p>Given a collection of <span class="math-container">$m$</span> ellipsoids in <span class="math-container">$\Bbb R^n$</span>, compute the maximum volume ellipsoid inscribed in their intersection.</p>
<hr />
<p>In section 8.4.2 of Boyd &amp; Vandenberghe's <a href="https://web.stanford.edu/%7Eboyd/cvxbook" rel="nofollow noreferrer">Convex Optimization</a>, this problem is listed as one of the few special cases of extremal ellipsoid 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?</p>

CC BY-SA 4.0
2023-06-24T20:50:33.257Z
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 followi
tomasantunes
CC BY-SA 4.0
2023-12-16T08:02:13.197Z
[Related](https://math.stackexchange.com/q/4632247/339790)
Rodrigo de Azevedo
<reference-request><convex-optimization>
Maximum volume ellipsoid in an intersection of ellipsoids
Andrea
# Maximum volume ellipsoid in an intersection of ellipsoids

(Asked by: username_0 on 2022-02-07)

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

---

In section 8.4.2 of Boyd & Vandenberghe's [Convex Optimization](https://web.stanford.edu/%7Eboyd/cvxbook), this problem is listed as one of the few special cases of extremal ellipsoid 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?

**Tags:** reference-request, convex-optimization

> **Comments:**
> **username_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 followi  
> **username_2**: [Related](https://math.stackexchange.com/q/4632247/339790)  

---

## 0 answers

