Newton Leaves and the Continuous Newton Method

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

Abstract. Aspects of the continuous Newton method in IR^{n} are discussed from a viewpoint of global optimization. Using an algebraic instead of an analytic definition of Newton trajectories we generalize the usual concept to certain higher dimensional sets (Newton leaves). The study of these sets reveals insight into the topological and geometrical structure of Newton trajectories and is also directly relevant for numerical methods of global optimization.

Key words. Global optimization, continuous Newton method, trajectory method.

1 Introduction

This paper discusses the concept of Newton leaves first defined in [5]. Here the general idea and some results are presented. Details and proofs can be found in [5] and the forthcoming paper [6].

We consider the following problem: Given a smooth map F : B ⊂ IR^{n} → IR^{n}, determine the set Zero(F, B) of all zeros of F in B. The classical Newton method with stepsize control finds one zero if a good enough local approximation is given as a starting point. This method can be viewed as an Euler method for integrating the Newton differential equation (NDE)

\frac{dx}{dt} = −DF (x)^{−1}F (x).

Writing this equation in the form

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

one can see that on the solution trajectories the relation

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

holds. Thus the direction of F stays constant on the solution trajectories and if the NDE can be integrated until t = ∞ a zero of F is reached.

However, the right hand side of the NDE is not defined on all of IR^{n} and so one usually considers a desingularized version (dNDE) of this equation, namely:

dx/dt = −D̃F(x)F (x),

where Ã denotes the adjoint matrix of A.

Thus the phase portraits of the equations NDE and dNDE are the same (up to orientation) where both are defined. Linearization of dNDE in a zero of F shows that the nondegenerate zeros of F are attractors or repellors for the trajectories. Now the right hand side of the equation dNDE is defined on the whole space and vanishes in the zeros of F. However, additional singularities might occur in points where F (x) ≠ 0 but still D̃F(x)F (x) = 0. Such points were called extraneous singularities in [1]. The structure of such extraneous singularities has been studied in several papers by Jongen, Jonker and Twilt (see [11] and references therein).

In [1] Branin suggested not to stop at a zero of F but to project the last step across the zero, reverse the sign on the right hand side of dNDE and to continue integration, possibly finding further zeros of F. He conjectured that in the absence of extraneous singularities one could find all zeros of F by this method. This is now known to be false. Branin was succesful with his method in several cases and his paper initiated an intensive study of this method during the mid seventies. However, no definite convergence results could be obtained and research in this area declined until, at the beginning of the eighties, Jongen, Jonker and Twilt thoroughly studied the complex case and obtained some nice results (see for instance [10, 12]). Still, the general question when Branin’s method determines all zeros of a function F remained unsolved.

In [3] an algebraic definition for Newton trajectories was given (for a similar, but more restrictive view see [8]) 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 [3] was a first step towards an algebraic instead of an analytic treatment of Newton trajectories. This idea was extended in [5] and an outline of the general idea and the results obtained in this work shall be presented now.

2 Newton leaves

For the rest of this paper let B ⊂ IR^{n} be nonempty and n ≥ 2. 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 any 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 we need Sard’s theorem. By G(k, n) we denote the Grassman manifold of k-codimensional subspaces in IR^{n}.

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

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

a k-Newton leaf for F (or a k–NL, for short). A 1–leaf is also called a Newton trajectory. ◇

Sometimes we just write F_{V} (F) instead of F_{V} (F, B) if it is clear which B is meant. 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. The connection between these Newton trajectories and the solution trajectories to the desingularized Newton differential equation dNDE is obvious: The direction of F stays constant on a Newton trajectory. There is also a connection with certain homotopy methods which can be stated as follows (for the case k = 1 see [7]):

Let F : IR^{n} → IR^{n} and V a k–codimensional linear subspace of IR^{n}. Let v_{1},…, v_{k} be a Basis for V^{⊥}. Then we define a map G : IR^{n} × IR^{k} → IR^{n} by:

(x, λ) ↦ F (x) + ∑_{i=1}^{k} λ_{i}v_{i}.

Let π : IR^{n} × IR^{k} → IR^{n} be the projection onto the first n components. Then obviously F_{V} (F) = π(G^{−1}(0)).

