  


A generalization of the LownerJohn's ellipsoid theorem
Jean B Lasserre(lasserrelaas.fr) Abstract: We address the following generalization $P$ of the LownerJohn'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+d1\choose d}$ contacts points in $K\cap G$ is also provided. This is the analogue for $d>2$ of the LownerJohn'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(xa)\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; LownerJohn's problem; Category 1: Nonlinear Optimization Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Category 3: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 02/20/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  