Interval contractor

In mathematics, an interval contractor (or contractor for short) associated to a set "X" is an operator "C" which associates to a box ["x"] in R"n" another box "C"(["x"]) of R"n" such that the two following properties are always satisfied
A "contractor associated to a constraint" (such as an equation or an inequality) is a 
contractor associated to the set "X" of all "x" which satisfy the constraint. 
Contractors make it possible to improve the efficiency of branch-and-bound
algorithms classically used in interval analysis.
Properties of contractors.
A contractor "C" is monotonic if we have 
formula_3
It is "minimal" if for all boxes ["x"], we have 
formula_4,
where ["A"] is the "interval hull" of the set "A", i.e., the smallest
box enclosing "A".
The contractor "C" is "thin" if for all points "x",
formula_5
where {"x"} denotes the degenerated box enclosing "x" as a single point.
The contractor "C" is "[[Idempotence|idempotent]]" if for all boxes ["x"], we have
formula_6
The contractor "C" is "[[Convergent matrix|convergent]]" if for all sequences ["x"]("k") of boxes containing "x", we have
formula_7
Illustration.
Figure 1 represents the set "X" painted grey and some boxes. Some of them of degenerated, i.e., they correspond to singletons. Figure 2 represents these boxes 
after [[contraction mapping|contraction]]. Note that no point of "X" has been removed by the contractor. The contractor
is minimal for the cyan box but is pessimistic for the green one. All degenerated blue boxes are contracted to
the empty box. The magenta box and the red box cannot be contracted.
[[File:Wiki contractor before.jpg|thumb|Figure 1: Boxes before contraction]]
[[File:Wiki contractor after.jpg|thumb|Figure 2: Boxes after contraction]]
Contractor algebra.
Some operations can be performed on contractors to build more complex contractors.
The [[intersection]], [[Union (set theory)|the union]], the [[Composition algebra|composition]] and the repetition are defined as follows.
Building contractors.
There exist different ways to build contractors associated to [[Equation|equations]] and [[Inequality (mathematics)|inequalities]],
say, "f"("x") in ["y"]. Most of them are based on interval arithmetic.
One of the most efficient and most simple is the "forward/backward contractor" (also 
called as HC4-revise). 
The principle is to evaluate "f"("x") using [[interval arithmetic]] (this is the forward step).
The resulting [[Interval (mathematics)|interval]] is [[Intersection (set theory)|intersected]] with ["y"]. A backward evaluation of "f"("x") is then performed 
in order to contract the intervals for the "x"i (this is the backward step). We now illustrate the principle on a simple example.
Consider the constraint
formula_12
We can evaluate the function "f"("x") by introducing the two intermediate
[[Dependent and independent variables|variables]] "a" and "b", as follows
The two previous constraints are called "forward constraints". We get the "backward constraints" 
by taking each forward constraint in the reverse order and isolating each variable on the right hand side. We get
The resulting forward/backward contractor 
formula_19
is obtained by
evaluating the forward and the backward constraints using [[Interval arithmetic|interval analysis]].
References.
[[Category:Arithmetic]]
[[Category:Computer arithmetic]]
[[Category:Optimization algorithms and methods]]
[[Category:Numerical analysis]]