Tractable approximations of sets defined with quantifiers

Abstract

Given a compact basic semi-algebraic set $K\subset R^n\times 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\in B: \mbox{$f(x,y)\leq 0$forall$y$suchthat$(x,y)\in K$}\}$ and $D_f:=\{x\in B: \mbox{$f(x,y)\geq 0$forsome$y$suchthat$(x,y)\in 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 $\mathbf{\Omega }\subset B$) whereas the latter set $D_f$ is useful (e.g. in optimization) when one does not want to work with its lifted representation $\{(x,y)\in K:f(x,y)\ge 0\}$. Assuming that $K_x:=\{y:(x,y)\in K\}\ne \varnothing$ for every $x\in 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\in B:\mbox{$(x,y)\in F$forall$y$suchthat$(x,y)\in K$}\}$, where $F$ is some other basic-semi algebraic set, and also sets defined with two quantifiers.

Cited by in corpus (1)

• Synthesis-guided Adversarial Scenario Generation for Gray-box Feedback Control Systems with Sensing Imperfections