A generalization of Löwner-John's ellipsoid theorem
type: Item
instance of: scholarly article
title: A generalization of Löwner-John's ellipsoid theorem
zbMATH Open document ID: 1337.90049
published in: Mathematical Programming. Series A. Series B
publication date: 2015-08-31T00:00:00Z
full work available at URL: https://arxiv.org/abs/1302.1056
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.
reviewed by: Didier Henrion
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 65K10
zbMATH DE Number: 6477223
zbMATH Keywords: approximation of semialgebraic sets
zbMATH Keywords: semidefinite programming
describes a project that uses: GloptiPoly
describes a project that uses: Polynomial Toolbox
author: Jean B. Lasserre
MaRDI profile type: Publication
OpenAlex ID: W2084193898
arXiv ID: 1302.1056
cites work: Q4271953
cites work: Smooth Optimization with Approximate Gradient
cites work: Q4606219
cites work: Ellipsoids of maximal volume in convex bodies
cites work: Convex geometry and functional analysis
cites work: Computing the volume, counting integral points, and exponential sums
cites work: John's decomposition of the identity in the non-convex case
cites work: The proof of Tchakaloff’s Theorem
cites work: Q3902884
cites work: John's theorem for an arbitrary pair of convex bodies
cites work: A random polynomial-time algorithm for approximating the volume of convex bodies
cites work: Q4321748
cites work: Complex analysis. Transl. from the German by Dan Fulea
cites work: Least-squares fitting of circles and ellipses
cites work: A semidefinite approach for truncated \(K\)-moment problems
cites work: Löwner-John ellipsoids
cites work: GloptiPoly 3: moments, optimization and semidefinite programming
cites work: Approximate Volume and Integration for Basic Semialgebraic Sets
cites work: Ellipsoidal approximation of the stability domain of a polynomial
cites work: Inner Approximations for Polynomial Matrix Inequalities and Robust Stability Regions
cites work: Positive polynomials and robust stabilization with fixed-order controllers
cites work: Q3141900
cites work: Q4273942
cites work: Robust control of polytopic systems by convex optimization
cites work: Q3769679
cites work: The General Moment Problem, A Geometric Approach
cites work: Global optimization with polynomials and the problem of moments
cites work: Recovering an homogeneous polynomial from moments of its level set
cites work: New and old results in resultant theory
cites work: Robust pole assignment via reflection coefficients of polynomials
cites work: Q4285035
cites work: Convex Analysis
cites work: Pattern separation by convex programming
cites work: A note on the least squares fitting of ellipses
cites work: Q4692741
cites work: Q5593890
cites work: Computation of Minimum-Volume Covering Ellipsoids
cites work: Semidefinite Programming
cites work: What is the Laplace Transform?
DOI: 10.1007/S10107-014-0798-5
description: scientific article