Quantified Constraints Under Perturbation

Stefan Ratschan

Quantified constraints (i.e., first-order formulae over the real numbers) are often exposed to perturbations: Constants that come from measurements usually are only known up to certain precision, and numerical solvers only compute with approximations of real numbers. In the talk we study the behavior of quantified constraints under perturbation by showing that one can formulate the problem of solving quantified constraints as a nested parametric optimization problem followed by one sign computation. Using the fact that minima and maxima are stable under perturbation, but the sign of a real number is stable only for non-zero inputs, we derive practically useful conditions for the stability of quantified constraints under perturbation.