INTERVAL ANALYSIS: INTERMEDI-ATE TERMS

Introduction.

In global optimization algorithms, the computer must repeatedly evaluate an objective function, as well as, possibly, inequality and equality constraints. Such functions are given as algebraic expressions or as subroutines or sections of computer code. When such computer code is executed, operations are applied to the independent variables, producing intermediate terms. These intermediate terms are, in turn, combined to produce other intermediate terms, or, eventually, the objective function value. For example, consider the problem

minimize ϕ(x) = x_{1}^{2} − x_{1}^{2}x_{2}^{2} + x_{2}^{2}
over the box x = ([−1, 1], [−1, 1])^{T} .

(1)

To evaluate ϕ, the computer may start with the independent variable values v_{1} = x_{1} and v_{2} = x_{2} internally produce quantities v_{3}, v_{4}, v_{5}, and v_{6}, to finally produce the dependent variable value ϕ(x) = v_{7}. The following table indicates how this may be done.

v_{1} = x_{1},
v_{2} = x_{2},
(i) v_{3} = v_{1}^{2},
(ii) v_{4} = v_{2}^{2},
(iii) v_{5} = v_{4}v_{3},
(iv) v_{6} = v_{3} − v_{5},
(v) v_{7} = v_{6} + v_{4}.

(2)

A list such as in (2) may be represented as a table of addresses of variables and operations. For example, if the operation x_{p} ← x_{q}^{2} corresponds to operation code 5, x_{p} ← x_{q}x_{r} corresponds to operation code 4, x_{p} ← x_{q} + x_{r} corresponds to operation code 20, and x_{p} ← x_{q} − x_{r} corresponds to operation code 21, then the set of relations (2) is represented by the table

\begin{matrix}OP & p & q & r \\ 5 & 3 & 1 & - \\ 5 & 4 & 2 & - \\ 4 & 5 & 4 & 3 \\ 21 & 6 & 3 & 5 \\ 20 & 7 & 6 & 4 \end{matrix}  (3)

Such a sequence of operations is called a code list, but is sometimes called other things, such as a tape. Assuming the axioms of real arithmetic hold for evaluation, code lists for a given algebraic expression or portion of a computer program are not unique.

The concept of a code list is familiar to computer science students who have worked with compilers, since a compiler produces such lists while translating algebraic expressions into machine language. However, code lists and access to the intermediate expressions are of particular importance in interval global optimization, for the following reasons.

• Code lists provide a convenient internal representation for the objective and constraints, to be used for automatic differentiation, for both point and interval evaluation of objectives, gradients, and Hessian matrices.

• The values of the intermediate quantities can be used within the optimization algorithm in processes that reduce the size of the search region.

• Symbolic manipulation can reduce the overestimation, or interval dependency that would otherwise occur with interval evaluations. Details are given below. In Automatic Differentiation.

A code list can be used either as a pattern to specify the computations in the forward mode of automatic differentiation or as a symbolic representation of the system of equations to be solved in the backward mode. See [5] for an in-depth look at the forward mode of automatic differentiation, and see [3] for somewhat more recent research on the subject. See [4, pp. 37–39] for some examples and additional references. Also see the articles on automatic differentiation in this encyclopedia. In Constraint Satisfaction Techniques. Since each intermediate variable in the code list is connected to one or two others via an elementary, invertible operation, narrow bounds on one such intermediate variable can be used to obtain narrow bounds on others. For example, suppose that the code list (2) has been symbolically differentiated, to get the code list (5). Then, if the sub-box x = ([0.5, 1], [−1, −0.5])^{T} is to be considered for possible inclusion of optima, the derivative code list (5) can be evaluated by forward substitution to obtain the interval set of intermediate values (6). Furthermore, since (1) is an unconstrained problem, an optimum must occur where ∂ϕ/∂x_{1} = 0 and ∂ϕ/∂x_{2} = 0. In particular, any global optimizer x^{∗} must have

independent variables intermediate terms code list automatic differentiation Hessian matrices interval dependency forward mode→ automatic differentiation: forward mode

v_{10}(x^{∗}) = 0.  (4)

Using (4) in line (viii) of the derivative code list (5),

v_{9} = v_{8} − v_{10},

whence

ṽ_{9} ← [1, 2] − 0
v_{9} ← ṽ_{9} ∩ v_{9} = [1, 2].

