Treating Non-Smooth Functions as Smooth Functions in Global Optimization

and Nonlinear Systems Solvers

R. Baker Kearfott

0 Introduction

Techniques of interval extensions and interval Newton methods have been developed for verified solution of nonlinear systems of equations and for global optimization. In most of the literature to date, such interval extensions and interval Newton methods are applicable when the functions are given by smooth expressions, without conditional branches. In fact, however, many practical problems, in particular those containing expressions such as |E(X)| and max{E(X), F (X)}, E, F : ℝ^{n} → ℝ, or expressions defined by IF-THEN-ELSE branches, result in functions whose derivatives have jump discontinuities. However, in [4], continuous, order-1 interval extensions were proposed for such continuous but non-smooth functions.

Such interval extensions of non-smooth functions can be used in the same contexts as other interval extensions. However, the width of a non-smooth derivative extension F′(X) or slope extension of a function F : ℝ^{n} → ℝ^{n} over an interval vector X does not, in general, tend to zero as the width vector w(X) tends to zero. Because of this, interval Newton iterations are only convergent in certain cases. However, ϵ-inflation algorithms can always be devised to prove existence or uniqueness for w(X) sufficiently small, provided merely that F′(X) is extended appropriately.

Special algorithms can be developed to handle non-smooth problems such as l_{1} optimization and l_{∞} optimization. However, simplicity is a major advantage of treating such non-smooth problems with the same techniques as smooth problems. This simpler, unified treatment is possible within the context described in this paper.

First, required properties of interval extensions for non-smooth functions are discussed. Then, selected formulas from [4] are presented. The formulas for slopes presented here represent improvements (sharper bounds) over those in [4]. A simple, illustrative example is then given. Fourth, a convergence and existence / uniqueness verification theory for interval Newton methods using non-smooth extensions is developed. Finally, formulas and examples are given for which interval Newton methods can find critical points, even if the gradient itself is discontinuous.

1 Extensions of Non-Smooth Functions

1.1 Required Properties

• An interval extension F (X) of F must contain the range, i.e.

{F (X) | X ∈ X} ⊆ F (X).

• Interval extensions F′(X) of the Jacobi matrix must be Lipschitz sets in the

sense that

F (X_{2}) − F (X_{1}) = A(X_{2}) − A(X_{1})

for some A ∈ F′(X), for every X_{1}, X_{2} ∈ X [6].

• Slope extensions S(F, X, X̌) must be slope sets in the sense that

F (X) − F (X̌) = A(X − X̌)

for some A ∈ S(F, X, X̌), for every X ∈ X and X̌ ∈ X̌ [6].

Such interval extensions should be as sharp as possible (i.e. should overestimate actual ranges as little as possible), subject to the above conditions, and subject to the condition that they can be computed automatically. The formulas in the next section give such extensions.

1.2 Some Example Formulas

Selected formulas satisfying the above conditions appear here. More complete listings of formulas appear in [4], and will appear with additional explanation in [5].

1.2.1 IF-THEN-ELSE

Branches can be handled in operator overloading and automatic differentiation with the function

