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

DOI10.1007/S10107-014-0798-5MaRDI QIDQ494343zbMATH OpenOpenAlexFDO

Authors Jean B. Lasserre

Publication date 31 August 2015

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.1056

zbMATH Keywords

approximation of semialgebraic setssemidefinite programming

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Semidefinite programming (90C22)

Abstract: We address the following generalization $P$ of the Lowner-John ellipsoid problem. Given a (non necessarily convex) compact set $Ksubset{R}^n$ and an even integer $d$, find an homogeneous polynomial $g$ of degree $d$ such that $KsubsetG:=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-1choosed$ contacts points in $KcapG$ is also provided. This is the analogue for $dextgreater2$ 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 $ain{R}^n$ such that $Ksubset{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.

Review text

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.

Recommendations

• Ellipsoid coverings with minimal volumina.
• Realization of configurations and the Löwner ellipsoid
• Publication:4863222
• Best approximation of functions by log-polynomials
• Publication:5751510

Cites work

• A note on the least squares fitting of ellipses
• A random polynomial-time algorithm for approximating the volume of convex bodies
• A semidefinite approach for truncated \(K\)-moment problems
• Approximate volume and integration for basic semialgebraic sets
• Complex analysis. Transl. from the German by Dan Fulea
• Computation of Minimum-Volume Covering Ellipsoids
• Computing the volume, counting integral points, and exponential sums
• Convex Analysis
• Convex geometry and functional analysis
• Ellipsoidal approximation of the stability domain of a polynomial
• Ellipsoids of maximal volume in convex bodies
• Global optimization with polynomials and the problem of moments
• GloptiPoly 3: moments, optimization and semidefinite programming
• scientific article; zbMATH DE number 439380 (Why is no real title available?)
• scientific article; zbMATH DE number 4028501 (Why is no real title available?)
• scientific article; zbMATH DE number 3711829 (Why is no real title available?)
• scientific article; zbMATH DE number 465663 (Why is no real title available?)
• scientific article; zbMATH DE number 477581 (Why is no real title available?)
• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• scientific article; zbMATH DE number 715155 (Why is no real title available?)
• scientific article; zbMATH DE number 6846220 (Why is no real title available?)
• scientific article; zbMATH DE number 194744 (Why is no real title available?)
• scientific article; zbMATH DE number 3313523 (Why is no real title available?)
• Inner Approximations for Polynomial Matrix Inequalities and Robust Stability Regions
• John's decomposition of the identity in the non-convex case
• John's theorem for an arbitrary pair of convex bodies
• Least-squares fitting of circles and ellipses
• Löwner-John ellipsoids
• New and old results in resultant theory
• Pattern separation by convex programming
• Positive polynomials and robust stabilization with fixed-order controllers
• Recovering an homogeneous polynomial from moments of its level set
• Robust control of polytopic systems by convex optimization
• Robust pole assignment via reflection coefficients of polynomials
• Semidefinite Programming
• Smooth Optimization with Approximate Gradient
• The General Moment Problem, A Geometric Approach
• The proof of Tchakaloff’s Theorem
• What is the Laplace Transform?

Cited in

(9)

• Approximate optimal designs for multivariate polynomial regression
• Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension
• Best approximation of functions by log-polynomials
• An arithmetic proof of John's ellipsoid theorem
• Finding minimum volume circumscribing ellipsoids using generalized copositive programming
• Volume of sublevel sets of homogeneous polynomials
• Convex optimization and parsimony of L_p-balls representation
• Conic version of Loewner-John ellipsoid theorem
• The John inclusion for log-concave functions

Describes a project that uses

Uses Software

• GloptiPoly
• Polynomial Toolbox

This page was built for publication: A generalization of Löwner-John's ellipsoid theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494343)