Now, using (vii) of (5),

ṽ_{4} ← \begin{matrix}v & 9 \\ v & 8 \end{matrix} = \frac{[1, 2]}{[1, 2]} = [0.5, 2],
v_{4} ← ṽ_{4} ∩ v_{4} = [0.5, 1].

Now using (ii) of (5) gives

ṽ_{2} ← \sqrt{v_{4}} ∪ −\sqrt{v_{4}}
⊆ [0.70, 1] ∪ [−1, −0.70],
v_{2} ← ṽ_{2} ∩ v_{2} = [−1, −0.70].

The last computation represents a narrowing of the range of one of the independent variables.

v_{1} = x_{1},
v_{2} = x_{2},
(i)  v_{3} = v_{1}^{2},
(ii)  v_{4} = v_{2}^{2},
(iii)  v_{5} = v_{4}v_{3},
(iv)  v_{6} = v_{3} − v_{5},
(v)  v_{7} = v_{6} + v_{4},
(vi)  v_{8} = 2v_{1},
(vii) v_{9} = v_{8}v_{4},
(viii) v_{10} = v_{8} − v_{9},
(ix) v_{11} = 2v_{2},
(x) v_{12} = v_{3}v_{11},
(xi) v_{13} = −v_{12},
(xii) v_{14} = v_{13} + v_{11},
ϕ = v_{7},
\frac{∂ϕ}{∂x_{1}} = v_{10},
\frac{∂ϕ}{∂x_{2}} = v_{14}.

(5)

\begin{aligned}v_{1} & = & [.5, 1], \\ v_{2} & = & [−1, −.5], \\ v_{3} & = & [.25, 1], \\ v_{4} & = & [.25, 1], \\ v_{5} & = & [.0625, 1], \\ v_{6} & = & [−.75, .9375], \\ v_{7} & = & [−.5, 1.9375], \\ v_{8} & = & [1, 2], \\ v_{9} & = & [.25, 2], \\ v_{10} & = & [−1, 1.75], \\ v_{11} & = & [−2, −1], \\ v_{12} & = & [−2, −.25], \\ v_{13} & = & [.25, 2], \\ v_{14} & = & [−1.75, 1], \\ ϕ & ∈ & [−.5, 1.9375], \\ \frac{∂ϕ}{∂x_{1}} & ∈ & [−1, 1.75], \\ \frac{∂ϕ}{∂x_{2}} & ∈ & [−1.75, 1]. \end{aligned}  (6)

(A similar computation could also have been carried out to obtain narrower bounds on v_{1}.) If in addition an upper bound \overline{ϕ} = 0 for the

global optimum of ϕ is known, then

v_{7} ∈ [−∞, 0] ∩ [−0.5, 1.9375] = [−0.5, 0].

backward mode→ automatic differentiation:backward mode forward substitution

This can now be used in (v) of (5), along with new intermediate variable bounds, wherever possible, to obtain

ṽ_{4} ← v_{7} − v_{6}
= [−0.5, 0] − [−0.75, 0.9375]
= [−1.4375, 0.75],
v_{4} ← v_{4} ∩ ṽ_{4} = [0.5, 0.75].

Now using (vii) of (5),

ṽ_{9} ← [1, 2][0.5, 0.75] = [0.5, 1.5],
v_{9} ← ṽ_{9} ∩ v_{9} = [1, 1.5],

then using (viii) and v_{10} = 0 gives v_{8} = [1, 1.5]. Finally, using (vi) of (5) gives

v_{1} ← [0.5, 0.75] ∩ [0.5, 1] = [0.5, 0.75]. (7)

Now, evaluating ϕ in (1) (or redoing the forward substitution represented in (6)) at (x_{1}, x_{2}) = ([0.5, 0.75], [−1, −0.70]) gives

ϕ ∈ [.5, .75]^{2} − [.5, .75]^{2}[−1, −.7]^{2}
+[−1, −.7]^{2}
= [.25, .5625] − [.25, .5625][.49, 1] + [.49, 1]
= [.25, .5625] + [−.5625, −.1225] + [.49, 1]
= [.1775, 1.44],

contradicting the known upper bound \overline{ϕ} = 0. This proves that there can be no global optimizer of (1) within ([0.5, 1], [−1, −0.5])^{T}. (Note that, in fact, there are no global optimizers in ([−1, 1], [−1, 1])^{T} if the problem is considered to be unconstrained.)

