Minimum enclosing ellipsoid to maximal enclosed ellipsoid

Question

Given a convex body $K$ and an ellipsoid of minimal volume which contains $K$, find the maximal ellipsoid contained in $K$.

I have tried to multiply the matrix by 4 (since the eigenvalues are the reciprocals of the squares of the semi-axes, but I don't get the maximal ellipsoid.

If you need to compute the minimal containing ellipsoid, please refer to here

Thanks in advance.

Answer 1

Consider the yellow and orange convex figures, which have the same bounding ellipsoid but different bounded ellipsoids.

Therefore, given just the bounding ellipsoid you cannot determine the bounded ellipsoid. (Nor vice versa.) You must know the figure $K$.

A better, limiting, example: Suppose $K$ is an ellipsoid. Then the bounding ellipsoid and the bounded ellipsoid are the same!

Answer 2

Here is a reasonable conjecture in dimension $2$:

For an equilateral triangle $T$ the smallest circumscribed ellipse is the circumcircle, and the largest inscribed ellipse is the incircle. The area ratio between these two is $4$.

Conjecture: Let $K\subset{\mathbb R}^2$ be convex and compact, and let $A_{\rm circum}(K)$, resp $A_{\rm inscr}(K)$, be the areas of the smallest circumscribed ellipse, resp., the largest inscribed ellipse. Then $${A_{\rm circum}(K)\over A_{\rm inscr}(K)}\leq4\ .$$

Answer 3

David has offered the correct answer geometrically, and I'd say he deserves the checkmark :-) But I did want to address this from a computational point of view.

The computational complexity of computing either the minimum volume circumscribed ellipsoid (MinVCE) or the maximum volume inscribed ellipsoid (MaxVIE) depends greatly on the way the underlying convex volume is described. And generally, only one of the exact ellipsoids yields a tractable solution. I can't think of a non-trivial case where computing both ellipsoids is tractable.

For instance, the minimum volume circumscribing ellipsoid is tractable for the following cases:

• A finite set of points $x_1,x_2,\dots, x_m$;
• A convex polyhedron described by its vertices (this is really the same as the previous case);
• The union of a finite number of ellipsoids.

Conversely, the maximum volume inscribing ellipsoid is tractable for the following cases:

• A convex polyhedron described by its faces (e.g., a set of linear inequalities);
• The intersection of a finite number of ellipsoids.

Source: Boyd & Vandenberghe, Convex Optimization, chatper 8.