Interval propagation

In numerical mathematics, interval propagation or interval constraint propagation is the problem of contracting interval domains associated to variables of R without removing any value that is consistent with a set of constraints (i.e., equations or inequalities). It can be used to propagate uncertainties in the situation where errors are represented by intervals.^[1] Interval propagation considers an estimation problem as a constraint satisfaction problem.

Atomic contractors

A contractor associated to an equation involving the variables x₁,...,x_n is an operator which contracts the intervals [x₁],..., [x_n] (that are supposed to enclose the x_i's) without removing any value for the variables that is consistent with the equation.

A contractor is said to be atomic if it is not built as a composition of other contractors. The main theory that is used to build atomic contractors are based on interval analysis.

Example. Consider for instance the equation

${\displaystyle x_{1}+x_{2}=x_{3},}$

which involves the three variables x₁,x₂ and x₃.

The associated contractor is given by the following statements

${\displaystyle [x_{3}]:=[x_{3}]\cap ([x_{1}]+[x_{2}])}$

${\displaystyle [x_{1}]:=[x_{1}]\cap ([x_{3}]-[x_{2}])}$

${\displaystyle [x_{2}]:=[x_{2}]\cap ([x_{3}]-[x_{1}])}$

For instance, if

${\displaystyle x_{1}\in [-\infty ,5],}$

${\displaystyle x_{2}\in [-\infty ,4],}$

${\displaystyle x_{3}\in [6,\infty ]}$

the contractor performs the following calculus

${\displaystyle x_{3}=x_{1}+x_{2}\Rightarrow x_{3}\in [6,\infty ]\cap ([-\infty ,5]+[-\infty ,4])=[6,\infty ]\cap [-\infty ,9]=[6,9].}$

${\displaystyle x_{1}=x_{3}-x_{2}\Rightarrow x_{1}\in [-\infty ,5]\cap ([6,\infty ]-[-\infty ,4])=[-\infty ,5]\cap [2,\infty ]=[2,5].}$

${\displaystyle x_{2}=x_{3}-x_{1}\Rightarrow x_{2}\in [-\infty ,4]\cap ([6,\infty ]-[-\infty ,5])=[-\infty ,4]\cap [1,\infty ]=[1,4].}$

Figure 1: boxes before contraction

Figure 2: boxes after contraction

For other constraints, a specific algorithm for implementing the atomic contractor should be written. An illustration is the atomic contractor associated to the equation

${\displaystyle x_{2}=\sin(x_{1}),}$

is provided by Figures 1 and 2.

Decomposition

For more complex constraints, a decomposition into atomic constraints (i.e., constraints for which an atomic contractor exists) should be performed. Consider for instance the constraint

${\displaystyle x+\sin(xy)\leq 0,}$

could be decomposed into

${\displaystyle a=xy}$

${\displaystyle b=\sin(a)}$

${\displaystyle c=x+b.}$

The interval domains that should be associated to the new intermediate variables are

${\displaystyle a\in [-\infty ,\infty ],}$

${\displaystyle b\in [-1,1],}$

${\displaystyle c\in [-\infty ,0].}$

Propagation

The principle of the interval propagation is to call all available atomic contractors until no more contraction could be observed. ^[2] As a result of the Knaster-Tarski theorem, the procedure always converges to intervals which enclose all feasible values for the variables. A formalization of the interval propagation can be made thanks to the contractor algebra. Interval propagation converges quickly to the result and can deal with problems involving several hundred of variables. ^[3]

Example

Consider the electronic circuit of Figure 3.

Figure 3: File:Electronic circuit to illustrate the interval propagation

Assume that from different measurements, we know that

${\displaystyle E\in [23V,26V]}$

${\displaystyle I\in [4A,8A]}$

${\displaystyle U_{1}\in [10V,11V]}$

${\displaystyle U_{2}\in [14V,17V]}$

${\displaystyle P\in [124W,130W]}$

${\displaystyle R_{1}\in [0\Omega ,\infty [}$

${\displaystyle R_{2}\in [0\Omega ,\infty [.}$

From the circuit, we have the following equations

${\displaystyle P=EI}$

${\displaystyle U_{1}=R_{1}I}$

${\displaystyle U_{2}=R_{2}I}$

${\displaystyle E=U_{1}+U_{2}.}$

After performing the interval propagation, we get

${\displaystyle E\in [24V,26V]}$

${\displaystyle I\in [4.769A,5.417A]}$

${\displaystyle U_{1}\in [10V,11V]}$

${\displaystyle U_{2}\in [14V,16V]}$

${\displaystyle P\in [124W,130W]}$

${\displaystyle R_{1}\in [1.846\Omega ,2.307\Omega ]}$

${\displaystyle R_{2}\in [2.584\Omega ,3.355\Omega ].}$

References

1. Jaulin, L.; Braems, I.; Walter, E. (2002). Interval methods for nonlinear identification and robust control (PDF). In Proceedings of the 41st IEEE Conference on Decision and Control (CDC).
2. Cleary, J.L. (1987). Logical arithmetic. Future Computing Systems.
3. Jaulin, L. (2006). Localization of an underwater robot using interval constraints propagation (PDF). In Proceedings of CP 2006.