page_title: Set inversion
section_title: Example
hierarchical_section_title: Set inversion / Example
caption_attribution_description: English: A ring defined as a set inversion problem
context_page_description: In mathematics, set inversion is the problem of characterizing the preimage X of a set Y by a function f, i.e., X = f⁻¹ = {x ∈ Rⁿ | f(x) ∈ Y}. It can also be viewed as the problem of describing the solution set of the quantified constraint "Y", where Y is a constraint, for example, an inequality, describing the set Y.
  In most applications, f is a function from Rⁿ to Rᵖ and the set Y is a box 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ᵖ made with non-overlapping boxes. For each box [x], we perform the following tests:
  if f ⊂ Y we conclude that [x] ⊂ X;
  if f ∩ 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 [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.
context_section_description: The set X = f⁻¹([4,9]) where f(x₁, x₂) = x²
  ₁ + x²
  ₂ is represented on the figure.
  For instance, since [−2,1]² + [4,5]² = [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,√5]² = [0,1] + [4,5] = [4,6] is inside [4,9], we conclude that the whole box [-1,1] × [2,√5] is inside X.
caption: A ring defined as a set inversion problem
exif: {}