Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Set inversion
Résumé
In mathematics, set inversion is the problem of characterizing the X of a set Y by a function f, i.e., X = f −1(Y ) = {x ∈ Rn | 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 Rn to Rp and the set Y is a box of Rp (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 Rp 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.
The set X = f −1([4,9]) where f (x1, x2) = x + x is represented on the figure.
For instance, since [−2,1]2 + [4,5]2 = [0,4] + [16,25] = [16,29] does not intersect the interval [4,9], we conclude that the box [−2,1] × [4,5] is outside X. Since [−1,1]2 + [2,]2 = [0,1] + [4,5] = [4,6] is inside [4,9], we conclude that the whole box [−1,1] × [2,] is inside X.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.