INTERVAL ANALYSIS: NONDIFFER-ENTIABLE PROBLEMS

Introduction.

Nondifferentiable problems arise in various places in global optimization. One example is in l_{1} and l_{∞} optimization. That is,

min_{x} ϕ(x) = min ∥F ∥_{1} = min_{x} ∑_{i=1}^{m} |f_{i}(x)| (1)

and

min_{x} ϕ(x) = min ∥F ∥_{∞} = min_{x} { max_{1≤i≤m} |f_{i}(x)|}

(2)

where x is an n-vector, arise in data fitting, etc., and ϕ has a discontinuous gradient. In other problems, piecewise linear or piecewise quadratic approximations are used, and the gradient or the Hessian matrix are discontinuous. In fact, in some problems, even the objective function can be discontinuous.

Much thought has been given to nondifferentiability in algorithms to find local optima, and various techniques have been developed for local optimization. Some of these techniques can be used directly in interval global optimization algorithms. However, the power of interval arithmetic to bound the range of a pointvalued function, even if that function is discontinuous, can be used to design effective algorithms for non-differentiable or discontinuous problems whose structure is virtually identical to that of algorithms for differentiable or continuous problems. Posing as continuous problems.

Several techniques are available for re-posing problems as differentiable problems, in particular for Problem 1 and Problem 2. One such technique, suggested in [4, p. 74] and elsewhere, involves rewriting the forms |e|, max{e_{1}, e_{2}}, and min{e_{1}, e_{2}} occurring in variable expressions in the objective and constraints in terms of additional constraints, as follows:

• Replace an expression |e| by a new variable x_{n+1} and the two constraints x_{n+1} ≥ 0 and x_{n+1}^{2} = e^{2}.

• Replace max{e_{1}, e_{2}} by

(e_{1} + e_{2} + |e_{1} − e_{2}|)/2

.

• Replace min{e_{1}, e_{2}} by

(e_{1} + e_{2} − |e_{1} − e_{2}|)/2

.

Alternately, as explained in [1] and elsewhere, the entire Problem 1 and Problem 2 can be replaced by constrained problems. In particular, Problem 1 can be replaced by

minimize ∑_{i=1}^{m} v_{i}

subject to v_{i} ≥ f_{i}(x), i = 1, …, m,
v_{i} ≥ −f_{i}(x), i = 1, …, m,

where the v_{i} are new variables. (3)

Likewise, Problem 2 can be replaced by

minimize v

subject to v ≥ f_{i}(x), i = 1, …, m,
v ≥ −f_{i}(x), i = 1, …, m,

where v is a new variable.

(4)

A special method for minimax problems. In [3], a special interval algorithm for Prob-

lem 2 is presented.

Treating as continuous problems.

Due to inclusion properties of interval arithmetic, interval algorithms based on a particular degree of smoothness can be effective, essentially unchanged when less smoothness is present. In particular,

• If the objective function is discontinuous, algorithms designed for continuous objective functions can be used effectively.

• If the function is non-smooth (that is, if the gradient has discontinuities), then algorithms based on second-order information can often be used effectively.

For a brief discussion and further references for these general algorithms, see Interval analysis: Unconstrained and constrained optimization. For a more in-depth discussion of how continuous algorithms can be used for discontinuous problems, see [2, Ch. 6]. The main ideas are highlighted below.

Minima of ϕ : R^{n} → R^{1} can still be located when the objective ϕ is discontinuous because bounds on the range of ϕ are all that is necessary to do a branch and bound search. For a simple example, suppose

ϕ(x) = \{ \begin{matrix}x^{2} & if x ≤ 1, \\ 1 + x & if x > 1, \end{matrix} \}  (5)

and suppose the interval [−2, 2] is to be searched for global minima. For illustration purposes, suppose ϕ(0.25) = 0.125 has been evaluated, so that 0.125 is an upper bound on the global optimum, and suppose the subinterval x = [0.5, 1.5] is to be analyzed. To obtain an interval enclosure for the range of ϕ over x, we take

ϕ(x) ∈ [0.5, 1.0]^{2} \underline{∪} (1 + [1.0, 1.5])
= [0.25, 1.0] \underline{∪} [2.0, 2.5] = [0.25, 2.5],

where a \underline{∪} b is the smallest interval that contains both a and b. Thus, since 0.125 < [0.25, 2.5], a minimum of ϕ cannot possibly occur within the interval [0.5, 1.5].

Similar considerations apply if the gradient ∇ϕ is discontinuous. In such cases, the gradient test (see Interval analysis: Unconstrained and constrained optimization) will keep boxes that either contain zeros of the gradient or critical points corresponding to gradient discontinuities where the gradient changes sign.

When the gradient is discontinuous, interval Newton methods can still be used for iteration, as well as to verify existence. (See [2, (6.4) and (6,5),p. 217] for a formula, and see Interval analysis: Interval Newton methods for an introduction to interval Newton methods, and see Interval analysis: Interval fixed point theory for an explanation of interval fixed point theory.). Application to problems with discontinuous gradients is based on extended interval arithmetic (with infinities) and astute computation of slope bounds; see Interval analysis: The slope interval Newton method for an explanation of slopes, and see [2, pp. 214–215] for details. An example. Consider

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

This function has both a root and a cusp at x = 1, with a left derivative of −3 and a right derivative of −1 at x = 1. If 1 ∈ x, then a slope enclosure is given by S(f, x, x) = [−1, 1](x+x−1)−2. Consider using 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 x̌ = 0.9 of x^{(k)}, and x^{(0)} = [0.7, 1.1], where S(f, x^{(k)}, x̌^{(k)}) is a bound on the slope enclosure of f at x̌. (See the figure for the concept of slope range.)

[figure: 0.0; 0.2; 0.4; 0.6; 0.8; 1.0; 0.7; 0.8; 0.9; 1.0; 1.1; 1.2; slope range; f(x) = |x^{2} − x| − 2x + 2]

The concept of a slope range for a non-differentiable function.

An initial slope enclosure is then S(f, [0.7, 1.1], 0.9) = [−3, −1],

x̃ = .9 − .29/[−3, −1] = [.99\overline{6}, 1.19],

Interval analysis: Unconstrained and constrained optimization Interval analysis: Unconstrained and constrained optimization Interval analysis: Interval Newton methods Interval analysis: Interval fixed point theory Interval analysis: The slope interval Newton method

3  date: November 6, 1998  file: kearfo05

and x^{(1)} = [0.99\overline{6}, 1.1]. If this interval Newton method is iterated, then on iteration 3, existence of a root within x^{(3)} was proven, since x^{(3)} ⊂ int(x^{(2)}), where int(x^{(2)}) is the interior of x^{(2)}. For details, see [2, pp. 224–225].

References

[1] Gill, P. E., Murray, W., and Wright, M.: Practical Optimization, Academic Press, New York, 1981.

[2] Kearfott, R. B.: Rigorous Global Search: Continuous Problems, Kluwer, Dordrecht, Netherlands, 1996.

[3] Shen, Z., Neumaier, A., and Eiermann, M. C.: ‘Solving Minimax Problems by Interval Methods’, BIT 30 (1990), 742–751.

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

R. Baker Kearfott

Department of Mathematics University of Southwestern Louisiana

U.S.L. Box 4-1010, Lafayette, LA 70504-1010 USA E-mail address: rbk@usl.edu

AMS1991SubjectClassification: 65G10, 65H20. Key words and phrases: non-differentiability, interval slopes, verification, interval computations, global optimization.