Twin Estimates for Slopes

by Humberto Muñoz

  R. Baker Kearfott, rbk@louisiana.edu

Department of Mathematics, University of Louisiana at Lafayette

Note: The ideas for this talk are contained in the first author’s Ph.D. dissertation Interval Slopes and Twin Slope Arithmetic in Nonsmooth Optimization, University of Louisiana at Lafayette, 2001.

Twin Estimates for Slopes May 25, VC02–1

What is Twin Arithmetic

• Twin arithmetic operates on pairs of intervals;

• The first element of the pair gives inner bounds on the exact answer.

• The second element of the pair gives outer bounds on the exact answer.

• Twin arithmetic is based on Kaucher arithmetic.

– \underline{Kaucher arithmetic} is in E. W. Kaucher, Computing (Suppl.) 2 (2), pp. 33–49, 1980.

– \underline{Twin arithmetic is introduced} in E. Gardeñes and A. Trepat, Computing 24, pp. 161–179, 1980.

– \underline{Twin arithmetic is clarified} in V. Kreinovich, V. M. Nesterov and N. A. Zheludeva, Reliable Computing 2 (2), pp. 119–124, 1996.

Twin Estimates for Slopes May 25, VC02–2

Why Do We Consider Inner Bounds?

• To obtain bounds on the sharpness of outer estimates.

• To automatically compute elements guaranteed to be in certain sets.

– There is much development of algorithms for non-smooth optimization based on generalized gradients.

– Such algorithms require an element of the generalized gradient.

– We have analyzed relationships between interval slopes and generalized gradients.

– We compute inner slope bounds with twin arithmetic, to get elements of the generalized gradient.

What Are Interval Slopes?

• A slope set A = S(F, x, x̌) for F at x̌ is any set with the property that ∀x ∈ x, ∃A ∈ A such that

F (x) − F (x̌) = A(x − x̌).

