Semidefinite approximations of projections and polynomial images of semialgebraic sets

2015/07/22 by Magron, Victor, Henrion, Didier, Lasserre, Jean-Bernard · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1507.06143

Abstract

Given a compact semialgebraic set S of Rⁿ and a polynomial map f from Rⁿ to R^m, we consider the problem of approximating the image set F = f(S) in R^m. This includes in particular the projection of S on R^m for n greater than m. Assuming that F is included in a set B which is "simple" (e.g. a box or a ball), we provide two methods to compute certified outer approximations of F. Method 1 exploits the fact that F can be defined with an existential quantifier, while Method 2 computes approximations of the support of image measures.The two methods output a sequence of superlevel sets defined with a single polynomial that yield explicit outer approximations of F. Finding the coefficients of this polynomial boils down to computing an optimal solution of a convex semidefinite program. We provide guarantees of strong convergence to F in L¹ norm on B, when the degree of the polynomial approximation tends to infinity. Several examples of applications are provided, together with numerical experiments.

Cited by

• KL and Lyapunov Approaches for Discrete-time Peak Computation Problems

Related

• Inner and Outer Approximations of Star-Convex Semialgebraic Sets
• Algebraic approximation preserving dimension
• Semidefinite Approximations of Reachable Sets for Discrete-time\n Polynomial Systems
• Tractable approximations of sets defined with quantifiers
• Simple Approximations of Semialgebraic Sets and their Applications to Control