The above procedure is easily automated, as is done in, say, GlobSol [2, 4], UniCalc [1], or other interval constraint propagation software.

This example illustrates a more general technique, associated with constraint propagation and logic programming. See [6] for an introduction to this view of the subject, and see [7] for alternate techniques of interval constraint satisfaction. In Symbolic Preprocessing.

To understand how symbolic analysis based on the code list may help, consider the following example.

Find all solutions to f(x) = 0, f = (f_{1}, f_{2})^{T}, within the box x = ([−2, 0], [−1, 1])^{T}, where

\begin{aligned}f_{1}(x_{1}, x_{2}) & = & x_{1}^{3} + x_{1}^{2}x_{2} + x_{2}^{2} + 1 \\ f_{2}(x_{1}, x_{2}) & = & x_{1}^{3} − 3x_{1}^{2}x_{2} + x_{2}^{2} + 1. \end{aligned}

(8)

A possible code list is

v_{1} = x_{1},
v_{2} = x_{2},
(i)  v_{3} = v_{1}^{2},
(ii)  v_{4} = v_{2}^{2},
(iii)  v_{5} = v_{3}v_{2},
(iv)  v_{6} = v_{1}^{3},
(v)  v_{7} = v_{6} + v_{4},
(vi)  v_{8} = v_{7} + 1,
(vii) v_{8} + v_{5} = 0,
(viii) v_{8} − 3v_{5} = 0.

(9)

There is much interval dependency in this system, both in the individual equations (since each variable occurs in various terms), and between the equations (since the equations share common terms). However, examination of the code list (9) reveals that a change of variables can make the system more amenable to interval computation. Seeing that (vii) and (viii) are linear in v_{5} and v_{8} = v_{4} + v_{6} + 1, define

\begin{aligned}y_{1} & = & v_{5} = x_{1}^{2}x_{2}, \\ y_{2} & = & v_{4} + v_{6} = x_{1}^{3} + x_{2}^{2}. \end{aligned}  (10)

Then the system becomes

\begin{aligned}y_{2} + y_{1} + 1 & = & 0 \\ y_{2} − 3y_{1} + 1 & = & 0. \end{aligned}  (11)

Thus, the linear system (11) may be solved easily for y_{1} and y_{2}. The interval bounds may then be plugged into (10) to obtain x_{1} and x_{2}. There is no overestimation in any of the expressions for function components or partial derivatives in either (11) or (10).

Additional research should reveal how to automate this change of variables process.

constraint propagation logic programming

file: kearfo06  date: November 10, 1998  4

References

[1] Babichev, A. B., Kadyrova, O. B., Kashevarova, T. P., Leshchenko, A. S., and Semenov, A. L.: ‘UniCalc, a Novel Approach to Solving Systems of Algebraic Equations’, Interval Computations 1993, no. 2 (1993), 29–47.

[2] Corliss, G. F., and Kearfott, R. B.: ‘Rigorous Global Search: Industrial Applications’, in T. Csendes (ed.): (Special issues of the journal “Reliable Computing”), Kluwer, 1998.

[3] Griewank, A., and Corliss, G. F. (eds.): Automatic Differentiation of Algorithms: Theory, Implementation, and Application (Philadelphia, 1991), SIAM.

[4] Kearfott, R. B.: Rigorous Global Search: Continuous Problems, Kluwer, Dordrecht, Netherlands, 1996.

[5] Rall, L. B.: Automatic Differentiation: Techniques and Applications, Lecture Notes in Computer Science no. 120. Springer, Berlin, New York, etc., 1981.

[6] Van Hentenryck, P.: Constraint Satisfaction in Logic Programming, MIT Press, Cambridge, MA, 1989.

[7] Van Hentenryck, P., Michel, L., and Deville, Y.: Numerica: A Modeling Language for Global Optimization, MIT Press, Cambridge, MA, 1997.

R. Baker Kearfott

Department of Mathematics University of Southwestern Louisiana

U.S.L. Box 4-1010, Lafayette, LA 70504-1010 USA E-mail address: rbk@usl.edu

AMS1991SubjectClassification: 65G10, 65H20. Key words and phrases: expression parsing, constraint satisfaction techniques, interval dependencies, verification, interval computations, global optimization.