Reliable Computing, 0, 1–5 (0000)

\begin{matrix}c \\ ◯ \end{matrix} 0000 Kluwer Academic Publishers, Boston. Manufactured in The Netherlands.

An Example of Singularity in Global Optimization

R. BAKER KEARFOTT rbk@louisiana.edu Department of Mathematics, University of Louisiana at Lafayette, Lafayette, LA 70504

Abstract. Certain practical constrained global optimization problems have to date defied practical solution with interval branch and bound methods. The exact mechanism causing the difficulty has been difficult to pinpoint. Here, an example is given where the equality constraint set has higher-order singularities and degenerate manifolds of singularities on the feasible set. The reason that this causes problems is discussed, and ways of fixing it are suggested.

Keywords: constrained global optimization, singular nonlinear algebraic systems, GlobSol

1. The Setting

Equality-constrained global optimization problems are of the form

minimize ϕ(x)

subject to c_{i}(x) = 0, i = 1, …, m where ϕ : ℝ^{n} → ℝ and c_{i} : ℝ^{n} → ℝ.

(1)

In interval branch and bound algorithms to solve problem (1), it is crucial to obtain small boxes x̌ for which it can be verified that there is a feasible point x̌ ∈ x̌, i.e. where c(x̌) = (c_{1}(x̌), …, c_{n}(x̌)) = 0. Such a small box is needed for an interval evaluation ϕ(x̌), from which a rigorous upper bound \overline{f} on the global optimum value can be obtained. This upper bound is then used to eliminate subregions x of the search region in which the lower bound of ϕ(x) is greater than \overline{f}; See [4], [5, §5.1], etc.

2. The Example

Consider

Example: Find a_{1}, a_{2}, a_{3}, x_{1}, x_{2}, and x_{3} such that c_{i} = 0, i = 1, …, 6, or, equivalently, such that ϕ is minimum, where

c_{1} = 0.08413r + 0.2163q_{1} + 0.0792q_{2} − 0.1372q_{3},
c_{2} = −0.3266r − 0.57q_{1} − 0.0792q_{2} + 0.4907q_{3}
c_{3} = 0.2704r + 0.3536 (a_{1}(x_{1} − x_{3}) + a_{2}(x_{1}^{2} − x_{3}^{2}) + a_{3}(x_{1}^{3} − x_{3}^{3})
+ x_{1}^{4} − x_{3}^{4})
c_{4} = 0.02383p_{1} − 0.01592r − 0.08295q_{1} − 0.05158q_{2} + 0.0314q_{3}
c_{5} = −0.04768p_{2} − 0.06774r − 0.1509q_{1} + 0.1509q_{3}

c_{6} = 0.02383p_{3} − 0.1191r − 0.0314q_{1} + 0.05158q_{2} + 0.08295q_{3}, where
r = a_{1} + a_{2} + a_{3} + 1,
p_{i} = a_{1} + 2a_{2}x_{i} + 3a_{3}x_{i}^{2} + 4x_{i}^{3}, i = 1, 2, 3,
q_{i} = a_{1}x_{i} + a_{2}x_{i}^{2} + a_{3}x_{i}^{3} + x_{i}^{4}, i = 1, 2, 3, and
ϕ = ∑_{i=1}^{6} c_{i}.

This system has been posed both as an optimization problem (with objective function ϕ), and as a simple nonlinear systems problem. Neither Numerica [11] nor GlobSol [1, 2] could efficiently solve this problem, but it was not known why. Preliminary computations reported in [7] indicated that it probably was not due to overestimation in the individual interval constraint residuals c_{i}, although it could have been due to dependencies between the c_{i} that arise in the linear algebra for the interval Newton method. We report here that, at least when the problem is posed as a global optimization problem, the intrinsic mathematical structure of the constraints is a major factor.

3. The Tools and Results

Our goal was to determine the mechanism by which excessive subdivision occurred in GlobSol and to see if techniques can be developed to avoid this excessive subdivision. We posed the problem as an optimization problem (i.e. minimization of ϕ), and traced GlobSol’s steps. To determine a feasible point, GlobSol first applies a generalized-inverse based generalized point Newton method [8] to the set of constraints, to find an approximate feasible point x̃ If such a x̃ is found, then epsilon-inflation is used to construct a small box x, x̃ ∈ x in a subspace of ℝ^{n} within which an interval Newton method can prove there exists a true feasible point; see [5, §5.2.4] and [6].

Using default configuration and initial box

x = (a_{1}, a_{2}, a_{3}, x_{1}, x_{2}, x_{3})
= ([−2, 2], [−3, 3], [−3, 3], [−2, 2], [−2, 2], [−2, 2]),

the May 2, 2000 version of GlobSol did not complete after processing 20,000 boxes. However, we modified that version of GlobSol to always try to compute an approximate feasible point before bisection and to print the approximate feasible points to a separate file. We subsequently checked the residuals |c_{i}(x̌)| at each approximate feasible point x̌, and found that all of these were reasonably small (i.e. the approximate feasible point finder was reliable). We then plotted the approximate feasible points, noting an apparent one-dimensional nonlinear manifold of solutions; see Figure 1 for the plot of a_{1} versus x_{1}. This indicates an unusual type of dependence of the constraints; the constraints are not symbolically dependent, since a number

-1 -0.5 0 0.5 1 1.5-1  -0.5  0  0.5  1  1.5 x_{1}  a^{1}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}  ^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘} ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘} ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}  ^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘} ^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}^{∘}  ^{∘}

Figure 1. Approximate solution points

of approximate feasible points could be verified to be near true feasible points. (A run of one hour produced 216 unverified small boxes and 12 boxes with verified feasible points.)

