Skip to Main content Skip to Navigation
New interface
Journal articles

A generalization of Löwner-John's ellipsoid theorem

Jean-Bernard Lasserre 1 
1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : We address the following generalization $P$ of the Lowner-John ellipsoid problem. Given a (non necessarily convex) compact set $K\subset R^n$ and an even integer $d$, find an homogeneous polynomial $g$ of degree $d$ such that $K\subset G:=\{x:g(x)\leq1\}$ and $G$ has minimum volume among all such sets. We show that $P$ is a convex optimization problem even if neither $K$ nor $G$ are convex! We next show that $P$ has a unique optimal solution and a characterization with at most ${n+d-1\choose d}$ contacts points in $K\cap G$ is also provided. This is the analogue for $d>2$ of the Lowner-John's theorem in the quadratic case $d=2$, but importantly, we neither require the set $K$ nor the sublevel set $G$ to be convex. More generally, there is also an homogeneous polynomial $g$ of even degree $d$ and a point $a\in R^n$ such that $K\subset G_a:=\{x:g(x-a)\leq1\}$ and $G_a$ has minimum volume among all such sets (but uniqueness is not guaranteed). Finally, we also outline a numerical scheme to approximate as closely as desired the optimal value and an optimal solution. It consists of solving a hierarchy of convex optimization problems with strictly convex objective function and Linear Matrix Inequality (LMI) constraints.
Document type :
Journal articles
Complete list of metadata
Contributor : Jean Bernard Lasserre Connect in order to contact the contributor
Submitted on : Monday, December 22, 2014 - 3:11:48 PM
Last modification on : Tuesday, October 25, 2022 - 11:58:11 AM
Long-term archiving on: : Monday, March 23, 2015 - 7:32:29 PM


Files produced by the author(s)



Jean-Bernard Lasserre. A generalization of Löwner-John's ellipsoid theorem. Mathematical Programming, Series A, 2015, 152, pp.559--591. ⟨10.1007/s10107-014-0798-5⟩. ⟨hal-00785158v5⟩



Record views


Files downloads