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''^−1(''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^''n'' 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
using interval analysis combined with a branch-and-bound algorithm.

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:
# if ''f'' ( 'x'' ⊂ ''Y'' we conclude that 'x''⊂ ''X'';
# if ''f'' ( 'x'' ∩ ''Y'' = ∅ we conclude that 'x''∩ ''X'' = ∅;
# 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.

Example

The set ''X'' = ''f''^−1( ,9 where ''f'' (''x''₁, ''x''₂) = ''x'' + ''x'' is represented on the figure.

For instance, since ˆ’2,1sup>2 + ,5sup>2 = ,4+ 6,25= 6,29does not intersect the interval ,9 we conclude that the box ˆ’2,1thinsp;×  ,5is outside ''X''. Since ˆ’1,1sup>2 + ,sup>2 = ,1+ ,5= ,6is inside ,9 we conclude that the whole box ˆ’1,1thinsp;×  ,is inside ''X''.

Application

Set inversion is mainly used for path planning, for nonlinear parameter set estimation, for localization
or for the characterization of stability domains of linear dynamical systems.

References

{{Reflist, 2

Topology