Semidefinite approximations of projections and polynomial images of semialgebraic sets
File(s)140992047.pdf (1 MB) 1507.06143v1.pdf (7.68 MB)
Published version
Accepted version
Author(s)
Magron, V
Henrion, D
Lasserre, J-B
Type
Journal Article
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.
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.
Date Issued
2015-10-29
Date Acceptance
2015-09-15
Citation
SIAM Journal on Optimization, 2015, 25 (4), pp.2143-2164
ISSN
1052-6234
Publisher
Society for Industrial and Applied Mathematics
Start Page
2143
End Page
2164
Journal / Book Title
SIAM Journal on Optimization
Volume
25
Issue
4
Copyright Statement
© 2015 Society for Industrial and Applied Mathematics
Subjects
math.OC
math.OC
Publication Status
Published