The following observations are elementary.

(i) If V, W are linear subspaces in IR^{n} and V ⊂ W, then W^{⊥} ⊂ V^{⊥} and thus F_{W} (F, B) ⊂ F_{V} (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 (V + W)^{⊥} = V^{⊥} ∩ W^{⊥} and thus F_{V +W} (F, B) = F_{V} (F, B) ∩ F_{W} (F, B).

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 on these sets. For, if a Newton trajectory is locally one-dimensional and connected, then one could determine all zeros of F by numerically tracing the trajectory.

A Newton trajectory beeing locally one-dimensional is no serious practical restriction; under slight regularity conditions on F “nearly all” Newton trajectories are one-dimensional differentiable manifolds. The real practical problem is that Newton trajectories may (and will) in general be disconnected. A numerical path following method would need a starting point on each component. (A general strategy for connecting different components has been suggested in [2] and [4] describes a numerical implementation of this strategy.)

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 also has direct practical implications.

We collect some facts about Newton leaves to aid our imagination. The proofs of these statements are easy and straight forward.

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

(i) F_{V} (F, B) can be represented as intersection F_{V} (F, B) = F_{U}(F, B) ∩ F_{W} (F, B) of an l–leaf F_{U}(F, B) and an m–leaf F_{W} (F, B) iff l, m ≥ k and l + m − k ≤ n. 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} (F, B) there is an l–Newton leaf F_{W} (F, B) such that y ∈ F_{W} (F, B) and F_{V} (F, B) ∩ F_{W} (F, B) = Zero(F, B).

(iii) If an l–leaf F_{W} (F, B) intersects F_{V} (F, B) in a point y ∈ B\Zero(F, B),

then

n − k − l + 1 ≤ dim(V ∩ W) ≤ min(n − k, n − l).

Thus, if F_{W} (F, B) is a Newton trajectory intersecting F_{V} (F, B) in a point y ∉ Zero(F, B), then F_{W} (F, B) is contained in F_{V} (F, B).

(iv) For all l mit 1 ≤ l ≤ k we have:

F_{V} (F, B) = ⋃_{\begin{matrix}W ⊃V \\ W ∈G(l,n) \end{matrix}} F_{W} (F, B).

Thus F_{V} (F, B) 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}.)

3 Extraneous singularities

We now want to derive a different characterization of Newton leaves that often is easier to work with. We would like to represent a Newton leaf F_{V} (F, B) 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–codimensional linear subspace in IR^{n} and F ∈ M^{∗}(B). Let A_{V} be an (n − k) × n– 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 the kernel of A_{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). We denote the set of such points by ExS_{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) ◇

Since the rank of a differentiable map is lower semicontinuous the sets ExS_{V} (F, B) and ExS(F, B) are closed in B. The extraneous singularities of Newton leaves can be characterized as follows:

LEMMA 1. Let F ∈ M^{∗}(B) and V ∈ G(k, n). Let v_{1},…, v_{k} be a basis for V^{⊥}. Then x ∈ F_{V} (F, B) is an extraneous singularity of F_{V} (F, B) iff the rank of the matrix DF (x) to which columns v_{1},…, v_{k} have been added is less than n, that is

rank[DF (x), v_{1},…, v_{k}] < n,

or, equivalently

ker D^{⊤}F (x) ∩ V ≠ {0}.
◇

From this one easily gets

THEOREM 1. Let F ∈ M^{∗}(B) and let x be an extraneous singularity of a k-Newton leaf F_{V} (F, B). Then

(i) If F_{W} (F, B) is a Newton leaf contained in F_{V} (F, B) and if x ∈ F_{W} (F, B), then x is also an extraneous singularity of F_{W} (F, B).

(ii) 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). Moreover W can be choosen such that l = k + dim(ker D^{⊤}F (x) ∩ V).

◇

These results can be used to study the geometry of Newton leaves near extraneous singularities (see [5, 6]). The structure of ExS(F, IR^{n}) has been extensively studied by Jongen, Jonker and Twilt in several papers (see [11] for an overview and further references). Especially there is a generic subset E of C^{∞}(IR^{n}, R^{n}) such that ExS(F, IR^{n}) is a closed stratified subset in IR^{n} of dimension ≤ n − 2.

