Tractable approximations of sets defined with quantifiers
Given a compact basic semi-algebraic set \(\mathbf {K}\subset \mathbb {R}^n\times \mathbb {R}^m\), a simple set \(\mathbf {B}\) (box or ellipsoid), and some semi-algebraic function \(f\), we consider sets defined with quantifiers, of the form $$\begin{aligned} \mathbf {R}_f:=\{\mathbf {x}\in \mathbf {B}&: f(\mathbf {x},\mathbf {y})\le 0 \,\, \text{ for } \text{ all } \,\, \mathbf {y}\,\, \text{ such } \text{ that }\quad (\mathbf {x},\mathbf {y})\in \mathbf {K}\}\\ \mathbf {D}_f:=\{\mathbf {x}\in \mathbf {B}&: f(\mathbf {x},\mathbf {y})\ge 0 \,\, \text{ for } \text{ some } \,\, \mathbf {y}\quad \text{ such } \text{ that }\quad (\mathbf {x},\mathbf {y})\in \mathbf {K}\}. \end{aligned}$$The former set \(\mathbf {R}_f\) is particularly useful to qualify robust decisions \(\mathbf {x}\) versus noise parameter \(\mathbf {y}\) (e.g. in robust optimization on some set \(\varvec{\Omega }\subset \mathbf {B}\)) whereas the latter set \(\mathbf {D}_f\) is useful (e.g. in optimization) when one does not want to work with its lifted representation \(\{(\mathbf {x},\mathbf {y})\in \mathbf {K}: f(\mathbf {x},\mathbf {y})\ge 0\}\). Assuming that \(\mathbf {K}_\mathbf {x}:=\{\mathbf {y}:(\mathbf {x},\mathbf {y})\in \mathbf {K}\}\ne \emptyset \) for every \(\mathbf {x}\in \mathbf {B}\), we provide a systematic procedure to obtain a sequence of explicit inner (resp. outer) approximations that converge to \(\mathbf {R}_f\) (resp. \(\mathbf {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 $$\begin{aligned} \mathbf {R}_F:=\{\mathbf {x}\in \mathbf {B}\,:\, (\mathbf {x},\mathbf {y})\in F \,\, \text{ for } \text{ all }\,\, \mathbf {y}\,\, \text{ such } \text{ that }\,\, (\mathbf {x},\mathbf {y})\in \mathbf {K}\} \end{aligned}$$where \(F\) is some other basic-semi algebraic set, and also sets defined with two quantifiers.
semi-algebraic set robust optimization semidefinite programming sets with quantifiers semi-algebraic optimization 90c22