Symmetry of convex sets and its applications to the extremal ellipsoids of convex bodies

Abstract

A convex body K in ℝ ⁿ has around it a unique circumscribed ellipsoid CE (K) with minimum volume and within it a unique inscribed ellipsoid IE (K) with maximum volume. The modern theory of these ellipsoids is pioneered by Fritz John in his 1948 seminal paper. This paper has two related goals. First, we investigate the symmetry properties of a convex body by studying its (affine) automorphism group Aut (K) and relate this group to the automorphism groups of its ellipsoids. We show that if Aut (K) is large enough, then the complexity of determining the ellipsoids CE (K) and IE (K) is greatly reduced, and in some cases, the ellipsoids can be determined explicitly. We then use this technique to compute the extremal ellipsoids associated with some classes of convex bodies that have important applications in convex optimization, namely when the convex body K is the part of a given ellipsoid between two parallel hyperplanes and when K is a truncated second-order cone or an ellipsoidal cylinder.

Keywords:

• circumscribed ellipsoid
• inscribed ellipsoid
• John ellipsoid
• Löwner ellipsoid
• minimum-volume ellipsoid
• maximum-volume ellipsoid
• optimality conditions
• semi-infinite programming
• contact points
• automorphism group
• symmetric convex bodies
• Haar measure

Subject Classifications::

• Primary: 90C34
• 46B20
• 90C30
• 90C46
• 65K10
• Secondary: 52A38
• 52A20
• 52A21
• 22C05
• 54H15

Acknowledgements

This research was partially supported by the National Science Foundation under grant DMS-0411955.