4 Geometry of Newton leaves

Generally, in the points of ExS_{V} (F, B) a Newton leaf F_{V} (F, B) will locally not be a differentiable manifold. Bifurcations and isolated points may occur. It follows from the above discussion that k-Newton leaves for 0 ≤ k < n − 1 can be represented as intersections of higher dimensional Newton leaves. Generically extraneous singularities can be seen as points where some of these higher dimensional leaves have contact of order ≥ 2.

This is made more precise by the following observation. If x ∉ ExS(F) then F_{V} (F) locally is a manifold and the tangent space in x (shifted to the origin) is ker A_{V} DF (x). Call two sets A, B oblique if neither A ⊂ B nor B ⊂ A. Then we have:

THEOREM 2. Let F_{V} (F), F_{W} (F) be two Newton leaves, oblique to each other. Then the tangent spaces of F_{V} (F) and F_{W} (F) are oblique to each other in any point x ∈ F_{V} (F) ∩ F_{W} (F) which does not belong to ExS_{V +W} (F). ◇

Especially, distinct Newton leaves intersect obliquely 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(x^{∗}) such that any connected component of a Newton leaf intersecting U(x^{∗}) must also contain x^{∗}. Thus, if a Newton leaf approaches a nondegenerate zero x^{∗} closely enough, it must run through x^{∗}.

We 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. Then we have:

THEOREM 3. Let F ∈ M^{∗}(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 proof follows from remark 1,(iii). The tangent vectors are given by the tangent vectors for the Newton trajectories on C.

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 4. 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 no assumptions on the extraneous singularities on the Newton leaves have been made.

THEOREM 5. 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. ◇

From this and the Brower fixed point theorem one gets

COROLLARY 6. Let F ∈ M^{∗}(IR^{2}) and ExS(F, IR^{2}) = ∅. Then every compact component of a Newton trajectory contains at least two zeros. ◇

It is an open question whether this theorem can be generalized to IR^{n} and k-Newton leaves. Can there exist, for instance, a free 2-leaf F_{V} (F) in IR^{3} which is homeomorphic to the torus S^{1} ×S^{1} if we demand ExS(F, IR^{3}) = ∅? Is that possible even if F is a gradient of some function f? It is no problem to construct a free 2-leaf homeomorphic to a torus. The problem lies in avoiding extraneous singularities.

With respect to the actual application of Newton leaves for the determination of all zeros of F, free components are something we do not want. 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.

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.

5 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 k-leaves 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 [9]. 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 the next

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 the first result on the connectedness of Γ^{k}(F, B):

THEOREM 7. 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. ◇

If condition C_{k} is not satisfied one can in some cases apply the following result:

THEOREM 8. If B ⊂ IR^{n} is open (!) and connected, F ∈ M^{∗}(B),k > 0, no unbounded component of a k-NL contains an extraneaous singularity of F and no component of any k–NL for F is free, then Γ^{k}(F, B) is connected. ◇

The condition that B be open cannot be dropped in this case because otherwise some connecting components of Newton leaves could be blocked by a suitable structure of B.

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 9. 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. ◇

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

THEOREM 10. 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 [5, 6].

6 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–NL for F are connected iff condition C_{k}(IR^{n}) is satisfied and for n = 2 one obtains the following disappointing result:

THEOREM 11. 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 [3] one obtains:

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

A · (DF (x))(DF (x))^{t} · A^{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)-NL 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}.

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 [14, 13].

THEOREM 13. 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. ◇

REMARK 2. In the application of this theorem the following question arises: Given a differentiable map F : IR^{n} → IR^{k} of rank k. Under which conditions can F be extended by a map G : IR^{n} → IR^{n−k} such that (F, G) : IR^{n} → IR^{n} is of rank n? ◇

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 13 one gets:

THEOREM 14. 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.

One can give simple examples in IR^{2} which show that even if Γ^{1}(F, IR^{2}) is a complete graph it is possible that no Newton trajectory for F is connected. But if certain further conditions are satisfied the structure of the graphs Γ^{k}(F, IR^{2}) can be used to draw conclusions concerning the existence of connected Newton leaves. So, for instance, one can prove:

