On Existence and Uniqueness Verification for Non-Smooth

Functions

by

R. Baker Kearfott rbk@louisiana.edu

Department of Mathematics, University of Louisiana at Lafayette

• We will show actual computations, to illustrate the relationship between traditional interval Newton methods and degree theory.

• We will illustrate how the computations can succeed or break down in non-smooth problems.

Credits: My former student, Jianwei Dian, who supplied both inspiration and perspiration.

Non-Smooth Root Verification May 25, 2002 VC02–1

The General Question

Let F (x) = 0 represent a system of n equations in n unknowns, and suppose x̌ is a numerical approximation to a solution x^{∗}, F (x^{∗}) = 0. We wish to compute bounds

x = (x_{1}, x_{2}, …, x_{n})
= ([\underline{x}_{1}, \overline{x}_{1}], [\underline{x}_{2}, \overline{x}_{2}], …, [\underline{x}_{n}, \overline{x}_{n}],

such that x̌ is the center of x, and such that x is guaranteed to contain a solution x^{∗} to F (x) = 0. That is,

Given F : x → ℝ^{n}, where x ∈ 𝕀ℝ^{n}, rigorously verify:

• there exists a x^{∗} ∈ x such that F (x^{∗}) = 0.

(1)

Here, 𝕀ℝ^{n} represents the set of interval n-vectors.

Interval Newton Methods

The Traditional Setting

If the Jacobi matrix F′(x^{∗}) is non-singular and continuous in x, then we can use an interval Newton method:

x̃ = N(F; x, x̌) = x̌ + v,

where

Σ(A, −F (x̌)) ⊂ v,

where A is a Lipschitz matrix for F over x,

and where Σ(A, −F (x̌)) = {x ∈ ℝ^{n} | ∃A ∈ A with AX = −F (x̌)} .

We have:

Theorem 1 (see Neumaier’s book) Suppose x̃ = N(F; x, x̌) is the image of x and x̌ under an interval Newton method. If x̃ ⊆ x, it follows that there exists a unique solution of F (x) = 0 within x.

Non-Smooth Root Verification May 25, 2002 VC02–3

Modifications for Singular / Non-Smooth Systems

The Topological Degree

• We can verify existence of solutions to F (x) = 0 within x, even when det(F′(x^{∗})) = 0.

• We do this with the topological degree d(F, x, 0) of F over x.

• If det(F′(x)) ≠ 0 when F (x) = 0 , then

d(F, x, 0) = ∑ ; {x∈int(x), \atop F (x)=0} sgn(det(F′(x))).

• The integer d(F, x, 0) is continuous in F and depends only on values of F on the boundary ∂x, so F′ may be singular or non-smooth in the interior int(x).

• d(F, x, 0) ≠ 0 ⇒ F (x) = 0 has a solution in x^{∗} ∈ x.

Non-Smooth Root Verification May 25, 2002 VC02–4

Modifications for Singular / Non-Smooth Systems

The Theorem Used in the Algorithms

• The boundary of x consists of:

x\underline{k} ≡ (x_{1}, …, x_{k−1}, \underline{x}_{k}, x_{k+1}, …, x_{n})^{T} ,
x\overline{k} ≡ (x_{1}, …, x_{k−1}, \overline{x}_{k}, x_{k+1}, …, x_{n})^{T} ,

where k = 1, …, n.

• For fixed ℓ, 1 ≤ ℓ ≤ n, define

\begin{matrix}F_{¬ℓ}(x) = \\ (f_{1}(x), …, f_{ℓ−1}(x), f_{ℓ+1}(x), …, f_{n}(x))^{T} . \end{matrix}

• For this ℓ, define \underline{K_{0}(s)} as that subset of {k|k ∈ {1, …, n}} such that F_{¬ℓ} = 0 has solutions on x\underline{k} and sgn(f_{ℓ}) = s at these solutions; similarly define \overline{K_{0}(s)} such that F_{¬ℓ} = 0 has solutions on x\overline{k} and sgn(f_{ℓ}) = s at these solutions, where s ∈ {−1, +1}.

The Theorem Used in the Algorithms (continued)

Theorem 2 If F is continuous, F ≠ 0 on ∂x, and there is an ℓ, 1 ≤ ℓ ≤ n, such that:

(1) F_{¬ℓ} ≠ 0 on ∂x\underline{k} or ∂x\overline{k}, k = 1, …, n;

(2) det(F′_{¬ℓ}) ≠ 0 whenever F_{¬ℓ} = 0 on ∂x. Then

d(F, x, 0) = (−1)^{ℓ−1}s

· \{_{k∈\underline{K_{0}(s)}}^{∑}(−1)^{k}

∑ ; {x∈x\underline{k} \atop F_{¬ℓ}(x)=0} sgn |\frac{∂F_{¬ℓ}}{∂x_{1}x_{2} … x_{k−1}x_{k+1} … x_{n}}(x)|

+ _{k∈\overline{K_{0}(s)}}^{∑}(−1)^{k+1}

∑ ; {x∈x\overline{k} \atop F_{¬ℓ}(x)=0} sgn |\frac{∂F_{¬ℓ}}{∂x_{1}x_{2} … x_{k−1}x_{k+1} … x_{n}}(x)|\} .

Non-Smooth Root Verification May 25, 2002 VC02–6

Simplifications to Make It Practical

In our methods, we

1. precondition F;

2. choose the coordinate widths w(x_{k}), 1 ≤ k ≤ n to have F_{¬ℓ}(x\underline{k}) ≠ 0 and F_{¬ℓ}(x\overline{k}) ≠ 0 for all k except k = n − p to k = n, where p is the dimension of the null space. This eliminates most terms in Theorem 2.

3. We then use a p-dimensional search on the remaining several faces of x to find the solutions of F_{¬ℓ} = 0.

4. In certain instances, we use a heuristic to guess the value of d(F, x, 0).

Simplifications to Make It Practical

The Preconditioner

We use incomplete LU factorization (with full pivoting) to put the Jacobi matrix into the form

Y F′(x^{∗}) ≈ ( \begin{matrix}1 & 0 & … & 0 & ∗ \\ 0 & 1 & 0 … & 0 & ∗ \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & … & 0 & 1 & ∗ \\ 0 & … & 0 & 0 & 0 \end{matrix} )

(for the case where the rank defect is 1).

An Example

f_{1}(x) = x_{1} + x_{2} + x_{3},
f_{2}(x) = −x_{2} + x_{3}^{3},
f_{3}(x) = x_{2} + x_{3}^{3},

with x = ([−0.02, 0.02], [−0.01, 0.01], [−0.01, 0.01])^{T}.

F′(x) = ( \begin{matrix}1 & 1 & 1 \\ 0 & −1 & [0, .0003] \\ 0 & 1 & [0, .0003] \end{matrix} ) , Y = ( \begin{matrix}1 & 0 & −1 \\ 0 & −1 & 0 \\ 0 & 1 & 1 \end{matrix} ) .

We thus have

Y F′(x) = ( \begin{matrix}1 & 0 & [0.9997, 1] \\ 0 & 1 & [−0.0003, 0] \\ 0 & 0 & [0, 0.0006] \end{matrix} ) ,

Y F (x) ≈ ( \begin{matrix}x_{1} + x_{3} − x_{3}^{3} \\ x_{2} − x_{3}^{3} \\ 2x_{3}^{3} \end{matrix} ) .

An Example (continued)

• We will find solutions to F_{¬3} = 0 on the boundary of x at which sgn(f_{3}) = +1.

• We choose the widths of x appropriately, then we use mean value extensions to show

– f_{1} ≠ 0 on x\underline{1} and x\overline{1} and

– f_{2} ≠ 0 on x\underline{2} and x\overline{2}.

• We then proceed with the interval Gauss–Seidel method on x\underline{3} and x\overline{3}.

• No solutions on x\underline{1}:

(Y F)_{1}(x\underline{1}) ⊆ (Y F)_{1}(0, 0, 0) + 1 · (−0.02)

+[0.9997, 1] · [−0.01, 0.01]

⊆ [−0.03, −0.01].

• Similarly, on x\overline{1}: (Y f)_{1}(x\overline{1}) ⊆ [.01, .03].

• We thus have verified (Y F)_{¬3} ≠ 0 on x\underline{1} = (−0.02, [−0.01, 0.01], [−0.01, 0.01])^{T} and x\overline{1} = (+0.002, [−0.01, 0.01], [−0.01, 0.01])^{T}.

• Similarly, we use mean value extensions for (Y f)_{2} on x\underline{2} and x\overline{2} to verify that (Y F)_{¬3} ≠ 0 on x\underline{2} and x\overline{2}.

An Example (continued)

Verifying solutions on x\underline{3} and x\overline{3} \underline{For x\underline{3}}:

• Plug in x_{3} = −0.01 and apply the interval Gauss–Seidel method. Setting {Mean Value Extension for (Y F)_{1}} = 0 gives

(Y F)_{1}(0, 0, −.01) + 1 · (x_{1} − 0)
+ 0 · x_{2}
+ [0.9997, 1](0) = 0;

solving this for x_{1} gives

x_{1} ∈ 0 − {(Y F)_{1}(0, 0, −0.01)

−([−0.01, −0.009997] · 0)} /1

= 0.009999.

• Similarly, x_{2} ∈ [−10^{−6}, −10^{−6}].

Non-Smooth Root Verification May 25, 2002 VC02–12

Verifying solutions on x\underline{3} and x\overline{3}

• Thus,

x ∈ ([0.009999], [−10^{−6}], [−0.01])^{T} = x^{(1)}.

• An interval evaluation of F (x^{(1)}) gives

Y F (x) ∈ ([0, 0], [0, 0], [−2 × 10^{−6}, −2 × 10^{−6}])^{T}

• Since (Y F)_{3} < 0, this solution can be ignored.

• Similar computations on x\overline{3} give a single point x^{(\overline{1})} at which (Y F)_{3}(x^{(\overline{1})}) > 0 and at which which

det (\frac{∂(Y F)_{¬3}}{∂x_{1}∂x_{2}}(x\overline{1})) > 0

• Combining these facts into the sum in the theorem gives a topological degree d(Y F, x, 0) = 1.

Non-Smooth Root Verification May 25, 2002 VC02–13

Summary

• d(Y F, x, 0) = 1 proves existence of a solution in x.

• This result has been proven with 2 ∗ (n − 1) mean-value-extension evaluations of (n − 1) components of F and with two incomplete Gauss–Seidel sweeps.

• Can the same process succeed when the components of F are non-smooth?

The Principles Behind Our Degree Computation

• For the interval Gauss–Seidel method, we “solve” the preconditioned variable for the i-th variable in the i-th equation.

• Success depends on the magnitude of the off-diagonal elements being larger than the mignitude of the diagonal elements of Y F′(x).

• In degree computation, we fix the last variables, eliminating the uncontrolled widths in the last column of Y F′(x).

A Non-Smooth Example

Define

f_{1}(x) = x_{1} + x_{2} + x_{3},
f_{2}(x) = \{ \begin{matrix}−x_{2} + x_{3}^{3} & if x_{2} ≥ 0, \\ −5x_{2} + x_{3}^{3} & if x_{2} < 0, \end{matrix}
f_{3}(x) = \{ \begin{matrix}x_{2} + x_{3}^{3} & if x_{2} ≥ 0, \\ 0.1x_{2} + x_{3}^{3} & if x_{2} < 0, \end{matrix}

and take

\begin{matrix}x = \\ ([−0.02, 0.02], [−0.01, 0.01], [−0.01, 0.01])^{T}. \end{matrix}

Then

\begin{matrix}Y F′(x) = \\ ( \begin{matrix}1 & [−0.66\overline{6}, 0.66\overline{6}] & [1.0000, 1.0001] \\ 0 & [ 0.33\overline{3}, 1.66\overline{6}] & [−0.0001, 0] \\ 0 & [−0.81\overline{6}, 0.81\overline{6}] & [0, 0.000355] \end{matrix} ) . \end{matrix}

• In this case, the off-diagonal entries of Y F′ (excluding the last column) are sufficiently small and narrow to allow the verification process to succeed: d(Y F, x, 0) = 1.

Non-Smooth Root Verification May 25, 2002 VC02–16

A Second Non-Smooth Example

f_{1}(x) = \{ \begin{matrix}x_{1} + x_{2} + x_{3} & if x_{2} ≥ 0, \\ x_{1} + 10x^{2} + x_{3} & if x_{2} < 0, \end{matrix}
f_{2}(x) = same as in the previous example,
f_{3}(x) = same as in the previous example.

In this case,

\begin{matrix}Y F′(x) = \\ ( \begin{matrix}1 & [−8.16\overline{6}, 8.16\overline{6}] & [1.0000, 1.00055] \\ 0 & [ 0.33\overline{3}, 1.66\overline{6}] & [−0.0001, 0] \\ 0 & [−0.81\overline{6}, 0.81\overline{6}] & [0, 0.000355] \end{matrix} ) , \end{matrix}

and the off-diagonal entries (excluding the last column) are \underline{not} sufficiently small and narrow to allow the verification process to succeed.

• Details of these two examples can be found in

   http://interval.louisiana.edu/
      preprints/nonsmooth degree.pdf

Non-Smooth Root Verification May 25, 2002 VC02–17

Additional Thoughts

• In these algorithms, the effect of the lack of smoothness is similar to the effect of non-smoothness on traditional interval Gauss–Seidel methods for verification of non-singular zeros.

• The degree d(F, x, 0) depends only on the values F on the boundary of x.

– The formula in the theorem also only involves values on the boundary.

– In principle, there is no problem applying the theorem for successful verification, as long as F is smooth on the boundary.

Additional Thoughts (continued)

• In practice, non-smoothness inside x makes simplifications as we have illustrated impossible in general.

• Direct application of the theorem involves (2n) global optimization problems.

• For details, see

http://interval.louisiana.edu/
   preprints/nonsmooth degree.pdf

• Our fast method may work anyway (as illustrated with our first non-smooth example).

• There may be other simplifications, for particular non-smooth cases, that we haven’t yet discovered.

These transparencies will be available from

http://interval.louisiana.edu/
 preprints.html

Non-Smooth Root Verification May 25, 2002 VC02–19