3.3.3 Optimality

 

The notion of optimality is not as simple for linear interval arithmetic as it was for constant interval arithmetic. Consider the following function g, with two distinct bounds, and :

We now define a measure of bound goodness. Consider the norm:    

where is a continuous positive function defined on [0,1]. The norm is always positive, since we consider only which are upper bounds of g. We consider the upper bound to be a better upper bound than if : a bound is good if is small.

A bound is optimal, for linear interval arithmetic, if no better linear interval upper bound exists:

The model returns optimal upper bounds if the upper bound is optimal for all :

As before, optimality can be defined without reference to the underlying function.

Also, arguing as before, we may show that an optimal model of g is an interval extension of g. This implies that for differentiable g, an optimal model produces bounds which touch g at two distinct points, allowing for infinitesimal separation between points. Infinitesimally separated points correspond to the upper bound matching both the value and the derivative at a point.

Jeff Tupper

March 1996