• We denote any smallest such set by S^{#}(F, x, x̌).

• Outer bounds on S^{#}(F, x, x̌) can be computed via automatic differentiation. (See Kearfott’s 1996 book or Ratz’ dissertation.)

Alefeld (1980) and Krawczyk and Neumaier (1985) introduced the slope concept, while Shen and Wolfe (1989, etc.) furthered the ideas. Hansen (1993), one of the authors (1996), Ratz (1997), Oliviera (1996) and others have used the concept in optimization.

Twin Estimates for Slopes May 25, VC02–4

Slopes for Non-Smooth Functions

An Illustration

S^{#}(F, x, x̌), where F (x) = max{x_{q}(x), x_{r}(x)}.

What About Generalized Gradients?

• Generalized gradients also are designed to describe the variation of non-smooth functions F.

• The basic definition of generalized gradient is more involved than the definition of slope.

• Generalized gradients are obtained as limits at a point

• To our knowledge, general techniques of automatically computing generalized gradients have not been developed in the literature.

• Nonetheless, there is much literature on algorithms involving generalized gradients.

Generalized Gradients

Some Intuition

Theorem 1 (Clarke’s book, p. 63) Let f : ℝ^{n} → ℝ be Lipschitz near x, and suppose S is any set of Lebesgue measure 0 in ℝ^{n} and Ω_{f} ∪ S is the set of points at which f is not differentiable. Then the generalized gradient ∂f(x) obeys

\begin{matrix}∂f(x) = \\ co \{lim ∇f(x_{i}) : x_{i} → x, x_{i} ∉ S ∪ Ω_{f}\} , \end{matrix}

where co represents the convex hull of all limits of convergent sequences ∇f(x_{i}) and x_{i} is any sequence in ℝ^{n} \ (Ω_{f} ∪ S) converging to x.

Generalized Gradients

Some References

The theoretical development: F. H. Clarke, Optimization and Nonsmooth Analysis, Classics in Applied Mathematics, SIAM, Philadelphia, 1990 (originally Wiley, 1983)

Some Algorithms: Krzysztof C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Springer-Verlag, Berlin, 1985.

Coordinate Projections

Generalized Gradients

• Neither Clarke’s generalized gradient nor interval slopes are rectangularly-shaped sets (i.e. interval vectors).

• We have found comparisons of the coordinate-wise projections of these sets to be the most meaningful comparisons.

• Coordinate-wise projections of the generalized gradient (from Clarke’s book):

Definition 1 The i-th projection, π_{i}∂f(x_{1}, …, x_{n}), of the generalized gradient ∂f is the set

π_{i}∂f(x_{1}, …, x_{n}) = {z_{i} ∈ ℝ : for some z_{j} ∈ ℝ, j = 1, …, n, j ≠ i, (z_{1}, …, z_{i−1}, z_{i}, z_{i+1}, …, z_{n}) ∈ ∂f(x)} .

Relationships between Generalized Gradients and

Slopes

Slopes at a Point?

• For non-smooth functions, the limiting value of the slope as we make the domain smaller is a non-degenerate set similar to the generalized gradient.

• Formally, we define this limiting set as

lim_{w(x)→0} S^{#}(F, x, x̌) =

[lim inf_{x→x̌} \frac{f(x)−f(x̌)}{x−x̌}, lim sup_{x→x̌} \frac{f(x)−f(x̌)}{x−x̌}] .

Twin Estimates for Slopes May 25, VC02–10

Coordinate Projections

Interval Slopes and Comparisons

Definition 2 Let f : x ⊂ ℝ^{n} → ℝ be Lipschitz near x̌. For i = 1, …, n, the ith projection π_{i} lim_{w(x)→0} S^{#}(F, x, x̌) is defined as the set

\begin{matrix}lim_{w(x)→0} cl\{s_{i} ∈ ℝ : ∃s ∈ ℝ^{n}, \\ f(x) − f(x̌) = s · (x − x̌), x ∈ x, x ≠ x̌\}. \end{matrix}

Theorem 2 Let f : x ⊂ ℝ^{n} → ℝ be Lipschitz of rank K near x̌. Then

lim_{w(x)→0} π_{i} S^{#}(F, x, x̌) ⊆ π_{i}∂f(x̌).

• Thus, if we compute inner bounds on the coordinates of the slopes, we obtain elements of the generalized gradient.

How Do We Automatically Compute Inner Interval Slopes?

• We use twin arithmetic to obtain inner bounds for rational expressions.

• We have developed a special analysis to obtain sharp inner estimates for particular elementary functions such as max{f_{1}, f_{2}} and min{f_{1}, f_{2}}.

• Non-sharp inner slope estimates for any function f : ℝ → ℝ can always be obtained by computing

\frac{f(x) − f(x̌)}{x − x̌} ⊆ S^{#}(f, x, x̌)

for a finite number of points x ∈ x, x ≠ x̌.

• This is all automated through usual automatic differentiation procedures, as used to compute partial derivatives or ordinary slopes.

Twin Estimates for Slopes May 25, VC02–12

Additional Results

Discontinuous Functions

• lim_{w(x)→0} S^{#}(f, x, x̌) = (−∞, −2].

• 0 ∉ lim_{w(x)→0} S^{#}(f, x, x̌).

• Nonetheless, f has an infimum at x̌.

Twin Estimates for Slopes May 25, VC02–13

Discontinuous Functions

• We want global optimization algorithms to detect critical points corresponding to extrema.

• Symmetric slopes are used for this purpose:

Definition 3 Let f : ℝ^{n} → ℝ. The vector SS is said to be a symmetric slope set for f over x and centered on the interval vector x̌ if, for each coordinate vector e_{i}, x ∈ x and x̌ ∈ x̌, x ≠ x̌,

f(x) − lim_{t↑0} f(x̌ + te_{i}) = S_{i1} · (x − x̌) and
f(x) − lim_{t↓0} f(x̌ + te_{i}) = S_{i2} · (x − x̌),

for some S_{i1}, S_{i2} ∈ SS, i = 1, …, n.

• Symmetric slopes are related to the non-smooth analysis concept of semigradient.

Twin Estimates for Slopes May 25, VC02–14

What About the Details?

(Careful definitions, additional theory, formulas, etc.)

• Details can be found in Humberto Muñoz’ Ph.D. dissertation (University of Louisiana at Lafayette, December, 2001)

• Results include many additional theoretical comparisons, including comparisons with slant slopes, etc.

• We are presently working on additional publications.

• We are presently finishing an algorithm for twin arithmetic and twin slopes, for possible publication in ACM TOMS.