Interval Analysis - Computer Graphics and Geometric Modeling - page 737

Figure 18.4. Boundary intersection sharing.

18.6 Constrained Minimizations

[Snyd92] also describes a constrained minimization algorithm. Here we are given
functions

n

fg ,: RR Æ

and we seek the minimum of f on the set defined by the equation g( x ) = 0. We again
choose inclusion functions F and G for f and g, respectively, and a solution accept-
ance set constraint H. Algorithm 18.6.1 describes the constrained minimization algo-
rithm. The idea behind the algorithm is to progressively refine a least upper bound u
of the function f. As we look at different intervals B, they affect u in the following
way:

(1) If we know a feasible point p in B , then we can use f( p ) as a new upper bound
for a global minimum for f. In particular, if B is a feasible region, then any
point in B will do.
(2) If we only know that B has a feasible point but do not actually know one, then
ub(F( B )) will serve as the new upper bound for a global minimum for f.
(3) If B is indeterminate so that we are unable to determine whether it contains
a feasible point, then u cannot be updated.

Algorithm 18.6.1 has some of the same problems that Algorithm 18.4.1 has, but
the following can be proved

18.6.1 Theorem. Let B i (k) be the ith interval on the priority queue Q in Algorithm
18.6.1 after the kth iteration of the while loop in the algorithm and let l k = lb(F(B 1 (k))).
Assume that the set of feasible points for G is nonempty and let m be the minimum
of f on that set. If the inclusion functions F and G are isotone, then the numbers l k
converge to m as k goes to infinity.

Proof. See [Snyd92].