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 metadatas

https://hal.archives-ouvertes.fr/hal-00785158
Contributor : Jean Bernard Lasserre <>
Submitted on : Monday, December 22, 2014 - 3:11:48 PM
Last modification on : Friday, January 10, 2020 - 9:10:08 PM
Long-term archiving on: Monday, March 23, 2015 - 7:32:29 PM

Files

lowner-correct.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00785158, version 5
  • ARXIV : 1302.1056

Citation

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

Share

Metrics

Record views

315

Files downloads

313