THEOREM 15. Let B ⊂ IR^{n} be closed, F ∈ M^{∗}(B) and suppose no more than one component of any Newton trajectory for F intersects ∂B. Suppose F hat exactly 3 zeros in B and Γ^{1}(F, B) is connected. Then there is a component of a Newton trajectory for F which contains all three zeros. ◇

7 Generalizations

As we have seen, k-Newton leaves F_{V} (F) live on certain l-Newton leaves F_{W} (F) for l > k. It is therefore quite natural to ask whether F_{V} (F) for F : IR^{n} → IR^{n} can be considered as a k-leaf for a function F̂ : F_{W} (F) → W^{⊥} ≅ IR^{l}. Or, more general, how can one define Newton leaves for functions F : M^{n} → IR^{n} on an n-dimensional manifold M^{n}? Our definition of Newton leaves carries over to this case in a straight forward way.

If f : IR^{n} → IR, the critical points of f lie on Newton leaves F_{V} (∇f). However it is more difficult to generalize the concept of Newton leaves to functions f : M^{n} → IR on n-manifolds. There are several possibilities and it is not clear yet which definition is “right”.

Recall that F_{V} (F) = F^{−1}(V^{⊥}). Instead of elements V^{⊥} from the Grassman manifold G(k, n) one could also take other subsets of IR^{n} and consider their pre-images. If a collection of such subsets provides a “foliation” of IR^{n} similar to the one provided by the linear subspaces, then large parts of the theory carry over. Consider, for instance, a second map G : IR^{n} → IR^{n}. Then (G ∘ F)^{−1}(V^{⊥}) = F^{−1}(G^{−1}(V^{⊥})) = F^{−1}(F_{V} (G)). This means that the Newton leaves for G ∘ F are the pre-images of the Newton leaves for G under F.

Hopefully this concise overview has convinced the reader that Newton leaves are interesting mathematical objects with connections to algebraic and differential topology as well as numerical analysis and global optimization.

References

[1] F.H. Branin. A widely convergent method for finding multiple solutions of simultaneous nonlinear equations. I.B.M Journal of Research and Development, (1972) 504–522.

[2] I. Diener. Trajectory nets connecting all critical points of a smooth function. Mathematical Programming, 36 (1986) 340–352.

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

[4] I. Diener and R. Schaback. An extended continuous Newton method. Journal of Optimization Theory and Applications, Vol. 67, Nr. 1 (1990) 57–77.

[5] I. Diener. Globale Aspekte des kontinuierlichen Newton–Verfahrens. Habilitationsschrift, Göttingen, 1991.

[6] I. Diener. Global Aspects of the Continuous Newton Method. In preparation.

[7] C.B. Garcia and F.J. Gould. Relations between several path following algorithms and local and global Newton methods. SIAM Review, Vol. 22, Nr. 3 (1980) 263–274.

[8] M.W. Hirsch and S. Smale. On algorithms for solving f(x) = 0. Communications on Pure and Applied Mathematics, XXXII, (1979) 281– 312.

[9] H.Th. Jongen, P. Jonker, and F. Twilt. On Newton flows in optimization. Methods of Operations Research, 31 (1979) 345–359.

[10] H.Th. Jongen, P. Jonker, and F. Twilt. The continuous Newtonmethod for meromorphic functions. In R. Martini, (ed), Geometric Approaches to Differential Equations. Lecture Notes in Mathematics, Vol. 810, Seiten 181–239. Springer Verlag, 1980.

[11] H.Th. Jongen, P. Jonker, and F. Twilt. Nonlinear Optimization in IR^{n}, Band II von Methoden und Verfahren der mathematischen Physik, Bd 32. Peter Lang Verlag, Frankfurt a.M., 1983.

[12] H.Th. Jongen, P. Jonker, and F. Twilt. The continuous, desingularized Newton-method for meromorphic functions. Acta Applicandae Mathematicae, 13 (1988) 81–121.

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

[14] R.S. Palais. Natural operations of differential forms. Transactions of the AMS, 92 (1959) 125–141.