Set inversion

In mathematics, set inversion is the problem of characterizing the preimage X of a set Y by a function f, i.e., X = f⁻¹(Y ) = {x ∈ Rⁿ | f(x) ∈ Y }. It can also be viewed as the problem of describing the solution set of the quantified constraint "Y(f (x))", where Y( y) is a constraint, e.g. an inequality, describing the set Y.

In most applications, f is a function from Rⁿ to R^p and the set Y is a box of R^p (i.e. a Cartesian product of p intervals of R).

When f is nonlinear the set inversion problem can be solved^[1] using interval analysis combined with a branch-and-bound algorithm.^[2]

The main idea consists in building a paving of R^p made with non-overlapping boxes. For each box [x], we perform the following tests:

1. if f ([x]) ⊂ Y we conclude that [x] ⊂ X;
2. if f ([x]) ∩ Y = ∅ we conclude that [x] ∩ X = ∅;
3. Otherwise, the box [x] the box is bisected except if its width is smaller than a given precision.

To check the two first tests, we need an interval extension (or an inclusion function) [f ] for f. Classified boxes are stored into subpavings, i.e., union of non-overlapping boxes. The algorithm can be made more efficient by replacing the inclusion tests by contractors.