Tractable approximations of sets defined with quantifiers

• 成果类型: Article
• 署名作者: Lasserre, Jean B.
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite de Toulouse
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0838-1
• 发表日期: 2015
• 页码: 507-527
• 关键词: polynomial matrix inequalities

摘要

Given a compact basic semi- algebraic set K subset of R-n x R-m, a simple set B (box or ellipsoid), and some semi- algebraic function f, we consider sets defined with quantifiers, of the form R-f := {x is an element of B : f (x, y) <= 0 for all y such that (x, y) is an element of K} D-f := {x is an element of B : f (x, y) >= 0 for some y such that (x, y) is an element of K}. The former set R-f is particularly useful to qualify robust decisions x versus noise parameter y (e. g. in robust optimization on some set Omega subset of B) whereas the latter set Df is useful (e. g. in optimization) when one does not want to work with its lifted representation {(x, y) is an element of K : f (x, y) >= 0}. Assuming that K-x := {y : (x, y) is an element of K} not equal empty set for every x is an element of B, we provide a systematic procedure to obtain a sequence of explicit inner (resp. outer) approximations that converge to R-f (resp. D-f) in a strong sense. Another (and remarkable) feature is that each approximation is the sublevel set of a single polynomial whose vector of coefficients is an optimal solution of a semidefinite program. Several extensions are also proposed, and in particular, approximations for sets of the form R-F := {x is an element of B : (x, y) is an element of F for all y such that (x, y) is an element of K} where F is some other basic-semi algebraic set, and also sets defined with two quantifiers.