TRAJECTORY METHODS IN GLOBAL OPTIMIZATION

IMMO DIENER

Institut für Numerische und Angewandte Mathematik, University of Göttingen, Germany.

Abstract. We review the application of trajectory methods (not including homotopy methods) to global optimization problems. The main ideas and the most successful methods are described and directions of current and future research are indicated.

Key words: Global Optimization, Continuous Newton Method, Trajectory Method.

1. Introduction

Consider the following problem: Given a set B ⊂ IR^{n} and a continuous function F : B → IR, determine f_{∗} = inf_{x∈B} f(x) and some or all points in f^{−1}(f_{∗}) provided this set is nonempty. This is about the most general form a global optimization problem on a finite dimensional space can take. It includes discrete (combinatorial) optimization problems as well as continuous constraint and unconstraint problems. A related problem is: Given B ⊂ IR^{n} and a continuous map F : B → IR^{n}, determine some or all points in Zero(F, B) := F^{−1}(0). This includes fixed point problems and the solution of nonlinear equations.

The above problems are obviously too general to be dealt with under a unifying aspect. So we restrict ourselfs to the case where B is a closed connected n-dimensional manifold M. We could allow M to have a boundary ∂M or, in many cases, could allow for B beeing a regular constraint set or even a manifold with generalized boundary as defined in [22]. However, the presence of a boundary, as usual, demands a special treatment and so we restrict our attention mainly to the case of closed (not necessarily compact) manifolds without boundary.

So we consider the following two problems:

(p) Given a connected, n-dimensional closed differentiable manifold M ⊂ IR^{N} and a smooth function f : M → IR. Determine the global minimum f_{∗} = inf_{x∈M} f(x) of f on M and some or all of the global minimizers, that is points in f^{−1}(f_{∗}).

(P) Given a connected, n-dimensional closed differentiable manifold M ⊂ IR^{N} and a smooth vectorfield F : M → T M on M, where T M denotes the tangent bundle of M. Determine some or all zeros of F on M. A point p ∈ M is called a regular point of f, if the differential T_{p}f : T_{p}M → IR

is onto and a critical point otherwise. As is well known, the global minimizers are critical points of f and thus if there are only finitely many such points, the global minimizers of problem (p) can be determined by finding all the critical points (which is a problem of type (P), where F is the gradient vectorfield of f) and then evaluating f in these points. This common strategy has the main drawback that there might be many more critical points (i.e. local minimizers and maximizers, saddle points) than global minimizers.

In the sequel we suppose that f is bounded from below and furthermore f^{−1}(f_{∗}) is nonempty.

A trajectory method for (p) or (P) defines a set K of finitely many curves (paths, trajectories) on M wich are construced in such a way that one or all solutions to the problem are a priori known to lie on paths from K or at least there is good reason to suspect that some or all solutions are on such paths. In many cases these curves are solution trajectories to ordinary differential equations of first or second order. However, there are also a number of other appealing possibilities as we shall see below.

To actually solve the given problem, one has to numerically follow (trace) the paths in K and note the solutions thus found. To trace the curves, one needs a starting point for the numerical path-following method on each component of the curves in K and in general it turns out that − either it is a priori known that every solution lies on a path in K but one cannot

actually construct a starting point for each component K_{i} in K, − or the starting points are no problem but it is impossible to guarantee that all

(or any) solutions lie on the traced trajectories, − or one curve is a “space filling” curve and tracing makes not much sense (at

least in higher dimensions).

This dilemma is not a shortcoming of trajectory methods however, but just another manifestation of a general handicap of all methods in global optimization. Under the given assumptions no finite method can guarantee to find a point x^{∗} ∈ M such that f(x^{∗}) differs from f_{∗} by no more that a specified accuracy. This follows immediately from the indentation argument which, in the authors opinion, should be a main lemma in global optimization:

From finitely many function values and derivatives and the information that f is C^{k} (k ∈ IN_{0} ∪ {∞} known) one cannot construct a lower bound for f_{∗}.

The reason is simply that one can take a point y^{∗} ∈ M and an ϵ-neighborhood U of y^{∗} such that no point in U has been considered. Then it is well known, that one can modify f on U such that f(y^{∗}) takes on any desired value, the modification is invisible from outside U and the modified function is still C^{k} on M.

Any method not susceptible to this argument must make global assumptions on f (like known Lipschitz constant for some derivative, or f of special form etc.) or somehow generate global information on f (like interval methods).

For (P) there is another class of methods which employs the tracing of path until one finds solutions, namely homotopy methods. Although such methods are pathfollowing methods, they are not trajectory methods from the viewpoint of this paper. The distiction made here is a conceptual one and might be clarified as follows.

Consider problem (P) on IR^{n}. The idea of a homotopy method is to consider instead of the difficult problem F (x) = 0 an appropriate easier problem G(x) = 0 which can be solved. Suppose the zeros of G are x_{1}^{∗},…, x_{k}^{∗}. Then one slowly “deforms” G into F and tries to follow the changes that the solutions to G(x) = 0 undergo during the deformation. In other words, one introduces a new parameter t ∈ [0, 1] and defines a homotopy from G to F, that is a differentiable map

H : IR^{n} × [0, 1] → IR^{n},

such that H(x, 0) = G(x) and H(x, 1) = F (x). Then one tries to follow the implicitely defined paths x_{i}(t) with

H(x_{i}(t), t) = 0

and x_{i}(0) = x_{i}^{∗}. If this can be done upto t = 1 one gets H(x_{i}(1), 1) = 0 = F (x_{i}(1)). So x_{i}(1) is a zero of F. Note that the paths x_{i}(t) are in IR^{n} × [0, 1], not in the original domain IR^{n}. The geometry of F is no design aspect and does not explicitly enter into the method. Unsually it is unclear how G and the homotopy H should be choosen and in accordance with the indentation argument, convergence results can only be obtained for special classes of functions.

For a trajectory method the idea is quite different. Consider as an example problem (p): Minimize f : IR^{n} → IR. One can try to visualize f as a landscape of smooth hills and valleys. Suppose one would take a marble, give it some initial velocity and let it roll down the landscape. The marble would pick up speed in downhill places, traverse small ponds and might finally get stuck in a deep trough. Of course, something quite different could happen. The marble migth even slow down in uphill motion and come to rest at the top of a hill. But in many cases it seems reasonable that such marble-rolling, given the “right” equations of motion (a second order ordinary differential equation in this case) should give good results.

Or one could choose a path such that for any point on it, the gradient (the direction of steepest increase in function value) lies in a fixed 1-dimensional subspace. This leads to a continuous version of Newtons method.

Generally, the intent is construct paths in the domain space and let them depend explicitly on the geometry (f, Df, D^{2}f) of the function. Although in some cases the paths of trajectory methods can be interpreted as projections of paths generated by suitable homotopy methods (c.f. Newton-homotopy vs. Newton trajectories) onto the domain space one should keep the diffent philosophies of the two approaches in mind. And generally, if a method can be viewed in both ways, these two viewpoints can each contribute to the understanding of what goes on.

Viewing trajectory methods in connection with differential equations might be called an analytic approch. We will consider a different possibility, a more algebraic or topological viewpoint which proves very useful.

