Semidefinite approximations of projections and polynomial images of semialgebraic sets
Abstract: 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.
Keywords: Semialgebraic sets; semidefinite programming; moment relaxations; polynomial sum of squares.
Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Entry Submitted: 10/17/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|