Interval Contractor
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, an interval contractor (or contractor for short) associated to a set X is an operator C which associates to a
hyperrectangle In geometry, a hyperrectangle (also called a box, hyperbox, k-cell or orthotopeCoxeter, 1973), is the generalization of a rectangle (a plane figure) and the rectangular cuboid (a solid figure) to higher dimensions. A necessary and sufficient cond ...
/math> in \bold^n another box C( of \bold^n such that the two following properties are always satisfied: * C( \subset /math> (contractance property) * C( \cap X = \cap X (completeness property) A ''contractor associated to a constraint'' (such as an
equation In mathematics, an equation is a mathematical formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for ...
or an
inequality Inequality may refer to: * Inequality (mathematics), a relation between two quantities when they are different. * Economic inequality, difference in economic well-being between population groups ** Income inequality, an unequal distribution of i ...
) 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 Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm ...
algorithms classically used in interval analysis.


Properties of contractors

A contractor ''C'' is
monotonic In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...
if we have \subset \Rightarrow C( \subset C( . It is ''minimal'' if for all boxes 'x'' we have C( = xcap X], 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'', C(\) = \\cap X where denotes the degenerated box enclosing ''x'' as a single point. The contractor ''C'' is ''
idempotent Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
'' if for all boxes 'x'' we have C \circ C( = C( . The contractor ''C'' is '' convergent'' if for all sequences 'x''''k'') of boxes containing ''x'', we have k) \rightarrow x \implies C( k))\rightarrow \ \cap X.


Illustration

Figure 1 represents the set ''X'' painted grey and some boxes, some of them degenerated (i.e., they correspond to singletons). Figure 2 represents these boxes after
contraction Contraction may refer to: Linguistics * Contraction (grammar), a shortened word * Poetic contraction, omission of letters for poetic reasons * Elision, omission of sounds ** Syncope (phonology), omission of sounds in a word * Synalepha, merged ...
. 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.


Contractor algebra

Some operations can be performed on contractors to build more complex contractors. The
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
, the union, the
composition Composition or Compositions may refer to: Arts and literature *Composition (dance), practice and teaching of choreography * Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
and the repetition are defined as follows. : (C_1 \cap C_2)( = C_1( \cap C_2( : (C_1 \cup C_2) ( = \cup C_2( ">_1( \cup C_2( /math> : (C_1 \circ C_2) ( = C_1( C_2( ) : C^\infty( = C \circ C \circ C \circ \cdots \circ C(


Building contractors

There exist different ways to build contractors associated to equations and 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 Interval arithmetic (also known as interval mathematics; interval analysis or interval computation) is a mathematical technique used to mitigate rounding and measurement errors in mathematical computation by computing function bounds. Numeri ...
(this is the forward step). The resulting interval is 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 (x_1+x_2)\cdot x_3 \in ,2 We can evaluate the function ''f''(''x'') by introducing the two intermediate
variables Variable may refer to: Computer science * Variable (computer science), a symbolic name associated with a value and whose associated value may be changed Mathematics * Variable (mathematics), a symbol that represents a quantity in a mathemat ...
''a'' and ''b'', as follows : a = x_1+x_2 : b =a \cdot x_3 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 : x_3 = \frac : a = \frac : x_1 = a-x_2 : x_2 = a-x_1 The resulting forward/backward contractor C( _1 _2 _3 is obtained by evaluating the forward and the backward constraints using interval analysis. : = _1 _2/math> : = \cdot _3/math> : = \cap ,2/math> : _3= _3 \cap \ \frac : = \cap \frac : _1= _1 \cap \ \ _2/math> : _2= _2 \cap \ \ _1/math>


References

{{Reflist, 2 Arithmetic Computer arithmetic Optimization algorithms and methods Numerical analysis