Again, consider problem (P) on IR^{n}. We want to define curves in M which pass through all zeros of F. So we might consider a 1-dimensional set D in the image space IR^{n} such that 0 ∈ D. Then we consider the preimage K := F^{−1}(D). Obviously all zeros of F are contained in K. Moreover, if D is a “smooth” set and F fulfills some slight regularity conditions, then K will be a smooth locally 1-dimensional set nearly everywhere. So K might be traced numerically and one could find all zeros of F if one could find a (starting) point on each one of the possibly many connected components of F^{−1}(D).

If D can be desribed as the set of zeros for some smooth function G : IR^{n} → IR^{n−1}, that is D := G^{−1}(0), then the points x in K are the ones with G(F (x)) = 0 and thus K = (G ∘ F)^{−1}(0). Thus the tangent direction in a point x ∈ K is in the kernel of DG(F (x))DF (x) and is uniquely determined if this matrix has full rank n − 1. This can be used in an algorithm for tracing K. How should one choose D? This depends on the form of F and generally nothing is known about this problem. If we take a straight forward choice and choose D to be a line then we again get the Newton trajectories. However, for any F there must be “good” choices for D, because there certainly exist smooth paths W passing through all zeros of F. Taking such a curve W and setting D := F (W) is certainly a very good choice. Except for the case of Newton trajectories (which will be discussed further below) this nice approach has not been investigated so far.

In this paper we only consider trajectory methods designed to deal with global problems which means with problems where a global solution is sought among possibly many local solutions (in case of problems of type (p)), or where several or all solutions are sought for (in case of problems of type (P)). So, in the sense of this paper, global method does not mean a method which is designed to find one solution from any starting point and then stop. Although many such methods have been designed for instance to cope with the problem of following small curved valleys in local optimization these methods will not be dealt with in this paper.

This paper is organized as follows: In section 2 we consider some examples of trajectory methods based on ordinary differential equations. Then, in section 3, we describe a generalization of the continuous Newton method based on an algebraic instead of the usual analytic definition. In section 4 we outline a general method for the determination of the connected path–components resulting from certain trajectory methods. We conclude with section 5 where we put forward some general remarks on the efficiency and applicability of trajectory methods to problems of global optimization.

2. Using differential equations

Several authors have considered the use of second order differential equations to construct search trajectories (see for instance [14, 30, 29, 19, 35, 18, 32, 2]). In analogy with classical mechanics, these search trajectories are based on Newton’s law for a particle of mass m(t) in a potential f subject to a dissipative force −v(t)ẋ(t):

m(t)ẍ(t) + v(t)ẋ(t) = −∇f(x(t)).

Snyman and Fatti in [30] for instance use the equation

ẍ = −∇f(x), x(0) = x_{0}, ẋ(0) = 0,

where the starting point x_{0} is choosen at random and a Bayesian stopping rule is used.

In the next subsections we shall describe Griewank’s method and the method of Snyman and Fatti more closely and then we will give a short description of a method initially introduced by Branin in [4] which is based on the first order differential equation

\frac{d}{dt}F (x) ± F (x) = 0, x(0) = x_{0}

Today this method is called continuous Newton method and in chapter 3 we shall take another look at this method from a different perspective.

2.1. Griewank’s method

In [14] Griewank imagines a function f : IR^{n} → IR which is the sum of a “wellbehaved” function u having a unique minimizer x^{∗} and a bounded oscillatory pertubation v such that some sort of smoothing process would make f approximately the same as u (for instance f could stem from a truncation or interpolation of noisy data for u). Provided the amplitude of the pertubation is low compared to the range of u–values, f attains its global minimum and all other local minima with values near f_{∗} in a neighborhood of x^{∗}. Under these circumstances Newton-like methods or many versions of multistart methods are likely to compute many local minima far away from x^{∗}.

Using a target level c which is slightly larger than f_{∗} Griewank formulates five desirable properties of a search trajectory:

(i) The trajectory cannot converge to minima with values greater than c. (ii) As long as f ≫ c, the trajectory is little affected by the pertubation v and tries

to follow a descent direction with respect to −∇u. (iii) As f tends to c, the trajectory minimizes more thoroughly and finally reduces

to a local minimization technique when f ≤ c. (iv) The trajectory does not explicitly depend on the Hessian D^{2}f.

(v) The trajectory is invariant with respect to translations of the variables and the multiplication of f − c by a positive scalar. He then shows, that these requirements are satisfied by the solutions of the fol-

lowing second-order differential equation:

ẍ = −e(I − ẋẋ^{t})\frac{∇f(x)}{f(x) − c}, e > 0,  (1)

