next up previous
Next: Substitution-Iteration in GlobSol Up: Substitution-Iteration Previous: Substitution-Iteration

The Basic Idea; An Example

 

When the expressions defining the objective function, gradient, and constraints are evaluated, intermediate quantities are computed. Under certain circumstances, the relationships among these intermediate quantities can be used, other than in the straightforward way for evaluating the dependent variables, to obtain tighter bounds on the dependent variables or to obtain a conclusion that no optimum can exist within the given box.

For example, suppose
 equation430
is to be optimized over tex2html_wrap_inline1267. The global optimum of tex2html_wrap_inline56 over tex2html_wrap_inline64 is 0, and the unique optimizer is tex2html_wrap_inline1275. If tex2html_wrap_inline56 is programmed as

T(1) = X(1)**2
T(2) = X(2)**2
PHI(1) = T(1) - T(1)*T(2) + T(2)

then an early version of GlobSol, compiled with the NAG compiler version 2.1, produces the following list of intermediate operations.


displaymath1279

(Different compilers will produce different decompositions, or code lists.) Suppose we know a sharp upper bound tex2html_wrap_inline1281 on the global optimum, and suppose the sub-box tex2html_wrap_inline1283 is to be processed. An initial evaluation of the code list (i.e. a forward substitution) gives:


displaymath1285

Thus, since tex2html_wrap_inline1287 and tex2html_wrap_inline1289, the box cannot be rejected just from the computed values. However, we may set tex2html_wrap_inline1297, and solve for tex2html_wrap_inline1293 in (v):
displaymath1301
We may now solve for tex2html_wrap_inline1297 in (viii), obtaining
displaymath1299
Since tex2html_wrap_inline1301 (with tex2html_wrap_inline1303), tex2html_wrap_inline64 cannot contain both the global optimum and a critical point of tex2html_wrap_inline56. Thus, the box tex2html_wrap_inline1309 may be rejected.



R. Baker Kearfott
Wed May 27 11:22:02 CDT 1998