A generalization of Löwner-John's ellipsoid theorem
In this remarkable work, the author considers the following geometric problem. Given a compact set \(K\) of \({\mathbb R}^n\) and an even integer \(d\), find a homogeneous polynomial \(g\) of degree \(d\) such that its unit sublevel set \(G:=\{x \in {\mathbb R}^n : g(x) \leq 1\}\) contains \(K\) and has minimal volume (i.e. Lebesgue measure). This turns out to be a finite-dimensional convex optimization problem, even though \(K\) is not assumed to be convex or connected. This follows from the observation that the volume of \(G\) is proportional to the integral \(\int_{{\mathbb R}^n} \exp(-g(x))dx\). Using first-order optimal conditions, the author then shows that this optimization problem has a unique optimal solution, and a tight upper bound on the number of contact points of \(K\) and \(G\) is also provided. Whereas finding the optimal set \(G\) boils down to solving a finite-dimensional convex optimization problem (whose decision variable is the homogeneous polynomial \(g\)), solving this optimization problem seems to be a challenge, the main difficulty being evaluation of integrals of exponentials of polynomials. Numerically, the optimal set \(G\) can however be approximated as closely as desired with a hierarchy of finite-dimensional semidefinite programming problems for which efficient interior-point algorithms are available. This work can be considered as a significant extension of the Löwner-John ellipsoid theorem stating that there exists a minimum volume ellipsoid \(G\) containing a given convex compact set \(K\). The extension is twofold. First, \(K\) is not assumed to be convex or connected. Second, \(G\) is not restricted to be the unit sublevel set of a degree \(2\) polynomial.
scientific article