4
$\begingroup$

I have an $n$-dimensional ellipsoid $E$ and a hyperplane $H$. This hyperplane cuts $E$ into two parts: $E_1$ and $E_2$ (whose disjoint union is $E$). I want to find another ellipsoid $E'$ that has minimal hyper-volume and contains $E_1$. Is there an efficient algorithm to do this?

My first thought was to formulate it as an optimization problem, but I am having difficulty with formulating it, as I don't know how to formulate the containment ($E_1 \subseteq E'$) constraint.

An approximation for the minimal hyper-volume ellipsoid is also good for my needs.

$\endgroup$
2
$\begingroup$

Your are describing the basic step in the ellipsoid algorithm. Your question might be answered in lecture notes on the algorithm, such as these ones by Goemans.

More generally, given a convex body $K$, the minimum volume ellipsoid containing it is called the Löwner–John ellipsoid. The same name is also given to the maximum volume ellipsoid contained in $K$. See for example these lecture notes of Boyd and Vandenberghe.

$\endgroup$
  • $\begingroup$ Thank you for telling me about the similar case found in the Ellipsoid algorithm! However, in your link and in others found in the Web, the theorem is not formulated for the general case. That is, only the case where the hyperplane contains the ellipsoid's center is considered. Do you know how to generalize it to the general case? Or, where can I find a formula for the ellipsoid form in the general case? $\endgroup$ – Dudi Frid Aug 21 '16 at 15:07
  • $\begingroup$ The general case is known as the Löwner–John ellipsoid, or sometimes the Fritz John ellipsoid. There are actually two ellipsoids (circumscribed and circumscribing), but presumably the two cases are dual. $\endgroup$ – Yuval Filmus Aug 21 '16 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.