from any initial point (x_{0}, ẋ_{0}) with f(x_{0}) > c and ∥ẋ_{0}∥ = 1. For any trajectory of this system he obtains that the current direction ẋ is an average of previous negative gradients weighted by (f(x) − c)^{−e−1}. Assuming that the target level f^{−1}(c) is a smooth (n − 1)–dimensional manifold, a trajectory may stay in the interior of one of the open connected components of {x ∈ IR^{n} | f(x) > c}, for all t ≥ 0, or approach the boundary f^{−1}(c). There is a maximal t_{c} ∈ (0, ∞], such that x(t) is defined on [0, t_{c}). If t_{c} < ∞, then lim_{t→t_{c}} x(t) = x_{c} ∈ f^{−1}(c) and furthermore lim_{t→t_{c}} ẋ(t) = −∇f(x_{c})/∥∇f(x_{c}∥. Thus in this case the solutions of (1) transform gradually to the trajectory of steepest descent as f goes to c in accordance with the third requirement and so such trajectories can be extended in a continuously differentiable way by a trajectory of steepest descent,

ẋ = −∇f(x)/∥∇f(x)∥, x(t_{c}) = x_{c}.  (2)

The resulting complete search trajectories are then completely determined by the initial point (x_{0}, ẋ_{0}) and solve the implicit system

max[0, f(x) − c]ẍ + e(I − ẋẋ^{t})∇f(x) = 0.

Unless the target level is never attained, the solutions of (2) converge to a minimum or possibly saddle point with value not greater than c. Of course this combination with steepest descent is only a theoretical construct as there are much more efficient techniques for local minimization.

Ideally the search leads into regions with low function values but this attempt can fail completely, for instance if c is so low that f^{−1}(c) is empty, or if the trajectory is trapped in the region of attraction of an unacceptable local minimum with f > c and with steep surrounding slopes. The first problem requires a sufficient increase of c while the second requires a suitable decrease of e.

A drawback of equation (1) is its symmetry: it is unaltered by a reversed parametrization from which it follows, that f(x(t)) cannot be bounded in terms of the initial data x_{0}, ẋ_{0}, c and e. Furthermore system (1) is not independent of linear transformations on the variables of f which can cause the unfortunate zigzagging known of the steepest-descent method in valleys. For local minimization this can be overcome by a variable metric method, i.e. a local scaling of the contours by a suitable linear transformation and a similar modification can be applied to equation (1).

Because of the indentation argument no global convergence results for arbitrary differentiable objective functions can be proven. In fact, according to Griewank, it can be shown that for any nonself-intersecting, three times differentiable path x(t) of length t_{1} < ∞ and any positive function 0 < ϕ(t)−c ∈ C^{1}[0, t_{1}] there is an objective function f ∈ C^{1}(IR^{n}) such that equation (1) is satisfied with f(x(t)) ≡ ϕ(t).

This is disappointing, of cause, but was to be expected. However, Griwank proves some convergence results for separable objective functions of the form

f(x) = f(x̂) + γ(r) h(\frac{x − x̂}{r}) r^{d},

where r = ∥x − x̂∥, d > 0 and γ, h are twice continuously differentiable. From the analysis of such functions he derives heuristic rules for the choice and (possible update) of the parameter e in equation (1).

For numerical integration the equation (1) is not suitable because ∥ẍ∥ as well as the Jacobian ∂(ẋ, ẍ)/∂(x, ẋ) can become arbitrarily large when f approaches the target level c. However, by applying a suitable parameter transformation such that the norm of the velocity equals f(x)−c the norm of the Jacobian can be bounded such that usual integration schemes can be used. Griewank discusses stability aspects, choice of stepsize, termination criterion and gives some experimental results.

For this purpose he considers objective functions of the form

f(x) = \frac{1}{const} ∑_{k=1}^{n} x_{k}^{2} − ∏_{k=1}^{n} cos(x_{k}/\sqrt{k}),  (3)

which have a unique global minimimizer and hundredth of local minima, and the well konwn six-hump camel-back function (see for instance [16] where also other common testfunctions for global optimization problems are given). The experiments show that care must be exercised when choosing the parameters c and e or otherwise the trajectories may bypass acceptable minima or orbit around unacceptable minima. The question how these parameters should be choosen in general remains open. However, with appropriately choosen initial data, and at least for functions not deviating to far from the model of a sum of a well-behaved Function u and a small pertubation v, Griewanks method apparently performs quite well.

2.2. The method of Snyman and Fatti

As mentioned above, Snyman and Fatti consider the equation

ẍ = −∇f(x), x(0) = x_{0}, ẋ(0) = 0.

Multiplying with ẋ and integrating gives the energy conservation relationship

\frac{1}{2}∥ẋ∥^{2} + f(x) = f(x_{0}).  (4)

Thus an imagined particle will start moving in the direction of steepest descent and its kinetic energy will increase as long as it moves downhill. By (4) it will continue past a local minimum and surmount a ridge of height less that f(x_{0}), possibly finding an even lower value of f. The minimizer x_{m} along the path and the corresponding quantities ẋ_{m} and f_{m} = f(x_{m}) are recorded. The trajectory must be terminated before it retraces or approximately retraces itself. This is done if the trajectory reaches a point at which the particle moves uphill and the function value is within a small bound ϵ from f(x_{0}), where ϵ is choosen in advance. Snyman and Fatti demonstrate that this is a reasonable criterion.

To ensure convergence to at least a local minimum a new search trajectory is started at the point x′ := (x_{m} + x_{0})/2 and with velocity ẋ_{m}/2. If this finds a lower f-value, the procedure is repeated. If not, a new trajectory is started in the midpoint of the line joining x′ and x_{m} with half the velocity of the previous starting velocity. If the level set corresponding to x_{0} is bounded and f is sufficiently differentiable it is shown that this procedure yields points converging to a stationary point of f.

Integration is performed by a simple leap-frog integration scheme which has proven to be fairly reliable with respect to energy conservation. This trajectory method is finally combined with a multi-start global minimization algorithm. The starting points are sampled randomly from the domain of interest. Such a procedure requires a rule for deciding when to stop the sampling and take the current overall minimum as an approximation to f_{∗}. Snyman and Fatti use a Bayesian approach based on the assumption that the minimum with the largest region of attraction with respect to the non-local minimization procedure outlined above is the global minimum.

The method has been successfully applied to standard testfunctions as well as the ones used by Griewank (c.f. equation (3)). The results on the testfunctions look quite promising but one must keep in mind that this is actually a variant of multistart which a piori has an asymptotic convergence guarantee and that the efficiency of such procedures depends very heavily on the choosen stopping rule and the appropriate setting of the parameters.

2.3. Branin’s method

In [4] Branin considers the problem (P) of finding possibly all solutions to F (x) = 0 on IR^{n}. He introduces the first order differential equation

\frac{d}{dt}F (x) + F (x) = 0, x(0) = x_{0},

which gives

ẋ = −DF (x)^{−1}F (x), x(0) = x_{0}.  (5)

as long as the Jacobian DF (x) is nonsingular. Applying Eulers method to equation (5) we get the usual Newton method with stepsizes h_{k}:

x_{k+1} = x_{k} − h_{k}DF (x_{k})^{−1}F (x_{k}).

This is why the trajectories of (5) are sometimes called Newton trajectories. From the analytical solution

F (x(t)) = F (x_{0})e^{−t},

it follows that the trajectories tend to a zero of F if the integration can be continued to t = ∞. Furthermore, we make the important observation, that F has constant direction on the trajectories, that is, F (x)/∥F (x)∥ stays constant on any trajectory x(t). However, the right hand side of (5) is not defined in those points, where DF (x) becomes singular.

To overcome this difficulty, one can desingularize equation (5) and consider

ẋ = ±D̃F(x)F (x),  (6)

where Ã denotes the adjoint of A satisfying ÃA = det(A)I. This equation is defined on the whole IR^{n} and the phase portrait is (up to orientation) the same as for equation (5) where both equations are defined. Now Branin suggested to trace the trajectories (6) until one finds a zero of F and then reverse the sign in (6) and continue integration until one possibly finds further zeros. He applied this approach successfully to a number of test examples.

However, equation (6) has more singularities than just the zeros of F. We also have ẋ = 0 whenever D̃F(x)F (x) = 0 but F (x) ≠ 0. These points were called extraneous singularities by Branin. The geometric structure of the set ExS(F) of extraneous singularities has been extensively studied by Jongen, Jonker and Twilt in several papers (see [23, 24] for an overview and further references). Especially, there is a generic subset of C^{∞}(IR^{n}, IR^{n}) such that for F in this subset ExS(F) is a closed stratified set in IR^{n} of codimension 2.

Early results on this and similar methods and some implementations are described in [16, 12, 13, 34, 3]. Smale [28] showed that, given appropriate boundary conditions on ∂Ω for some bounded open set Ω ⊂ IR^{n}, then for almost all x_{0} ∈ ∂Ω the paths of (6) tend to a zero of F. Furthermore, Branins method can also be viewed in the context of homotopy methods. See for instance [25, 11, 1].

However, except for some very special (but nevertheless interesting) cases, like meromorphic functions in the complex domain, (see [21, 33, 23]) no detailed knowledge on the phase portrait is available. Especially it is generally unknown under which conditions on F all or several zeros will be on a single trajectory and how appropriate starting values x_{0} could be found. In [7] an algebraic definition for Newton trajectories was given (for a similar, but more restrictive view see [17]) and a global implicit function theorem was derived and applied to the case of Newton trajectories. However, the conditions of applicability are too strong to be useful in most practical cases. But the algebraic characterization of Newton trajectories contained in [7] was a first step towards an algebraic instead of an analytic treatment of Newton trajectories. An outline of the general idea shall be given in the next section.

3. Newton–leaves

In the last section we have seen, that for Newton trajectories the direction of F stays constant on the path. This and the idea mentioned at the end of the introductory section motivates a generalized definition:

DEFINITION 1. Let F ∈ C(B, IR^{n}) and for 0 ≤ k ≤ n let V be a k–dimensional linear subspace of IR^{n}. Then we call the set

F_{V} (F, B) := {x ∈ B | F (x) ∈ V } = F^{−1}(V)

a k–Newton leaf for F. A 1–leaf is also called a Newton trajectory. ◇

Obviously the 0-leaf for F is just the set Zero(F, B) of all zeros of F in B and the n-leaf is all of B. We immediately have the following properties:

(i) If V, W are linear subspaces in IR^{n} and V ⊂ W, then F_{V} (F, B) ⊂ F_{W} (F, B). (ii) For all linear subspaces V in IR^{n} we have Zero(F, B) ⊂ F_{V} (F, B). (iii) If V, W are linear subspaces in IR^{n} then F_{V} (F, B) ∩ F_{W} (F, B) = F_{V ∩W} (F, B).

Thus Newton trajectories “live” on higher dimensional Newton leaves. Through any point x ∈ B \ Zero(F, B) exactly one Newton trajectory passes, namely F_{V} (F) with V = ⟨F (x)⟩. Any such trajectory contains all zeros of F and the intersection F_{V} (F) ∩ F_{W} (F) of two distinct Newton trajectories is equal to Zero(F). This holds in general, even if the zeros of F are degenerate, and is a key feature for the practical interest in these sets.

However, Newton leaves need not be connected. Of cause, if we knew that for some 1–dimensional linear subspace V ∈ IR^{n} the Newton trajectory F_{V} (F) were connected, then all zeros of F could be found by tracing this trajectory numerically. In general, to trace F_{V} (F) we need a starting point on every component. (A general strategy for connecting different components will be described in section 4.)

In some cases, however, one can prove that a certain k–Newton leaf, for k > 1, for F is connected. In practice this means that an n–dimensional problem can be reduced to a k–dimensional one and since the numerical complexity for a global problem usually increases exponentially with the dimension, such a reduction can be substantial. Thus the study of general Newton leaves is relevant not only because one can get Newton trajectories as intersections of such leaves but it also has direct practical implications.

In the next subsections we first consider the geometry of Newton leaves, then we introduce certain graphs, which reflect the relations between distinct Newton leaves and the zeros of F. Finally we discuss the question when Newton leaves are connected and thus the numerical problem of determining the zeros of F can be solved or at least reduced in dimension.

3.1. Geometry of Newton leaves

Let B ⊂ IR^{n}, n ≥ 2 and let M(B) be the set of functions from C^{r}(IR^{n}, IR^{n}) which contain only finitely many zeros in B, have no zero on the boundary ∂B of B and all of whose zeros are nondegenerate; that is DF (x) is nonsingular for all x ∈ Zero(F, B). We suppose that r is “sufficiently large”. Usually r = 1 or r = 2 will be enough but sometimes r = n is required if the proof uses Sard’s theorem.

First we collect some facts about Newton leaves to aid our imagination. For details on this and the following discussion see [8, 9] and the forthcoming paper [5]. The proofs of the following statements are easy and straight forward. For brevity we suppress the arguments and simply write F_{V} := F_{V} (F, B).

REMARK 1. Let F ∈ M(B) and let F_{V} := F_{V} (F, B) be a k–Newton leaf.

(i) F_{V} can be represented as intersection F_{U} ∩ F_{W} of an l–leaf F_{U} and an m–leaf F_{W} iff l + m − n ≤ k ≤ min(l, m). So, for instance, every Newton trajectory in IR^{3} is the intersection of two 2–Newton leaves in IR^{3}.

(ii) If l + k ≤ n then for any point y ∉ F_{V} there is an l–Newton leaf F_{W} such that

y ∈ F_{W} and F_{V} ∩ F_{W} = Zero(F). (iii) If an l–leaf F_{W} intersects F_{V} in a point y ∉ Zero(F), then

max(l, k) ≤ dim(V + W) ≤ k + l − 1

Thus, a Newton trajectory intersecting F_{V} in a point y ∉ Zero(F) must be contained in F_{V}.

(iv) If 1 ≤ l ≤ k then the leaf F_{V} is the union of all l–leaves contained therein. ◇

Thus Newton leaves provide a “foliation” of B. The set–theoretic relations among the linear subspaces of IR^{n} carry over to corresponding relations among the Newton leaves in IR^{n}. (It is also interesting to draw connections to the structure of the real projective spaces P IR^{n}.)

For both theoretical and practical considerations and in the spirit of the ideas put forward at the end of the introduction we want to derive a third characterization of Newton trajectories that is often easier to work with. We would like to represent a Newton leaf F_{V} in the form F_{A}^{−1}(0) with a certain map F_{A} depending on F and V. This form is suitable for the application of methods from differential geometry.

DEFINITION 2. As usual, let B be a subset of IR^{n} and V a k–dimensional linear subspace in IR^{n} and F ∈ M(B). Let A_{V} be a Matrix whose rows form a basis of V^{⊥}. We call such a Matrix associated to V. Consider the map F_{A} : IR^{n} → IR^{n−k}, with x ↦ A_{V} F (x). Because the kernel of A_{V} is V we have F_{A}^{−1}(0) = F_{V} (F, IR^{n}). The exact form of A_{V} does not matter as long as the kernel of A_{V} is V. Then we have F_{A}^{−1}(0) ∩ B = F_{V} (F, B).

Thus F_{A}^{−1}(0) is a closed submanifold of dimension k in IR^{n} if for all x ∈ F_{V} (F, IR^{n}) the matrix A_{V} DF (x) has full rank dim V^{⊥} = n − k. In this case we call F_{V} (F, IR^{n}) a regular Newton leaf. Regularity obviously does not depend on A_{V} but only on V.

A point x ∈ F_{V} (F, B) in which rankA_{V} DF (x) is less than dim V^{⊥} is called an extraneous singularity of F_{V} (F, B). If F_{V} (F, B) is a Newton trajectory and x an extraneous singularity of F_{V} (F, B) we also call x an extraneous singularity of F. Since then x ∉ Zero(F, B) we have V = ⟨F (x)⟩. The set of extraneous singularities of F in B is denoted by ExS(F, B) ◇

Geometrically, extraneous singularities of a Newton leaf are points where the local structure of the leaf might not be that of a manifold. Especially, bifurcations may occur in such points. Since the rank of a differentiable map is lower semicontinuous the set of extraneous singularities of a Newton leaf is closed in B. A point x ∈ F_{V} (F, B) is an is an extraneous singularity of F_{V} (F, B) iff the rank of the n×(n+k)– matrix [DF (x), v_{1} …, v_{k}] is less than n, where v_{1},…, v_{k} is a basis for V. From this one can derive that an extraneous singularity x of a Newton leaf F_{V} is also an extraneous singularity for any Newton leaf F_{W} through x and contained in F_{V}. Furthermore, if k < rankDF (x), then there is an l-Newton leaf F_{W} (F, B) containing F_{V} (F, B) such that x is not an extraneous singularity of F_{W} (F, B) and l can be choosen equal to k + dim(ker D^{⊤}F (x) ∩ V^{⊥}). For further results on the structure of extraneous singularities of Newton trajectories see [23].

If x ∈ F_{V} ∩ F_{W} is not an extraneous singularities of F_{V ∩W} then F_{V} and F_{W} intersect transversally in x (i.e. the tangent space T_{x}F_{V} is not contained in the tangent space T_{x}F_{W}.) Especially Newton leaves intersect transversally in nondegenerate zeros of F. From the implicit function theorem one easily derives that around any nondegenerate zero x^{∗} of F there is a neighbourhood U of x^{∗} such that any connected component of a Newton leaf intersecting U must also contain x^{∗}. Thus, if a Newton leaf approaches a nondegenerate zero x^{∗} closely enough, it must pass through x^{∗}.

Two zeros of F ∈ M(B) which are adjacent along a single component of a regular Newton trajectory have different index. From this one gets by induction and the use of the Morse-Sard lemma:

THEOREM 1. Let F ∈ M(B) and 1 ≤ k ≤ n−1. Then any compact component of a k-Newton leaf for F which does not intersect the boundary of B contains an even number of zeros of F. ◇

Observe that in this theorem no assumptions on the extraneous singularities on the Newton leaves have been made.

Let us call a connected subset of B free (with respect to F ∈ M(B)) if it contains no zeros of F. Otherwise we call the subset bound. For applicational purpose free Newton leaves are something we do not want; for we would only waste time in searching such leaves for zeros of F. Moreover, free (n − 1)-leaves divide the image space into disconnected regions and from remark 1, part (iii) it follows that no Newton trajectory can connect points from different such regions. Therefore, if several such regions contain zeros of F then no single connected component of a Newton trajectory can string all these zeros. It is therefore important to characterize such leaves and derive conditions for there nonexistence. An easy criterion is:

THEOREM 2. Let F ∈ C^{2}(IR^{n}, IR^{n}) and k > 0. Then any compact free component C of a k-Newton leaf F_{V} (F, IR^{n}) which contains no extraneous singularities of F posesses a continuous nowhere vanishing field of tangent vectors. ◇

The tangent vectors are given by the tangent vectors for the Newton trajectories on C. Especially C cannot be a sphere S^{2m}.

THEOREM 3. Let the boundary of the bounded open set U ⊂ IR^{n} be contained in a free component of an (n − 1)-Newton leaf F_{V} (F, IR^{n}). Then every component of U contains an even number of zeros of F and any component of U which contains a zero of F also contains an extraneous singularity of F. Moreover, if \overline{U} contains neither zeros nor extraneous singularities of F then there exists a continuous map U → U (\overline{U} → \overline{U} respectively) without fixed points. ◇

The question which topological structures are possible for compact free k-leaves F_{V} (F) without extraneous singularities can be related to certain problems in differential topology, for instance to the existence of fields of tangent hyperplanes on F_{V} (F) and sphere bundles over spheres and projective spaces. Similarly, a characterization of the possible topological structures for compact bound k-leaves without extraneous singularities can be dealt with by methods from differential and algebraic topology and has to do with fiberings of such k-leaves. So, for instance, in the absence of extraneous singularities a compact bound 2-leaf cannot be homeomorphic to a torus S^{1} × S^{1} but it can be homeomorphic to the sphere S^{2}. We shall not go into details here.

3.2. The graphs Γ^{k}

The optimum for practical application is a connected Newton trajectory. Then all zeros can be found by numerically tracing the single component. Connected kleaves with k < n at least reduce the problem dimension. We next consider a relaxed question, namely when it is possible to connect all zeros of F by a net of Newton trajectories or, more generally, a net of k-Newton leaves.

DEFINITION 3. Let B ⊂ IR^{n} and F ∈ C(B, IR^{n}). Then we define for k = 0, 1,…, n graphs Γ^{k}(F, B). The vertices of Γ^{k}(F, B) are the zeros of F. Two vertices u, v in Γ^{k}(F, B) are connected by an edge iff u ≠ v and there exists a k–NL K of F such that u and v are contained in a single component of K. ◇

Observe that for 0 ≤ l ≤ k ≤ n the graph Γ^{l}(F, B) is a spanning subgraph of Γ^{k}(F, B). The graph Γ^{0}(F, B) is totally disconnected and Γ^{n}(F, B) is a complete graph. The graph Γ^{1}(∇f, IR^{n}) is similar to the graph Γ(f) defined in [20]. If Γ^{k}(F, B) is connected, this means that one can select a finite number of components of k-leaves such that any zero of F is contained in one of these k-leaf-components and one can find all zeros by exploring the problem on one such component, then selecting a component of a different k-leaf passing through a zero already found, and so on. If Γ^{k}(F, B) is disconnected for some k > 0, then no Newton trajectory contains all zeros of F within a single component.

To state conditions under which Γ^{k}(F, B) is connected we need

DEFINITION 4. Let F ∈ M(B). Then we say that condition C_{k}(B) is satisfied if no k-Newton leaf for F contains more than at most one unbounded component. ◇

Thus condition C_{k}(B) is satisfied for instance if B is bounded. Now we can state a first result on the connectedness of Γ^{k}(F, B):

THEOREM 4. Suppose B ⊂ IR^{n} is closed and connected, F ∈ M(B), k > 0 and condition C_{k}(B) is satisfied. Then: If no component of any k-Newton leaf for F is free, then Γ^{k}(F, B) is connected. ◇

Similar results are available for the case that condition C_{k} is not satisfied. The condition that no component of any k–NL for F is free is cumbersome. Could we get rid of it? Not easily because since in our theorems B is rather arbitrary one could in many cases cut off connecting leaves by a suitable modification of B without making B disconnected. Also, as has been pointed out above, free (n − 1)–leaves separate B into connected components and no Newton trajectory can reach one from the other. So, if both contain zeros of F, Γ^{1}(F, B) cannot be connected.

Still, something can be said without supposing that no component of any k–NL for F is free. We define the sets:

bound_{k}(F, B) := {x ∈ B | There exists a bound k-leaf component
through x}
bound_{k}^{∗}(F, B) := {x ∈ B | Every k-leaf component through x is bound}

Then one can prove:

THEOREM 5. Let B ⊂ IR^{n} be closed and connected, F ∈ M(B) and condition C_{k}(B) be satisfied. Then (i) if bound_{k}(F, B) is disconnected, then Γ^{k}(F, B) is disconnected too and (ii) if bound_{k}^{∗}(F, B) is connected, then Γ^{k}(F, B) is also connected. ◇

For k = 1 the gap between (i) and (ii) in the above theorem can be closed, because then the sets bound_{1}(F, B) and bound_{1}^{∗}(F, B) coincide:

THEOREM 6. Let B ⊂ IR^{n} be closed and connected, F ∈ M(B) and condition C_{1}(B) be satisfied. Then Γ^{1}(F, B) has as many connected components as bound_{1}(F, B). Especially Γ^{1}(F, B) is connected iff bound_{1}(F, B) is connected. ◇

Using the sets bound_{k}(F, B) and bound_{k}^{∗}(F, B) one can prove some interesting invariance properties for Γ^{k}(F, B) under local modification of F or B. For details see [8, 5].

3.3. Connected Newton leaves

For the practical application of these ideas it would be nice to characterize those F for which all k–Newton leaves for a certain k are connected. Some experience with Newton trajectories can convince one, that this is just about never the case.

If F ∈ M(IR^{n}), k > 0 and there are no extraneous singularities one can show, that all k–Newton leaves for F are connected iff condition C_{k}(IR^{n}) is satisfied and for n = 2 one obtains the following disappointing result:

THEOREM 7. Suppose F ∈ M(IR^{2}) has at least 3 zeros and there are no extraneous singularities. Then there is a Newton trajectory T for F such that not all zeros are on one component of T . ◇

It is an open problem whether a similar result can be proven for higher dimensions. I suppose so.

We now consider the question under which conditions there exist connected Newton leaves. Applying a global implicit function theorem from [7] one obtains:

THEOREM 8. Let F_{V} (F, IR^{n}) be a k-Newton leaf for F and let A_{V} be a matrix associated with V. If the (n − k) × (n − k)–matrix

A_{V} · (DF (x))(DF (x))^{t} · A_{V}^{t}

is uniformly positive definite on IR^{n}, then the Newton leaf F_{V} (F, IR^{n}) is connected. ◇

The condition in this theorem is rather strong but still applicable in a number of cases. If, for instance, some partial derivative ∂F_{i}/∂x_{j} can be uniformly bounded away from zero on all of IR^{n}, then the (n − 1)-Newton leaf F_{V} (F, IR^{n}) for V = ⟨e_{i}⟩ is connected and the search for the zeros of F can be restricted to the connected (n − 1)–manifold F_{V} (F, IR^{n}) in IR^{n}. More generally, the above theorem can be applied to the gradient function of f : IR^{n} → IR and if f is uniformly convex in k variables we obtain a connected (n − k)–leaf.

Similar results can be obtained by applying other global implicit function theorems to the map A_{V} F (x). The next theorem shows how one can get global implicit function theorems from global inverse function theorems such as the ones contained in [27, 26].

THEOREM 9. Suppose F : D ⊂ IR^{n} → IR^{k}, k < n and suppose there exists a map G : D → IR^{n−k} such that H := (F, G) : IR^{n} → IR^{n} is a global homeomorphism. Let x_{0} ∈ D. Then F^{−1}F (x_{0}) is connected if and only if H(D) ∩ {F (x_{0})} × IR^{n−k} is connected. ◇

For instance, F ∈ C^{1}(IR^{n}, IR^{n}) is a C^{1}-diffeomorphism onto IR^{n} iff DF (x) is nonsingular for all x ∈ IR^{n} and ∥x∥ → ∞ implies ∥F (x)∥ → ∞. Applying theorem 9 one gets:

THEOREM 10. Let k ≤ n and F ∈ C^{1}(IR^{n}, IR^{k}). Let J be a k-element subset of {1,…, n}. Let D_{J}F (x) denote the matrix containing only those colums from DF (x) that belong to indices from J and for x ∈ IR^{n} let x_{J} be correspondingly defined. Then:

If D_{J}F (x) is nonsingular for all x ∈ IR^{n} and if for all sequences {x^{ν}} in IR^{n} with ∥x_{J}^{ν}∥ → ∞ we have ∥F (x^{ν})∥ → ∞, then F^{−1}(y) is a connected (n − k)-dimensional C^{1}-manifold in IR^{n}. ◇

In general, however, the conditions for the existence of connected Newton leaves derived from versions of global implicit function theorems are far too strong. In one form or the other one has to verify further conditions besides the rank condition rankA_{V} DF (x) = dim V for all x. But in the case of Newton trajectories, this rank condition alone is already too strong. Other techniques must be developed.

4. Connecting trajectory components

As we have seen above (Newton trajectories and, more general, trajectories arising from the application of the ideas stated at the end of the introduction), it is easy to define implicitly a set K of curves in B such that we know a priori that all critical points of f : B → IR are on certain curves K_{i} ∈ K. So in principle we could find all critical points of f by numerically tracing these curves K_{i} ⊂ K. The difficulty arises from the fact that in general K consists of several curves K_{i} which do not intersect. Thus to actually trace the K_{i} numerically, we need a starting point on each K_{i}. This, however, is again a global problem which in general might not be easier that the original one. In this section we want to describe a general idea on how different components of curves generated by trajectory methods can be connected by further trajectories. Details are contained in [6] and an application of these ideas to Newton trajectories as well as a discussion of a numerical implementation can be found in [10].

Suppose f : M → IR is a smooth function on a smooth compact manifold M, possibly with boundary ∂M. As is well known from differential topology, the topological nature of the contours f^{−1}(y), y ∈ IR may change only at critical levels, i.e. if f^{−1}(y) contains a critical point of f. There is a simple way to describe the information about the varying number of connected components of the contours by a certain quotient space. To obtain such a space we refine the usual equivalence relation on M for points with identical images and define two points to be equivalent, iff they have the same image under f and are in the same connected component of a contour.

DEFINITION 5. Let X be a topological space, Y a set and f : X → Y a mapping. For any point x ∈ X we call the connected component of f^{−1}(f(x)) that contains x the f–contour in x and denote it by C_{x}(f). Furthermore we define an equivalence relation R_{f} ⊂ X × X by (x, y) ∈ IR_{f} ⇔ C_{x}(f) = C_{y}(f). We call the quotient space X/R_{f} the contour space of f and denote it by X_{f}. The canonical projection from X onto X_{f} is denoted by π_{f}. ◇

Note that in case X := M and Y := IR the contour space can be visualized as a tree embedded in IR^{2} whose vertices (nodes) are the critical points of f and the minima and maxima of f are leaves of this tree. Now f can be split into π_{f} : M → M_{f} and a map f̂: M_{f} → IR such that f = f̂∘ π_{f} and f̂^{−1} describes the number of contour-components.

Suppose now that we have implicitly defined a set K of curves K_{i} in M such that every f-contour has a nonempty intersection with at least one curve K_{i}. Then the following theorem is the basis for more involved results. It shows that the curves K_{i} can be connected by adding certain f-contours:

THEOREM 11. Let X be a connected topological space and let R be an equivalence relation on X such that all equivalence classes are connected. Denote by π : X → X/R the canonical projection onto the quotient space. Let K be the union of finitely many closed connected subsets K_{i} of X. Suppose that all sets π(K_{i}) are closed in X/R and that π(K) = π(X). Define Z := K ∪ S where S denotes the union of the sets S_{i} := π^{−1}(∂π(K_{i})).

Then for every connected component T of Z we have π(T) = π(X). ◇

Thus the (possibly disconnected) set K (a union of curves, say) can be enriched by adding certain f–contours such that any connected component of the resulting set Z intersects every f-contour (and so contains every nondegenerate maximum or minimum of f). Note that Z must not be connected if f has only degenerate minima and maxima. The obvious points of interest are characterized by:

DEFINITION 6. Let X be a topological space, A ⊂ X, Y a set, f : X → Y and x ∈ X. Then we say that f touches A (globally) in x iff x ∈ π_{f}^{−1}(∂π_{f}(A)) ∩ ∂A and f touches f locally in x if every neighbourhood V of x contains a neighbourhood U of x such that f|_{U} touches A ∩ U. ◇

Touching points can also be characterized in a more geometric way: A point x ∈ ∂A is a (global) touching point iff C_{A}(f) := ⋃_{x∈A} C_{x}(f) is not a neighbourhood of the f-contour at x. Globality and locality of touching points in general are independent properties, i.e. a point x can be a local but not a global touching point or a global but not a local one or a local as well as a global touching point. See [6] for examples.

If f : M → IR is smooth then the property of x beeing a local toching point of a curve can be checked numerically by a local transversality condition. The property of beeing a global touching point however is a global condition which in general cannot be verified by local considerations. Now theorem 11 can be applied to continuous maps between topological spaces as follows:

THEOREM 12. Let f : X → Y be a continuous map between topological spaces X and Y. Let K be a union of finitely many closed connected subsets K_{i} of X. Suppose the sets π_{f}(K_{i}) are closed in the contour space X_{f} of f and every f– contour has a nonempty intersection with K. Let T be a connected component of

Z := K ∪ ⋃_{x∈Γ} C_{x}(f),

where Γ is any subset of X containing all global touching points of f with K. Then any f–contour has nonempty intersection with T. ◇

The condition that π_{f}(K_{i}) is closed in X_{f} cannot easily be enforced by imposing restrictions on X and f. However π_{f} is closed if X is compact and X_{f} is a Hausdorff space and these conditions can often be verified directly.

In applying these results to a map f : M → IR several difficulties remain: First, how are the global touching points to be found? Second, the sets adjoined to K are f–contours, so they are generally of dimensionsion n − 1 and might have a acomplicated geometric structure. How can the intersection points of these sets with the curves K_{i} (these are the possible starting points for tracing the curves K_{i}) be found? If might be inconvienient to solve equality-constraint global optimization problems on these surfaces in order to find the intersection points with the curves K_{i}.

For one special case, namely that K is a Newton trajectory, we now outline how these difficulties can be resolved. Suppose B ⊂ IR^{n} is compact, convex and has interior points. Suppose further that f is constant on the boundary ∂B of B. Let g : B ⊂ IR^{n} → IR be a linear function of full rank and let V^{⊥} be the kernel of g. Let F := ∇f : B → IR^{n} denote the gradient of f. In this case the contour space of B with respect to g is homeomorphic to a closed real interval and since B is compact and the connected components of the Newton trajectory K := F_{V} (F, B) are closed, it follows that the sets π_{g}(K_{i}) are closed, where the K_{i} denote the trajectory components of K. It follows from the construction of F_{V} (F, B) and from the assumptions on B and f that the set K ∩ C_{g}(x) is nonempty for all x ∈ B. Thus we can connect the components of F_{V} (F, B) by adjoining appropriately choosen g–contours. But these g-contours are intersections of linear hyperplanes in IR^{n} with the compact and convex set B. So they are easily handled numerically.

Let us assume that K has only finitely many connected components. Which gcontours have to be added? First observe that with our choice of g and the convex set B every global touching point of K with g is also a local touching point and thus can be detected by local computations. Second, since K has only finitely many components and the contour space of g is a real interval it follows that the image W of global touching points of K with g under π_{g} is finite. Thus there is a finite subset Γ′ of the set of global touching points such that π_{g}(Γ′) = π_{g}(W). Now let Γ be a finite nonempty subset of B with π_{g}(Γ) = π_{g}(W) and define

Z := K ∪ ⋃_{x∈Γ} C_{x}(g).

Observing that Γ ≠ ∅ and applying theorem 12 we obtain that Z is connected.

For n = 2 we are done, because then Z is already 1-dimesional and connected. For n > 2 we continue recursively as follows:

The sets S_{x} := C_{x}(g) are intersections of n−1–dimensional hyperplanes with the convex compact set B. We do not really need these sets but just there intersections with K. Now it turns out that these intersection points in S_{x} ∩ K are critical points for the restricted function f|_{S_{x}}. So we have a problem of the same type as before: Determine the critical points of f|_{S_{x}} on the compact, convex set S_{x} where f|_{S_{x}} is constant on the boundary. But this problem is now posed on the (n−1)–dimensional compact and convex set B_{x}. We may attack it by the same techniques as the one on B setting up a Newton trajectory for f|_{S_{x}} and so on. We obtain one such problem for every x ∈ Γ. This construction is repeated until the dimension has dropped down to 2 and results in a 1-dimensional connected set Ω which contains all critical points of f (c.f. [6] for details).

However, that Ω is 1–dimensional and connected does not mean that Ω can be traced numerically by an algorithm that uses only local information. This would violate the indentation argument stated in the introduction. Closer inspection reveals that, although Ω is entirely defined by local means, a local algorithm will not recognize a point in, say the intersection of S_{x} and K unless it has found x ∈ Γ before. Thus, although Ω is connected, it contains one-way-streets which can be traced by a numerical algorithm using only local information in only one direction. Which critical points of f can be reached starting from certain other ones can be described by a weakly connected digraph and all critical points are reached from any single critical starting point only if this digraph is strongly connected.

The paper [10] describes a numerical implementation and states some experimental results with a method based on these ideas for some nonlinear problems with up to 16 variables. Numerous critical points were found in each case. Concerning reliability and speed this method compares favorably with other methods.

5. Final remarks

In this paper we have described some of the most promising ideas and current developments concerning the application of trajectory methods to problems of global optimization. We have only dealt with unconstraint problems but some of the methods described can also be modified to incorporate equality constraints. For inequality constraints some results are available in the context of parametric optimization. Methods for following curves of local minimizers or generalized critical points are described in [15] where lots of further references to the application of trajectory methods to parametric and multiobjective optimization problems can be found. Techniques from parametric optimization are also employed in [31] where a trajectory method is constructed for functions which are convex with respect to some variables.

Most reseachers are sceptical that trajectory methods which do not comprise some stochastic elements will ever lead to a general all-purpose method for global optimization since in contrast to some stochastic methods they offer no asymptotic guarantee that eventually all critical points (or zeros) or even the global minimizers will be found. However, any trajectory method might be modified such as to include stochastic elements like random choices of initial data. In this case a trajectory method can be viewed as a device to greatly enlarge the regions of attraction such that fewer sampling points are needed.

But even if no or only few stochastic elements are employed deterministic trajectory methods offer some attractive possibilities. So the computational efford to numerically follow the trajectories apparently increases only polynomially with the dimension n of the problem. Of course this bound a priori holds only for each step in a discretized succesion of points on a trajectory. If a path approaches a space-filling curve the complexity might still grow exponentially in n. However, such behavior has never been observed for the common trajectory methods and results on the maximal length of a trajectory should be obtainable in the future.

Furthermore some trajectory methods can easily be adapted to utilize special features of the objective function (like convexity in some variables or sum of convex function and small pertubation, as we have seen). So, if some knowledge on the special structure of a problem is available, a hand-tailored trajectory method might be the method of choice.

Trajectory methods based on differential equations of first order are generally not very useful for problems of type (p), if very many local minima are present. On the other hand, they can often be successfully applied if f has only few local solutions and especially if the global minimizers have very small regions of attraction with respect to a local method. Similarly, such trajectory methods do a good job in resolving clusters of neighboring solutions.

For problems of type (P) where several or all zeros of a map F have to be found, trajectory methods or, more generally, path-following methods are the methods of choice. For this common type of problems they are apparently not challenged by stochastic competitors; at least as far as the author knows. Here, apart from homotopy methods, Newton like methods do quite well. And, last but not least, such methods lead to interesting and beautiful mathematics with connections to many fields of pure and applied mathematics.

References

1. E.L. Allgower and K. Georg. Predictor–corrector and simplicial methods for approximating fixed points and zero points of nonlinear mappings. In A. Bachem, M. Grötschel, and B. Korte, editors, Mathematical Programming, pages 15–56. Springer Verlag, 1983.

2. F. Aluffi-Pentini, V. Parisi, and F. Zirilli. A global optimization algorithm using stochastic differential equations. MRC Technical Summary Report (2719), Mathematics Research Center, Madison, Wisconsin, 1985.

3. V. Ts. Banchev. On a continuous analogue of Newton’s method for the solution of non-linear systems of equations. C. R. Acad. Bulg. Sci., 33:1329–1331, 1980. (in Russian).

4. F.H. Branin. A widely convergent method for finding multiple solutions of simultaneous nonlinear equations. I.B.M Journal of Research and Development, 16:504–522, 1972.

5. I. Diener. Global aspects of the continuous Newton method. (In preparation).

6. I. Diener. Trajectory nets connecting all critical points of a smooth function. Mathematical Programming, 36:340–352, 1986.

7. I. Diener. On the global convergence of path-following methods to determine all solutions to a system of nonlinear equations. Mathematical Programming, 39:181–188, 1987.

8. I. Diener. Globale Aspekte des kontinuierlichen Newton–Verfahrens. Habilitationsschrift, Göttingen, October 1991.

9. I. Diener. Newton leaves and the continuous newton method. In E. Deutsch, B. Brosowski, and J. Guddat, editors, Parametric Optimization and Related Topics III. Peter Lang Verlag, Frankfurt a.M., 1993.

10. I. Diener and R. Schaback. An extended continuous Newton method. Journal of Optimization Theory and Apllications, 67(1):57–77, October 1990.

11. C.B. Garcia and F.J. Gould. Relations between several path following algorithms and local and global Newton methods. SIAM Review, 22(3):263–274, July 1980.

12. J. Gomulka. Remarks on Branin’s method for solving nonlinear equations. In L.C.W. Dixon and G.P. Szegö, editors, Towards Global Optimisation, volume 1. North–Holland, Amsterdam, 1975.

13. J. Gomulka. Two implementations of Branin’s method: Numerical experience. In L.C.W. Dixon and G.P. Szegö, editors, Towards Global Optimisation, volume 2. North–Holland, Amsterdam, 1978.

14. A.O. Griewank. Generalized descent for global optimization. Journal of Optimization Theory and Applicalions, 34:11–39, 1981.

15. J. Guddat, Guerra Vazquez F., and Jongen H. Th. Parametric Optimization: Singulatities, Pathfollowing and Jumps. John Wiley and B.G. Teubner, 1990.

16. J.W. Hardy. An implemented extension of Branin’s method. In L.C.W. Dixon and G.P. Szegö, editors, Towards Global Optimisation, volume 1. North–Holland, Amsterdam, 1975.

17. M.W. Hirsch and S. Smale. On algorithms for solving f(x) = 0. Communications on Pure and Applied Mathematics, XXXII, 1979.

18. S. Incerti, V. Parisi, and F. Zirilli. A new method for solving nonlinear simultaneous equations. SIAM Journal of Numerical Analysis, 16:779–789, 1979.

19. S. Inomata and M. Cumada. On the Golf Method. Bulletin of the Electrotechnical Laboratory, 25:495–512, 1964. Denshi Gijutso Sogo Kenkyujo, Tokyo, Japan.

20. H.Th. Jongen, P. Jonker, and F. Twilt. On Newton flows in optimization. Methods of Operations Research, 31:345–359, 1979.

21. H.Th. Jongen, P. Jonker, and F. Twilt. The continuous Newton-method for meromorphic functions. In R. Martini, editor, Geometric Approaches to Differential Equations. Lecture Notes in Mathematics, Vol. 810, pages 181–239. Springer Verlag, 1980.

22. H.Th. Jongen, P. Jonker, and F. Twilt. Nonlinear Optimization in IR^{n}, volume I of Methoden und Verfahren der mathematischen Physik, Bd 29. Peter Lang Verlag, Frankfurt a.M., 1983.

23. H.Th. Jongen, P. Jonker, and F. Twilt. Nonlinear Optimization in IR^{n}, volume II of Methoden und Verfahren der mathematischen Physik, Bd 32. Peter Lang Verlag, Frankfurt a.M., 1986.

24. H.Th. Jongen, P. Jonker, and F. Twilt. A note on Branin’s method for finding the critical points of smooth functions. In Parametric Optimization and Related Topics, pages 209–228, 1987. Int. Conf., Plaue/GDR, 1985.

25. H.B. Keller. Global homotopies and Newton methods. In C. de Boor and G.H. Golub, editors, Recent Advances in Numerical Analysis. Academic Press, 1978.

26. J.M. Ortega and W.C. Rheinboldt. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York and London, 1970.

27. R.S. Palais. Natural operations of differential forms. Transactions of the AMS, 92:125–141, July 1959.

28. S. Smale. A convergent process of price adjustment and global Newton methods. Journal of Mathematical Economics, 3:107–120, 1976.

29. J.A. Snyman. A new dynamic method for unconstrained minimization. Applied Mathematical Modelling, 6:449–462, 1982.

30. J.A. Snyman and L.P. Fatti. A multi-start global minimization algorithm with dynamic search trajectories. Journal of Optimization Theory and Applications, 54(1):121–141, July 1987.

31. E.G. Sturua and S.K. Zavriev. A trajectory algorithm based on the gradient method I. The search on the quasioptimal trajectories. Journal of Global Optimization, 1(4):375–388, 1991.

32. G. Treccani. A new strategy for global optimization. In L.C.W. Dixon and G.P. Szegö, editors, Towards Global Optimisation. North–Holland, Amsterdam, 1975.

33. F. Twilt. Newton-flows for meromorphic functions. PhD thesis, Twente University of Technology, The Netherlands, 1981.

34. H. Yamashita. A continuous path method of optimization and its application to global optimization. In A. Prekopta, editor, Survey of Mathematical Programming 1, pages 539–546. Budapest, 1979.

35. N.P. Zidkov and B.M. Siedrin. A certain method of search for the minumum of a function of several variables. Computing Methods and Programming, 10:203–210, 1968. Izdat Moscow University.