Set inversion

Set inversion is the problem of characterizing the reciprocical image X of a set Y by a function f, i.e., X=f^-1(Y) = {x ∈ ℝⁿ | f(x) ∈ Y}.

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

When f is nonlinear the set inversion problem can be solved using interval analysis combined with a branch and bound algorithm.

The main idea consists in building a paving of ℝ^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.

Example The set X=f^-1([4,9]) where f(x₁ ,x₂) = x₁² + x₂² is represented on the figure.

A ring defined as a set inversion problem