However, there are higher-order singularities on the feasible set. Necessarily, the Jacobi matrix must have rank-defect at least 1 at each point on the solution manifold. A rank-defect 2 singularity occurs at the feasible point (0, −.5, −.5, 0, 0, 0).

The point x̌ = (0, −.5, −.5, 0, 0, 0) was examined with an interval multivariate Taylor decomposition. We interfaced GlobSol with the COSY system [10], using a Fortran 90 interface module Jens Hoefkens recently supplied to us. Although the c_{i} are of degree 4 only, it is advantageous to view them in Taylor form: We computed the Taylor models based at x̌ and with semiwidths 10^{−5}, for each of the components c_{i}, 1 ≤ i ≤ 6 of the constraint vector c(x). We then applied a preconditioner based on incomplete LU factorization of the midpoint of the interval Jacobi matrix of c to the Taylor models for the six components. (Note that this is a type of symbolic preconditioning, similar to what Hansen has recommended for certain computations.) We thus obtained six Taylor models. The Taylor models for the last two preconditioned constraints were as follows:

(Y c)_{5}(x) ≈ .069a_{1}x_{1} + .059a_{1}x_{2} − .11a_{1}x_{3} − .035x_{1}^{2} − .029x_{2}^{2} + .0054x_{3}^{2}
+.069(a_{2} + .5)x_{1}^{2} + .059(a_{2} + .5)x_{2}^{2} − .011(a_{2} + .5)x_{3}^{2}
−.035x_{1}^{3} − .030x_{2}^{3} + .0055x_{3}^{3}
+.069(a_{3} + .5)x_{1}^{3} + .058(a_{3} + .5)x_{2}^{3} − .011(a_{3} + .5)x_{3}^{3}
+.069x_{1}^{4} + .059x_{2}^{4} − .011x_{3}^{4}

(Y c)_{6}(x) ≈ −.12a_{1}x_{1} − .066a_{1}x_{2} + .053a_{1}x_{3} + .059x_{1}^{2} + .033x_{2}^{2} − .026x_{3}^{2}
−.12(a_{2} + .5)x_{1}^{2} − .066(a_{2} + .5)x_{2}^{2} + .053(a_{2} + .5)x_{3}^{2}
+.059x_{1}^{3} + .032x_{2}^{3} − .026x_{3}^{3}
−.12(a_{3} + .5)x_{1}^{3} − .066(a_{3} + .5)x_{2}^{3} − .053(a_{3} + .5)x_{3}^{3}
−.12x_{1}^{4} − .066x_{2}^{4} + .053x_{3}^{4}

where terms of magnitude 10^{−10} or less are omitted, where we have rounded the point coefficients to two significant digits, and where we have omitted the remainder bound which, here, consists of roundout error only. In contrast, the first five components of Y c (not shown) have nonzero order-one coefficients. This unambiguously reveals a rank-defect two singularity where c behaves as a two-dimensional quadratic form.

4. Conclusions

Our analysis shows that, for this problem, the difficulty lies not in intrinsic properties of interval arithmetic, but in the problem itself. If there is a manifold of solutions, there seems to be no way to efficiently verify that all of the solution set has been found, although it may be possible with specialized subdivision algorithms (and with parallel computation, perhaps) to complete the process more quickly than with a general algorithm. It seems that the best chances are for the modeler to reformulate the problem, or to symbolically parametrize the solution manifolds.

Originally, we thought degree computation as in [9] generalized as in [3] could help for the point x̌ = (0, −.5, −.5, 0, 0, 0). However, degree computation, although allowing verification in singular cases, must fail if the solution is not isolated and the solution manifold crosses through the boundary of the bounding box.

An advantage of interval computations is that we can suspect singularities and unusual solution manifolds like those observed above if efficiency is poor. The Newton method used in the approximate solver converged without difficulty. Without the branch and bound search, the modeler might never suspect such solution set properties!

References

1. G. F. Corliss. Globsol entry page, 1998. http://www.mscs.mu.edu/∼globsol/.

2. G. F. Corliss and R. B. Kearfott. Rigorous global search: Industrial applications. In T. Csendes, editor, Developments in Reliable Computing, pages 1–16, Dordrecht, Netherlands, 2000. Kluwer.

3. J. Dian. Existence Verification of Higher Degree Singular Zeros of Nonlinear Systems. PhD thesis, University of Louisiana at Lafayette, 2000.

4. E. R. Hansen. Global Optimization Using Interval Analysis. Marcel Dekker, Inc., New York, 1992.

5. R. B. Kearfott. Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht, Netherlands, 1996.

6. R. B. Kearfott. On proving existence of feasible points in equality constrained optimization problems. Math. Prog., 83(1):89–100, September 1998.

7. R. B. Kearfott and A. Arazyan. Taylor series models in deterministic global optimization. In G. F. Corliss, editor, Proceedings of Automatic Differentiation 2000: From Simulation to Optimization, New York, 2000. Springer-Verlag.

8. R. B. Kearfott and J. Dian. An iterative method for finding approximate feasible points, 1998. Preprint, Department of Mathematics, Univ. of Southwestern Louisiana, U.S.L. Box 4-1010, Lafayette, La

70504http://interval.louisiana.edu/GlobSol/Dian-approximate-optimizer.pdf.

9. R. B. Kearfott, J. Dian, and A. Neumaier. Existence verification for singular zeros of nonlinear systems. SIAM J. Numer. Anal., 38(2):360–379, 2000.

10. K. Makino and M. Berz. New applications of Taylor model methods. In G. F. Corliss, editor, Proceedings of Automatic Differentiation 2000: From Simulation to Optimization, New York, 2000. Springer-Verlag.

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