Semidefinite Approximations of Projections and Polynomial Images of SemiAlgebraic Sets

Given a compact semialgebraic set S of R^n and a polynomial map f from R^n 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'&#...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on optimization 2015-01, Vol.25 (4), p.2143-2164
Main Authors: Magron, Victor, Henrion, Didier, Lasserre, Jean-Bernard
Format: Article
Language:English
Subjects:
Mathematics
Optimization and Control
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a compact semialgebraic set S of R^n and a polynomial map f from R^n 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^1 norm on B, when the degree of the polynomial approximation tends to infinity. Several examples of applications are provided, together with numerical experiments.
ISSN:1052-6234
1095-7189
DOI:10.1137/140992047