4
$\begingroup$

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, 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?

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Jun 24, 2023 at 20:50
  • $\begingroup$ Related $\endgroup$ Dec 16, 2023 at 8:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.