Optimization Online


A generalization of the Lowner-John's ellipsoid theorem

Jean B Lasserre(lasserre***at***laas.fr)

Abstract: We address the following generalization $P$ of the Lowner-John's 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.

Keywords: homogeneous polynomials; Lowner-John's problem;

Category 1: Nonlinear Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 02/20/2013
Entry Accepted: 02/20/2013
Entry Last Modified: 02/20/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society