χ(x_{s}, x_{q}, x_{r}) = \{ \begin{matrix}x_{q} & if x_{s} < 0, \\ x_{r} & otherwise. \end{matrix}

For example, if

f(x) = \{ \begin{matrix}x^{2} & if x < 1 \\ 2x − 1 & if x ≥ 1, \end{matrix}  (1)

then an internal representation for f may be generated within our INTLIB 90 system [3], with the following program.

PROGRAM CHI_EXAMPLE
  USE OVERLOAD
      TYPE(CDLVAR), DIMENSION(1):: X
      TYPE(CDLLHS), DIMENSION(1):: F
      OUTPUT_FILE_NAME='CHI_EXAMPLE.CDL'
      CALL INITIALIZE_CODELIST(X)
  F(1) = CHI(X(1)-1,X(1)**2,2*X(1)-1)
      CALL FINISH_CODELIST
END PROGRAM CHI_EXAMPLE

Once the internal representation is generated, the automatic differentiation process introduced in [3] and explained in [5] can make use of the following formulas.

• Interval extension:

χ(x_{s}, x_{q}, x_{r}) = \{ \begin{matrix}x_{q} & if x_{s} < 0; \\ x_{r} & if x_{s} > 0; \\ x_{q} \underline{∪}x_{r} & otherwise, \end{matrix}  (2)

where x\underline{∪}y is the interval hull of the intervals x and y.

• Derivative extension when χ(0^{−}, x_{q}, x_{r}) = χ(0^{+}, x_{q}, x_{r}), i.e. when f(X) = χ(E(X), F (X), G(X)) is continuous:

\frac{∂χ(x_{s},x_{q},x_{r})}{∂x_{q}} = \{ \begin{matrix}1 & if x_{s} < 0; \\ 0 & if x_{s} > 0; \\ [0, 1] & otherwise. \end{matrix}

\frac{∂χ(x_{s},x_{q},x_{r})}{∂x_{r}} = \{ \begin{matrix}0 & if x_{s} < 0; \\ 1 & if x_{s} > 0; \\ [0, 1] & otherwise. \end{matrix}
\frac{∂χ(x_{s},x_{q},x_{r})}{∂x_{s}} = 0

(3)

Within the automatic differentiation process, these formulas lead to enclosures of the range and to Lipschitz sets.

1.2.2 Absolute Value x_{p} = |x_{q}|

Although |x| = χ(x, −x, x), χ(x, −x, x) overestimates the range of |∘| over the interval x. For example, the range of |∘| over [−1, 2] is [0, 2], whereas χ([−1, 2], [−2, 1], [−1, 2]) = [−2, 2]. The following formulas are sharper.

• Interval extension:

|x| = \{ \begin{matrix}[0, max\{|\underline{x}|, |\overline{x}|\}] & if 0 ∈ x; \\ [min\{|\underline{x}|, |\overline{x}|\}, max\{|\underline{x}|, |\overline{x}|\}] & otherwise. \end{matrix}  (4)

• Derivative enclosure:

\frac{d|x_{q}|}{dx_{q}} = \{ \begin{matrix}−1 & if x_{q} < 0; \\ 1 & if x_{q} > 0; \\ [−1, 1] & otherwise. \end{matrix}  (5)

• Slope enclosure:

S(|x_{q}|), X, X̌) = \{ \begin{matrix}−S(x_{q}, X, X̌) & if x_{q} \underline{∪}x̌_{q} < 0; \\ S(x_{q}, X, X̌) & if x_{q} \underline{∪}x̌_{q} > 0; \\ S^{(d)}(|x_{q}|, x_{q}, x̌_{q})S(x_{q}, X, X̌) & otherwise, \end{matrix}  (6)

where

S^{(d)}(|x|, x, x̌) = h(\underline{x})\underline{∪}h(\overline{x}) with h(x) = \{ \begin{matrix}\frac{|x|−|x̌|}{x−x̌} & for x ∉ x̌; \\ [−1, 1] & otherwise. \end{matrix}  (7)

Formula (7) is derived from formulas explained by Rump in [8, 9]. In particular, it is valid to compute slopes by taking differences at end points, whenever the function, such as | · |, is convex.

1.2.3 x_{p} = max{x_{q}, x_{r}}

• Interval extension:

max\{x_{q}, x_{r}\} = [max\{\underline{x}_{q}, \underline{x}_{r}\}, max\{\overline{x}_{q}, \overline{x}_{r}\}]  (8)

• Derivative enclosure:

\frac{∂ max\{x_{q},x_{r}\}}{∂x_{q}} = \{ \begin{matrix}1 & if x_{q} > x_{r}; \\ 0 & if x_{q} < x_{r}; \\ [0, 1] & otherwise. \end{matrix}

\frac{∂ max\{x_{q},x_{r}\}}{∂x_{r}} = \{ \begin{matrix}0 & if x_{q} > x_{r}; \\ 1 & if x_{q} < x_{r}; \\ [0, 1] & otherwise. \end{matrix}

(9)

For additional formulas, see [4, 5].

2 Example – Univariate Interval Newton Method

Suppose roots of the function

f(x) = |x^{2} − x| − 2x + 2 = 0

are sought. The function f has a root and a cusp at 1: f(1) = 0, but

lim_{x→1^{−}} f′(x) = −3, lim_{x→1^{+}} f′(x) = −1.

For illustration purposes, a slope enclosure when 1 ∈ x may be given by S(f, x, x) = [−1, 1](x + x − 1) − 2. (This enclosure is cruder, but simpler, than that given above by S^{(d)}.) Apply the interval Newton method

x̃ ← x̌^{(k)} − f(x̌^{(k)})/S(f, x^{(k)}, x̌^{(k)}), x^{(k+1)} ← x^{(k)} ∩ x̃,

with x̌^{(k)} equal to the midpoint of x^{(k)}, and x^{(0)} = [0.7, 1.1]. The initial slope enclosure is S(f, [0.7, 1.1], 0.9) = [−3, −1], x̃ = .9 − .29/[−3, −1] = [.99\overline{6}, 1.19], and x^{(1)} = [0.99\overline{6}, 1.1]. Continuing iteration leads to the table:

k  x^{(k)}  w(x^{(k)}) \begin{matrix}w & (x^{(k)}) \\ w & (x^{(k−1)}) \end{matrix}
0 [0.699999, 1.1000] 4.0E-1  —
1 [0.996666, 1.1000] 1.0E-1  0.25
2 [0.996666, 1.0337] 3.7E-2  0.37
3 [0.999461, 1.0102] 1.1E-2  0.28
4 [0.999949, 1.0032] 3.3E-3  0.30
5 [0.999994, 1.0010] 1.1E-3  0.33
6 [0.999999, 1.0003] 3.6E-4  0.33

(Here, w(x) represents the width of an interval x.) On iteration 3, existence of a root within x^{(3)} is proven, since x^{(3)} is in the interior of x^{(2)}. The observed convergence is linear, with a convergence factor of about 0.33. (Somewhat faster convergence would be observed if S^{(d)} were used instead.) In any case, convergence of the interval Newton method, requiring derivative information, occurs, even though the derivative is discontinuous. Also, programming of the optimization problem requires, besides variable declarations and the program template, only the statement:

F(1) = ABS(X(1) ∗ ∗2 − X(1)) − 2 ∗ X(1) + 2

Preliminary experiments in n-space are reported in [4].

3 Convergence Theory

The consequences of using the above formulas in nonlinear equations and global optimization algorithms are briefly discussed here.

3.1 Objective Function Approximation

Interval extensions involving χ, |∘|, and max, computed with formulas as in §1.2 and in [4, 5], are first-order extensions in the sense of [7, p. 38]. Thus, these interval extensions may be used to prove that no roots exist within a box X. Similarly, since the formulas for the derivative extensions, if they lead to finite intervals, lead to Lipschitz matrices or slope matrices, an image of X under any interval Newton method that employs these extensions must contain all roots within X; hence, the interval Newton method can also be used to prove that no roots exist within X.

However, the mean value extension based on the above does not, in general, lead to a second-order interval extension. For an example, see [5].

3.2 Verification and Interval Convergence

Convergence of interval Newton methods occurs, and existence or uniqueness verification is possible in many cases with the non-smooth extensions described above. Conditions under which convergence occurs or under which verification is possible are examined in this section.

3.2.1 Interval Newton Methods – General Convergence

We consider the general multivariate interval Newton method:

X̃ = N(F; X, X̌) = X̌ + V ,

where X, V , and X̃ are boxes (i.e. interval vectors) in ℝ^{n}, where

Σ(A, −F (X̌)) ⊂ V ,

where A is either a Lipschitz matrix or a slope enclosure S(F, X, X̌) for F over X and centered at X̌, and where Σ(A, −F (X̌)) is the exact solution set of the interval linear system AX = −F (X̌).

Convergence analysis of

X ← N(F; X, X̌),

as well as analysis of existence/uniqueness verification with

N(F; X, X̌) ⊂ int(X),

may proceed by bounding the width norm:

∥w(N(F; X, X̌))∥ .

Define

Σ_{0} = Σ(A, −F (X̌))  and Σ_{0} = Σ(A, −F (X̌)),  (10)

where Σ is the smallest interval vector containing Σ. First note that the width norms obey

∥w(Σ_{0})∥ = ∥w( Σ_{0})∥,  (11)

from the definition of Σ_{0} and since ∥ · ∥ = ∥ · ∥_{∞}. Also write

V = Σ_{0} + E, so w(N(F; X, X̌)) = w(V ) = w( Σ_{0}) + w(E).  (12)

The following assumption is non-restrictive.

Assumption 1 There exists a K, depending only on the particular interval Newton method, such that

∥w(E)∥ = ∥w(V ) − w(Σ)∥ ≤ K∥w(Σ)∥.  (13)

In fact, for most methods of bounding Σ, Assumption 1 follows from (12) and considerations as in [6, §4.2, p. 124 and §4.3.5, p. 138]. Thus, ∥w(N(F; X, X̌))∥ can be bounded by bounding ∥w(Σ_{0})∥. To bound ∥w(Σ_{0})∥, a sensitivity bound for real linear systems will be used, namely

Theorem 1 (A modification of Theorem 2.7.2 in [2]) Assume

AX = B,  A ∈ ℝ^{n×n}, B ∈ ℝ^{n}, and
(A + ΔA)(X + ΔX) = B,  ΔA ∈ ℝ^{n×n},

assume ∥ΔA∥ ≤ δ∥A∥, and assume δκ(A) = r < 1, where κ(A) is the condition number ∥A∥ · ∥A^{−1}∥. Then

∥ΔX∥ ≤ r \frac{1}{1 − r} ∥X∥
≤ r \frac{1}{1 − r} ∥A^{−1}∥ · ∥B∥.

To use Theorem 1, identify:

B = −F (X̌) and A = Ǎ = m(A), so ΔA = \frac{w(A)}{2},

(where m(A) is the midpoint matrix of an interval matrix A) so that

δ = \frac{1}{2} \frac{∥w(A)∥}{∥Ǎ∥} and r = \frac{1}{2}∥w(A)∥ · ∥Ǎ^{−1}∥.  (14)

Assume X_{1} ∈ Σ_{0} and X_{2} ∈ Σ_{0}. Then (14) and Theorem 1 give

∥X_{1} − X_{2}∥ ≤ ∥w(A)∥ · ∥ − F (X̌)∥ \{\frac{∥Ǎ^{−1}∥}{2} · \frac{1}{1 − r} \} .  (15)

Combining (15) and (13) gives Lemma 2 Make Assumption 1. Then

∥w(N(F; X, X̌))∥ ≤ C∥w(A)∥ · ∥F (X̌)∥,

where

C = K \{\frac{1}{2} · \frac{∥Ǎ^{−1}∥}{1 − \frac{1}{2}∥w(A)∥ · ∥Ǎ^{−1}∥}\} .  (16)

The next assumption is necessary for proof that verification is possible.

Assumption 2 Assume there exists an X^{∗} ∈ X with F (X^{∗}) = 0. Also assume that X̌ = m(X).

Now, since A is either a Lipschitz matrix or a slope enclosure centered at X̌,

F (X^{∗}) = 0 = F (X̌) + A(X^{∗} − X̌) for some A ∈ A.

Thus,

∥F (X̌)∥ ≤ ∥A∥\frac{∥w(X)∥}{2}.  (17)

Combining (17) and Lemma 2 thus gives

Theorem 3 Make assumptions 1 and 2, and let C be as in (16) of Lemma 2. Then

∥w(N(F; X, X̌))∥ ≤ C∥w(A)∥ · ∥A∥\frac{∥w(X)∥}{2}.

Corollary 4 Make assumptions 1 and 2, and let C be as in (16) of Lemma 2. Then

∥w(N(F; X, X̌))∥ ≤ ∥w(X)∥

provided

C∥w(A)∥ · ∥A∥ < 2 (for convergence).  (18)

Furthermore, if we assume X̌ ∈ N(F; X, X̌), such as when F (X̌) ≈ 0 and ϵ-inflation is used, then N(F; X, X̌) ⊂ X, provided

C∥w(A)∥ · ∥A∥\begin{matrix}∥ & w(X) & ∥ \\ min & 1≤i≤n & w(x_{i}) \end{matrix} < 1 (for inclusion).  (19)

For smooth problems and Lipschitz or slope matrices formed with the usual computations,

∥w(A)∥ ≤ K_{F′}∥w(X)∥,  (20)

so Condition (18) (and the more restrictive Condition 19 for the inclusion N(F; X, X̌) ⊂ X) hold for sufficiently small X centered about an approximate solution X̌ ≈ X^{∗}. Thus, neglecting roundout error, it should always be possible to verify existence or uniqueness with ϵ-inflation. In fact, the following is a direct consequence of Theorem 3.

Theorem 5 Make assumptions 1 and 2, and let C be as in Lemma 2. Also assume ∥w(A)∥ ≤ K_{F′}∥w(X)∥. Then

∥w(N(F; X, X̌))∥ ≤ C̃∥w(X)∥^{2},

where C̃ = CK_{F′}∥A∥/2.

3.2.2 Convergence for Non-Smooth Problems

For non-smooth problems, w(A) ↛ 0 as w(X) → 0 (i.e. Condition (20) does not hold), Condition 18 is not in general satisfied, and the interval Newton method does not converge. However, when the non-smoothness does not occur in dominant terms, Condition 18 is sometimes still satisfied for small w(X), and the interval Newton method converges linearly:

Theorem 6 Make assumptions 1 and 2, and let C be as in Lemma 2. Also assume that (for small enough w(X))

∥w(A)∥ ≤ \frac{2}{CM′_{F}} .

Then the width of X under iteration of

X ← X ∩ N(F; X, X̌)

tends to zero linearly, with convergence factor c = C∥w(A)∥ · ∥A∥/2. That is,

∥w(N(F; X, X̌))∥ ≤ c∥w(X)∥.

In some cases, Theorem 6 does not give reasonably sharp bounds, since the convergence factor c incorporates a worst-case bound ∥X^{∗} −X̌∥ ≤ w(X)/2. Actually, in ϵ-inflation algorithms, X can be constructed so

∥X^{∗} − X̌∥ ≤ ν∥w(X)∥^{2}  (21)

For example, as explained in [5], X^{∗} can be computed with an approximate solver with a stopping tolerance that is proportional to the square of the width of the tolerance of the box constructed around it. In such cases, (17) can be replaced by

∥F (X̌)∥ ≤ ∥A∥ν∥w(X)∥^{2},  (22)

and Theorem 6 may be replaced by

Theorem 7 Make assumptions 1 and 2, and let C be as in Lemma 2. Also assume (21) for some ν > 0. Then, for small enough initial w(X), the width of X under iteration of

X ← X ∩ N(F; X, X̌)

tends to zero quadratically. In particular,

∥w(N(F; X, X̌))∥ ≤ C∥w(A)∥ · ∥A∥ν∥w(X)∥^{2},

where C is as in (16).

Theorem 7 follows directly from Lemma 2.

Remark 1 Theorem 7 implies that, even for non-smooth functions, existence and uniqueness can always be verified with ϵ-inflation, provided a sufficiently accurate approximate solution can be obtained.

Now we will use Theorem 6 to analyze the convergence for the example of §2. The limiting value of the slope bound set as x → [1, 1], for x̌ ⊆ x, is A = [−3, −1], and the limiting value of its center is Ǎ = −2. From this, we compute limiting values for C as defined in (16) and Assumption 1: Assumption 1 implies that, for an ϵ > 0 of our choosing and w( Σ_{0}) sufficiently small (i.e. w(X) sufficiently small), K can be taken to be (1 + ϵ). Furthermore, w(A) ≈ −1 − (−3) = 2, and ∥Ǎ^{−1}∥ ≈ |1/(−2)| = \frac{1}{2}, so

C ≈ (1 + ϵ) · \frac{1}{2} · \frac{\frac{1}{2}}{1 − \frac{1}{2}(2)\frac{1}{2}} ≈ \frac{1}{2}.

Also, ∥A∥ ≈ max{| − 3|, | − 1|} = 3, and

c ≈ \frac{1}{2} · (2) · \frac{3}{2} = \frac{3}{2}

in Theorem 6. Thus, Theorem 6 is not sharp enough in this case to predict inclusion. Also, we observe that |x̌ − x^{∗}| is tending to zero at about the same rate as w(x), so Theorem 7 would not give an appropriate conclusion either. However, after iteration no. 2, we observe |f(x^{(2)})| ≤ 0.015 and w(x^{(2)}) ≈ 0.04. Plugging these values directly into Lemma 2 gives

w(x^{(3)}) ≤ \frac{1}{2} · 2 · 0.015 = 0.015 < 0.04/2 = .02,

thus proving that verification must occur on this step. (In fact, the new width w(x^{(3)}) ≈ 0.01. The left endpoints of x^{(k)} are converging faster than the right endpoints.)

4 Slopes for Discontinuous Functions

In computations such as l_{1} or l_{∞} optimization, the objective function ϕ : ℝ^{n} → ℝ typically is continuous but non-smooth, and consists of compositions of smooth operations and | · |, max, or, more generally, χ. For example, if

ϕ(x) = max{2 − x^{2}, x^{2}},  (23)

x_{s}(x)

x_{r}(x_{s}) − x_{q}(x_{s}) x_{s}(x̌)

slope range in x_{s} coordinates

Figure 1: Computation of slope bounds of a discontinuous function

then ϕ has a minimum at x = 1. This minimum is at a cusp of ϕ, where the gradient

∇ϕ(x) = χ(x^{2} − (2 − x^{2}), −2x, 2x)  (24)

has a jump discontinuity. Thus, the interval extension of the second derivative of ϕ (corresponding to the Hessian matrix) is ℝ, and an interval Newton method would not be a useful computation. On the other hand, the actual gradient (24), rather than, say, a slope that would not have the discontinuity, is necessary to detect the critical point. Fortunately, interval slopes^{1} of functions such as (24) contain meaningful information.

Definition of the interval slopes of discontinuous functions is illustrated in Figure 1. There, the slope S(χ(x_{s}(x), x_{q}(x), x_{r}(x)), x, x̌) is shown in terms of x_{s} coordinates, that is, assuming x_{s} = x. It is seen that, if 0 ∉ x̌, the slope bound is finite. Furthermore, the slope bounds will include the jump (a finite change over an infinitely small interval), and interval Newton methods will converge on critical points, be they zeros or breaks in the gradient.

Based on Figure 1, the following formula can be derived.

S(χ(x_{s}(x), x_{q}(x), x_{r}(x)), x, x̌) =

S(x_{r}(x), x, x̌)\underline{∪} \{\frac{1}{x_{s}(x^{}ˇ )}(x_{r}(x) − x_{q}(x))S(x_{s}(x), x, x̌)\} if x_{s}(x̌) > 0
S(x_{q}(x), x, x̌)\underline{∪} \{\frac{−1}{x_{s}(x^{}ˇ )}(x_{r}(x) − x_{q}(x))S(x_{s}(x), x, x̌)\} if x_{s}(x̌) < 0

\{[\frac{1}{\overline{x}_{s}(x^{}ˇ )}, ∞) ∪ [\frac{−1}{\underline{x}_{s}(x^{}ˇ )}, ∞)\} (x_{r}(x) − x_{q}(x))S(x_{s}, x, x̌)

\underline{∪}S(x_{q}(x), x, x̌)\underline{∪}S(x_{r}(x), x, x̌)  if 0 ∈ x_{s}(x̌).

(25)

The first branch of Formula (25), for x_{s}(x̌) > 0, corresponds to Figure 1: The factor \frac{1}{x_{s}(x^{}ˇ )} represents the distance of x_{s}(x̌) to the break point, while (x_{r}(x) − x_{q}(x)) represents the jump at the break point, so the product \frac{1}{x_{s}(x^{}ˇ )}(x_{r}(x) − x_{q}(x)) represents the slope of the line from the point above x_{s}(x̌) to the break point. The factor S(x_{s}(x), x, x̌) comes from the analogue of the chain rule for slopes. The part S(x_{r}(x), x, x̌) takes account of the portion of the curve to the right of the break point. The other two branches of Formula (25) are analogous.

1explained in [1] and later works

Formula (25) can be applied to the example of (24). Suppose x = [1, 5] and x̌ = 3. Then x_{s}(x̌) = 2x̌^{2} − 2 = 16 > 0, so the first branch of (25) applies. Proceeding, 1/x_{s}(x̌) = 1/16, (x_{r}(x) − x_{q}(x)) = 2x + 2x = [4, 20], and S(x_{s}, x, x̌) = S(2x^{2} − 2, [1, 5], 3) = [8, 16] (computed using convexity). Thus, the slope bound is

S(∇ϕ, x, x̌) = S (χ(x^{2} − (2 − x^{2}), −2x, 2x), x, x̌)
= \{2\}\underline{∪} \frac{1}{16}[4, 20][8, 16] = [2, 20].  (26)

Applying the bound (25) in an interval Newton method, we obtain

x̃ ← 3 − 6/[2, 20] = 3 − [\frac{3}{10}, 3] = [0, 2.7] ⊂ x.  (27)

This computation proves that there is a critical point of ϕ in x̃. Further analysis, such as that in [8], could possibly prove that this critical point is unique. Also, iteration of the interval Newton method may lead to convergence to the critical point.

References

[1] G. Alefeld. Bounding the slope of polynomial operators and some applications. Computing, 26:227–237, 1980.

[2] G. H. Golub and C. F. Van Loan. Matrix Computations (Second Edition). Johns Hopkins University Press, Baltimore, MD, 1989.

[3] R. B. Kearfott. A Fortran 90 environment for research and prototyping of enclosure algorithms for nonlinear equations and global optimization. ACM Trans. Math. Software, 21(1):63–78, March 1995.

[4] R. B. Kearfott. Interval extensions of non-smooth functions for global optimization and nonlinear systems solvers, preprint, 1995.

[5] R. B. Kearfott. Verified Global Optimization – Interval Methods and Software. Kluwer, Dordrecht, Netherlands, to be published.

[6] A. Neumaier. Interval Methods for Systems of Equations. Cambridge University Press, Cambridge, England, 1990.

[7] H. Ratschek and J. Rokne. New Computer Methods for Global Optimization. Wiley, New York, 1988.

[8] S. M. Rump. Verification methods for dense and sparse systems of equations. In J. Herzberger, editor, Topics in Validated Computations, pages 63–135, Amsterdam, 1994. Elsevier Science Publishers.

[9] S. M. Rump. New results on validation algorithms for large systems of equations, presented at SCAN’95.

Addresses:

R. B. Kearfott, University of Southwestern Louisiana, Department of Mathematics, U.S.L. Box 4-1010, Lafayette, Louisiana 70504-1010, USA.