Convex Optimization 2026, 33 - Extremal Volume Ellipsoids

A minimum volume ellipsoid containing a set C that is bounded and has a nonempty interior, is its Lowner-John ellipsoid (𝔼_ij). The volume of any ellipsoid is proportional to det A^-1 given 𝔼 = {v : ||Av + b||₂ ≤ 1}. The minimum volume ellipsoid for C can be found by minimizing log det A^-1 with sup_c∈C ||Av + b||₂ ≤ 1. It's possible to compute the Lowner-John ellipsoid for a sum of ellipsoids (p 411). The Lowner-John ellipsoid for a convex set C with center x₀ can be shrunk by a factor of n around x₀, which produces an ellipsoid fully inside C. This approximation is 1/n-efficient (without further assumptions on C) (p. 412). If C is symmetric about x₀, the efficiency can be tightened to n^-1/2 (8.4.1).

An ellipsoid can be parametrized as the image of the unit ball under an affine transformation 𝔼 = {Bu + d : ||u||₂ ≤ 1}. The maximum volume ellipsoid inside C can be determined by maximizing log det B with sup_{||u||2 ≤ 1} I_C(Bu + d) ≤ 0 (p. 414). If C is a polyhedron {x : a_i^Tx ≤ b_i, i = 1, ..., m}, the constraint can be rewritten in a more convenient form ||Ba_i||₂ + a_i^Td ≤ b_i. This leads of course to an ellipsoidal inner approximation, which operates on the same efficiency as the outer approximation.