# Newton’s method for nonlinear mappings into vector bundles

Laura Weigl & Anton Schiela

###### Abstract

We consider Newton’s method for finding zeros of mappings from a manifold
$\mathcal{X}$ into a vector bundle $\mathcal{E}$. In this setting a connection
on $\mathcal{E}$ is required to render the Newton equation well defined, and a
retraction on $\mathcal{X}$ is needed to compute a Newton update. We discuss
local convergence in terms of suitable differentiability concepts, using a
Banach space variant of a Riemannian distance. We also carry over an affine
covariant damping strategy to our setting. Finally, we discuss two simple
applications of our approach, namely, finding fixed points of vector fields
and stationary points of functionals.

#### Keywords:

Newton’s method, Banach manifolds, vector bundles

#### AMS MSC2020:

53-08, 58C15, 46T05, 49M15

## 1\. Introduction

Newton’s method is a central algorithm for the solution of nonlinear problems,
but also, in its variants, a theoretical tool, e.g., in the proof of the
implicit function theorem [21]. Most of the literature consider Newton’s
method for finding zeros $F(x)=0$ for a differentiable mapping $F:X\to Y$,
where $X$ and $Y$ are linear, normed, not necessarily finite dimensional
spaces, in most cases Banach spaces. In this setting, a Newton step is defined
straightforwardly as the solution $\delta x\in X$ of the linear operator
equation and a simple additive update:

$F^{\prime}(x)\delta x+F(x)=0,\quad x_{+}=x+\delta x.$

Extensions of Newton’s method to problems $F:\mathcal{X}\to Y$, where
$\mathcal{X}$ is a Riemannian manifold and $Y$ still a linear space with the
help of so called retractions $R_{x}:T_{x}\mathcal{X}\to\mathcal{X}$, are
relatively straightforward, replacing the simple update by $x_{+}=R_{x}(\delta
x)$. But also, Newton’s method has been used to find stationary points of
twice differentiable functions $f:\mathcal{X}\to\mathbb{R}$ [1], and finally
to find zeros of vector fields $v\in\Gamma(\mathcal{X})$ on $\mathcal{X}$ [2,
6]. However, much richer classes of problems are conceivable in a manifold
setting, such as constrained optimization [3, 15, 22, 23], non-symmetric
variational problems, problems of stationary action [16], or other saddle
point problems, to name just a few.

Given this variety of settings, the following questions arise: What is an
appropriate general mathematical framework for Newton’s method for mappings
between nonlinear spaces? What structure is actually needed to define, but
also to implement and globalize Newton’s method for such problems? It is the
aim of this work to explore possible answers to these questions.

Specifically, we want to establish Newton’s method for a mapping
$F:\mathcal{X}\to\mathcal{E}$, where $\mathcal{X}$ is a differentiable
manifold and $p:\mathcal{E}\to\mathcal{M}$ is a _vector bundle_ with fibres
$E_{y}$, $y\in\mathcal{M}$. This formulation still allows the search for
zeros, i.e. $F(x)=0_{p(F(x))}\in E_{p(F(x))}$, and it covers many of the above
mentioned settings. The derivative of $F$ is a mapping
$F^{\prime}(x):T_{x}\mathcal{X}\to T_{F(x)}\mathcal{E}$, which means the
Newton equation cannot be formulated in the usual way, since the codomains of
$F$ and $F^{\prime}(x)$, i.e., $\mathcal{E}$ and $T_{F(x)}\mathcal{E}$, do not
coincide. It is thus necessary to introduce some additional geometric
structure. It turns out that we need a _connection_ on $\mathcal{E}$, which
induces for every $e\in\mathcal{E}$ a linear projection
$Q_{e}:T_{e}\mathcal{E}\to E_{p(e)}$ onto the corresponding fibre. This allows
us to formulate the Newton equation in a well defined way:

$Q_{F(x)}\circ F^{\prime}(x)\delta x+F(x)=0_{p(F(x))}.$

If $Q_{F(x)}\circ F^{\prime}(x)$ is invertible, the Newton direction $\delta
x\in T_{x}\mathcal{X}$ can be computed, and thus the Newton step via a
retraction $x_{+}=R_{x}(\delta x)$.

To observe convergence of Newton’s method we need a _metric_
$d:\mathcal{X}\times\mathcal{X}\to\mathbb{R}_{+}$ on $\mathcal{X}$. Since
Newton’s method in the linear setting is not restricted to Hilbert spaces and
has important applications in Banach spaces (cf. e.g. [25] or [7]), we will
introduce metrics similar to, but more general than Riemannian distances.
Finally, to compare images of successive iterates on different fibres, e.g.,
$F(x_{+})$ and $F(x)$, _vector back-transports_ of the form
$V^{-1}_{y}:\mathcal{E}\to E_{y}$ are needed on $\mathcal{E}$ (we call them
back-transports, because they work in the opposite direction than classical
vector transports).

After setting up this framework, we will establish basic local convergence
results, based on minimal assumptions on the smoothness of $F$, using a
geometric version of Newton differentiability. Besides giving a classical
a-priori result, we also establish a theorem, which relates local convergence
to a quantity that is purely defined in terms of the space of iterates
$\mathcal{X}$, and which can be estimated a-posteriori. This opens the door to
define an affine covariant damping strategy in the spirit of Deuflhard [9],
which is based on following the so called Newton path. While carrying over
this strategy from linear spaces to our nonlinear setting, we will observe
that strict differentiability of $F$ is required to make this strategy viable.
In addition, it will turn out that the employed connection and the vector
back-transport have to satisfy a consistency condition to ensure that useful
steps are taken. Finally, we will illustrate our results for the two simplest
applications, namely the search for fixed points of vector fields and
stationary points of functions on $\mathcal{X}$.

## 2\. Preliminaries

We consider a Banach manifold $\mathcal{X}$, i.e. a topological space
$\mathcal{X}$ and a collection of charts $(U,\phi)$, where each chart
$\phi:U\to\mathbb{X}$ maps an open subset $U$ of $\mathcal{X}$
homeomorphically into a real Banach space $\mathbb{X}$ with norm
$\|\cdot\|_{\mathbb{X}}$. Unless otherwise noted we will assume that the
manifold is of class $C^{1}$, which means that the transition mappings, i.e.,
$t_{ji}:=\phi_{j}\circ\phi_{i}^{-1}:\phi_{i}(U_{i}\cap U_{j})\to\mathbb{X}$
for charts $\phi_{i},\phi_{j}$, are local diffeomorphisms and thus, in
particular, locally Lipschitz. Mappings $F:\mathcal{X}\to\mathcal{Y}$ between
two Banach manifolds are called continuous, differentiable, locally Lipschitz,
if their representations in charts, i.e. the composition with charts
$\phi_{\mathcal{Y}}\circ F\circ\phi_{\mathcal{X}}^{-1}$, have the respective
property. It can readily be shown that these properties are independent of the
choice of charts. However, we cannot assign a local Lipschitz constant to a
locally Lipschitz mapping, since this quantity is chart dependent.

For a manifold $\mathcal{X}$ we define tangent spaces by using charts, see,
e.g., [13, II §2]. Let $x\in\mathcal{X}$ and consider the set

$\\{(\phi,v)\;|\;\phi:U\rightarrow\mathbb{X}\text{ chart at }x\in\mathcal{X},\
v\in\mathbb{X}\\}.$

The relation $(\phi_{i},v_{i})\sim(\phi_{j},v_{j})\ :\Leftrightarrow\
t_{ji}^{\prime}(\phi_{i}(x))v_{i}=v_{j}$ defines an equivalence relation. The
corresponding equivalence class is called a tangent vector $v$ of
$\mathcal{X}$ at $x$. The set of these equivalence classes at a point
$x\in\mathcal{X}$ is a vector space, called the tangent space
$T_{x}\mathcal{X}$ of $\mathcal{X}$ at $x$. Every differentiable map
$F:\mathcal{X}\rightarrow\mathcal{M}$ between two $C^{1}$-manifolds
$\mathcal{X}$ and $\mathcal{M}$ induces a linear map
$F^{\prime}(x_{0}):T_{x_{0}}\mathcal{X}\rightarrow T_{F(x_{0})}\mathcal{M}$,
termed tangent map or derivative of $F$ at $x_{0}\in\mathcal{X}$ [13].

#### Vector Bundles.

Consider a _vector bundle_ $p:\mathcal{E}\rightarrow\mathcal{M}$. Its
projection $p$ is a smooth surjective map, which assigns to $e\in\mathcal{E}$
its base point $y=p(e)$ in the base manifold $\mathcal{M}$ [13, III §1]. The
_total space_ $\mathcal{E}$ is a manifold with special structure: for each
$y\in\mathcal{M}$ the preimage $E_{y}:=p^{-1}(y)$ is a Banachable space (i.e.
a complete topological vector space whose topology is induced by some norm,
rendering $E_{y}$ complete), called fibre over $y$. The zero element in
$E_{y}$ is denoted by $0_{y}$. A mapping $v:\mathcal{M}\to\mathcal{E}$, such
that $p(v(y))=y$ for all $y\in\mathcal{M}$ is called section of $\mathcal{E}$.
The set of all sections is denoted by $\Gamma(\mathcal{E})$. The most
prominent example for a vector bundle is the tangent bundle
$\pi:T\mathcal{X}\to\mathcal{X}$ of a manifold $\mathcal{X}$ with fibres
$T_{x}\mathcal{X}$. A section of $T\mathcal{X}$ is called a vector field.

Vector bundles can be described via general local charts, but usually, _local
trivializations_ are used instead, which reflect their structure better. For a
Banach space $(\mathbb{E},\|\cdot\|_{\mathbb{E}})$ and an open set
$U\subset\mathcal{M}$, a local trivialization is a diffeomorphism
$\tau:p^{-1}(U)\to U\times\mathbb{E}$, such that $\tau_{y}:=\tau|_{E_{y}}\in
L(E_{y},\mathbb{E})$ is a linear isomorphism. Thus, any element of
$e\in\mathcal{E}$ can be represented as a pair
$(y,e_{\tau})\in\mathcal{M}\times\mathbb{E}$ with $y=p(e)$ and $e_{\tau}$
depending on the trivialization. For two trivializations $\tau$ and
$\tilde{\tau}$ around $y\in\mathcal{M}$ we can define smooth transition
mappings $A:y\mapsto\tilde{\tau}_{y}\tau_{y}^{-1}$ with $A(y)\in
L(\mathbb{E},\mathbb{E})$, and obtain $e_{\tilde{\tau}}=A(y)e_{\tau}$. If
$\phi:U\to\mathbb{M}$ is a chart of $\mathcal{M}$, then we can construct a
_vector bundle chart_ :

$\displaystyle\Phi_{\mathcal{E}}:p^{-1}(U)$
$\displaystyle\to\mathbb{M}\times\mathbb{E},\quad
e\mapsto(\phi(p(e)),\tau_{p(e)}e),$

which retains the linear structure of the fibres. Vice versa, the second
component of a vector bundle chart yields a local trivialization.

######  Remark 2.1.

For the tangent bundle $\pi:T\mathcal{X}\to\mathcal{X}$ of a manifold
$\mathcal{X}$ we have trivializations and vector bundle charts in the
following natural way:
Let $(U,\phi_{i})$ be a chart of $\mathcal{X}$ at $x$. Then every tangent
vector $v\in T_{x}\mathcal{X}$ has a chart representation
$v_{i}\in\mathbb{X}$, so $\tau_{i}(v):=v_{i}$ is a trivialization. Since
tangent vectors transform by $t_{ji}^{\prime}(\phi_{i}(x))v_{i}=v_{j}$ under
change of charts, the transition mapping is given by
$A(x)=t_{ji}^{\prime}(\phi_{i}(x))$. A vector bundle chart for $T\mathcal{X}$
is then given by:

$\displaystyle\Phi_{T\mathcal{X}}:\pi^{-1}(U)$
$\displaystyle\to\mathbb{X}\times\mathbb{X},\quad(x,v)\mapsto(\phi_{i}(x),v_{i}).$

Similarly, each element $\delta e\in T_{e}\mathcal{E}$ can be represented in
local trivializations as a pair of elements $(\delta y,\delta e_{\tau})\in
T_{y}\mathcal{M}\times\mathbb{E}$, where the tangential part $\delta
y=p^{\prime}(e)\delta e$ is given canonically. The representation $\delta
e_{\tau}$ of the fibre part, however, depends crucially on the chosen
trivialization, and so there is no _natural_ splitting of $\delta e$ into a
tangential part and a fibre part. In fact, if $e_{\tilde{\tau}}=A(y)e_{\tau}$,
then $\delta e_{\tilde{\tau}}=A(y)\delta e_{\tau}+(A^{\prime}(y)\delta
y)e_{\tau}$ by the product rule.

#### Fibrewise linear mappings.

Consider two vector bundles
$p_{1}:\mathcal{E}_{1}\to\mathcal{M}_{1},p_{2}:\mathcal{E}_{2}\to\mathcal{M}_{2}$,
and denote by $L(E_{1,y},E_{2,z})$ the set of continuous linear mappings
$E_{1,y}\to E_{2,z}$ for $y\in\mathcal{M}_{1}$ and $z\in\mathcal{M}_{2}$.
Given a mapping $f:\mathcal{M}_{1}\to\mathcal{M}_{2}$ we denote by
$f^{*}\mathcal{E}_{2}$ the _pullback bundle_ of $\mathcal{E}_{2}$ via $f$,
i.e. $(f^{*}E_{2})_{y}:=E_{2,f(y)}$. Collecting all mappings in
$L(E_{1,y},E_{2,f(y)})$ for all $y\in\mathcal{M}_{1}$ in a set
$\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2})$, we observe that
$p_{\mathcal{L}}:\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2})\to\mathcal{M}_{1}$
is a vector bundle itself with fibres $L(E_{1,y},E_{2,f(y)})$. In
trivializations an element $H$ of
$\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2})$ is represented by a pair
$(y,H_{\tau})$ where $y\in\mathcal{M}_{1}$ and $H_{\tau}\in
L(\mathbb{E}_{1},\mathbb{E}_{2})$.

A _fibrewise linear mapping_ , also called _vector bundle morphism_ , see
e.g., [13, III §1], is a section
$S\in\Gamma(\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2}))$, i.e, a
mapping

$S:\mathcal{M}_{1}\to\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2})\text{
with }p_{\mathcal{L}}\circ S=Id_{\mathcal{M}_{1}}.$

For example, if $F:\mathcal{X}\to\mathcal{M}$ is differentiable, then the
derivative
$S:=F^{\prime}\in\Gamma(\mathcal{L}(T\mathcal{X},F^{*}T\mathcal{M}))$ is a
fibrewise linear mapping, but also vector transports, defined below, are
fibrewise linear mappings. $S$ is called locally bounded, respectively
differentiable, if its representation in local trivializations, i.e.

$S_{\tau}:=\tau_{\mathcal{E}_{2}}\circ S\circ\tau_{\mathcal{E}_{1}}^{-1}$ (1)

has the same property. If $S$ is differentiable, then its derivative is a
section
$S^{\prime}\in\Gamma(T\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2}))$ of
the tangent bundle
$p_{\mathcal{L}}^{\prime}:T\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2})\to
T\mathcal{M}_{1}$, i.e., a mapping

$S^{\prime}:T\mathcal{M}_{1}\to
T\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2}),\text{ such that
}p_{\mathcal{L}}^{\prime}\circ S^{\prime}=Id_{T\mathcal{M}_{1}}.$

From $S\in\Gamma(\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2}))$ we can
construct a mapping ${\langle{S}\rangle}\in
C^{1}(\mathcal{E}_{1},\mathcal{E}_{2})$ as follows:

$\displaystyle{\langle{S}\rangle}:\mathcal{E}_{1}$
$\displaystyle\to\mathcal{E}_{2},\quad
e\mapsto{\langle{S}\rangle}(e):=S(p_{1}(e))e.$

Thus, we obtain a natural inclusion of the sections of the bundle of fibrewise
linear mappings into the $C^{1}$-mappings:

$\varphi:\Gamma(\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2}))\to
C^{1}(\mathcal{E}_{1},\mathcal{E}_{2}),\quad S\mapsto{\langle{S}\rangle}.$

Comparison of
$S^{\prime}\in\Gamma(T\mathcal{L}(\mathcal{E}_{1},f^{*}\mathcal{E}_{2}))$ with
${\langle{S}\rangle}^{\prime}\in\Gamma(\mathcal{L}(T\mathcal{E}_{1},S^{*}T\mathcal{E}_{2}))$
in trivializations yields by the product rule

${\langle{S}\rangle}_{\tau}^{\prime}(e)(\delta y,\delta
e_{\tau})=S_{\tau}(p_{1}(e))\delta e_{\tau}+(S_{\tau}^{\prime}(p_{1}(e))\delta
y)e_{\tau}\quad\forall(\delta y,\delta e_{\tau})\in
T_{p_{1}(e)}\mathcal{M}_{1}\times\mathbb{E}_{1}.$ (2)

#### Vector transports.

Special fibrewise linear mappings, which will later be needed in our
globalization strategy, are the so called _vector transports_.

######  Definition 2.2.

For a vector bundle $p:\mathcal{E}\rightarrow\mathcal{M}$ and
$y\in\mathcal{M}$ we define a _vector transport_ as a section
$V_{y}\in\Gamma(\mathcal{L}(\mathcal{M}\times E_{y},\mathcal{E}))$, i.e.

$V_{y}:\mathcal{M}\to\mathcal{L}(\mathcal{M}\times E_{y},\mathcal{E}),\
\text{with }p_{\mathcal{L}}(V_{y}(\hat{y}))=\hat{y}\;
\forall\hat{y}\in\mathcal{M},$

with the properties that $V_{y}(y)=Id_{E_{y}}$ and $V_{y}(\hat{y})$ is
invertible for all $\hat{y}\in\mathcal{M}$.
We define a _vector back-transport_ as a section
$V_{y}^{-1}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$, i.e.

$V_{y}^{-1}:\mathcal{M}\to\mathcal{L}(\mathcal{E},E_{y}),\ \text{with
}p_{\mathcal{L}}(V^{-1}_{y}(\hat{y}))=\hat{y}\; \forall\hat{y}\in\mathcal{M}$

with the property that $V^{-1}_{y}(y)=Id_{E_{y}}$ and $V^{-1}_{y}(\hat{y})$ is
invertible for all $\hat{y}\in\mathcal{M}$.

By restricting $\mathcal{M}$ appropriately, vector transports can also be
defined locally. Given a vector transport
$V_{y}\in\Gamma(\mathcal{L}(\mathcal{M}\times E_{y},\mathcal{E})$, we can
derive a vector back-transport
$V_{y}^{-1}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$ by taking pointwise
inverses $V_{y}^{-1}(\hat{y}):=(V_{y}(\hat{y}))^{-1}$,
$\hat{y}\in\mathcal{M}$, and vice versa.

#### Connections on vector bundles.

The concept of a _connection_ of a vector bundle $p:\mathcal{E}\to\mathcal{M}$
is fundamental to differential geometry. It is an additional geometric
structure imposed on $\mathcal{E}$ that describes in an infinitesimal way, how
neighboring fibres are related. The most prominent example is the Levi-Civita
connection on $\mathcal{E}=T\mathcal{X}$ (see e.g. [13, VIII §4]) for a
Riemannian manifold $\mathcal{X}$. Connections give rise to further concepts
like the covariant derivative, curvature, geodesics, and parallel transports.
They are described in the literature in various equivalent ways (cf. e.g. [13,
IV §3 or X §4 or XIII]). For the purpose of our paper we choose a formulation
that emphasizes the idea of a connection map $Q_{e}:T_{e}\mathcal{E}\to
E_{p(e)}$, which then induces a splitting of $T_{e}\mathcal{E}$ into a
vertical and a horizontal subspace.

It is well known that the kernel of $p^{\prime}:T\mathcal{E}\rightarrow
T\mathcal{M}$ canonically defines the _vertical subbundle_ $V\mathcal{E}$ of
$\mathcal{E}$ [13, IV §3]. Its fibres are closed linear subspaces, called the
vertical subspaces $V_{e}:=\ker p^{\prime}(e)\subset T_{e}\mathcal{E}$. We can
identify $E_{p(e)}\cong V_{e}$ canonically by the isomorphism
$\operatorname{\kappa}_{e}:E_{p(e)}\rightarrow V_{e}$, given by
$w\mapsto\frac{d}{dt}(e+tw)|_{t=0}$. Elements of $V_{e}$ are represented in
trivializations by pairs of the form $(0_{y},\delta e_{\tau})\in
T_{y}\mathcal{M}\times\mathbb{E}$.

Using this identification, we define a _connection map_
$Q:T\mathcal{E}\rightarrow\mathcal{E}$ as a fibrewise projection onto
$\mathcal{E}$. More precisely,
$Q\in\Gamma(\mathcal{L}(T\mathcal{E},p^{*}\mathcal{E}))$, i.e., for each
$e\in\mathcal{E}$ we get a continuous linear map $Q_{e}\in
L(T_{e}\mathcal{E},E_{p(e)})$, such that
$Q_{e}\operatorname{\kappa}_{e}=Id_{E_{p(e)}}$. The kernels $H_{e}:=\ker
Q_{e}$ are called _horizontal subspaces_ , collected in the _horizontal
subbundle_ $H\mathcal{E}$. While $V\mathcal{E}$ is given canonically, a choice
of $Q$ (or equivalently $H\mathcal{E}$), imposes additional geometric
structure on $\mathcal{E}$.

Using the representations $(y,e_{\tau})\in\mathcal{M}\times\mathbb{E}$ for
$e\in\mathcal{E}$ and $(\delta y,\delta e_{\tau})\in
T_{x}\mathcal{M}\times\mathbb{E}$ for $\delta e\in T_{e}\mathcal{E}$, the
representation for a linear connection map $Q$ in trivializations can be
written in the form

$Q_{e}\delta e\sim Q_{e,\tau}(\delta y,\delta e_{\tau})=\delta
e_{\tau}-B_{y,\tau}(e_{\tau})\delta y,$ (3)

where $B_{y,\tau}:\mathbb{E}\to L(T_{y}\mathcal{M},\mathbb{E})$ assigns a
linear mapping $B_{y,\tau}(e_{\tau})$ to each $e_{\tau}\in\mathcal{E}$. Since
$Q_{e,\tau}(0_{y},\delta e_{\tau})=\delta e_{\tau}$, we see that $Q_{e,\tau}$
indeed represents a projection onto $V_{y}$. To reflect the linearity of the
fibres we want the connection to be _linear_ (fibrewise with respect to $e$).
To this end, we consider the fibrewise scaling
$m_{s}:\mathcal{E}\rightarrow\mathcal{E},e\mapsto se$ and require the
condition $Q\circ m_{s}^{\prime}=m_{s}\circ Q$ for all $s\in\mathbb{K}$, which
reads in trivializations:

$Q_{se,\tau}(\delta y,s\delta e_{\tau})=sQ_{e,\tau}(\delta y,\delta
e_{\tau})\quad\forall s\in\mathbb{K}.$

It can be shown that $Q$ is linear, if and only if the mapping $e_{\tau}\to
B_{y,\tau}(e_{\tau})$ is linear, or put differently, the mapping $(\delta
y,e_{\tau})\to B_{y,\tau}(e_{\tau})\delta y$ is bilinear. Alternatively, for a
vector bundle chart $\Phi$ we have a representation
$B_{y,\Phi}:\mathbb{M}\times\mathbb{E}\to\mathbb{E}$.

If $\mathcal{E}=T\mathcal{X}$ in classical Riemannian geometry, where $Q$ is
given by the Levi-Civita connection, the bilinear mapping
$B_{x,\Phi}:\mathbb{X}\times\mathbb{X}\to\mathbb{X}$ is represented by
Christoffel symbols, and it is symmetric, i.e.
$B_{x,\Phi}(v_{i})w_{i}=B_{x,\Phi}(w_{i})v_{i}$, in natural tangent bundle
charts.

#### Connections induced by vector back-transports.

If no Levi-Civita connection is present or expensive to evaluate
algorithmically, connections can be derived from differentiable vector back-
transports, which are needed frequently for numerical purposes anyway:

######  Lemma 2.3.

Let $V^{-1}_{y}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$ be a vector back-
transport and $e\in E_{y}$, $y=p(e)$. Then

$Q_{e}:={\langle{V^{-1}_{y}}\rangle}^{\prime}(e):T_{e}\mathcal{E}\to E_{y}$

defines a linear connection map at $e$, which is represented in
trivializations by (3) with

$B_{y,\tau}(e_{\tau})\delta y=-((V_{y,\tau}^{-1})^{\prime}(y)\delta
y)e_{\tau}.$ (4)

If $V_{y}^{-1}$ is defined via pointwise inverses of a vector transport
$V_{y}\in\Gamma(\mathcal{M}\times E_{y},\mathcal{E})$, then

$B_{y,\tau}(e_{\tau})\delta y=(V_{y,\tau}^{\prime}(y)\delta y)e_{\tau}.$ (5)

###### Proof.

By differentiation of ${\langle{V^{-1}_{y}}\rangle}:\mathcal{E}\to E_{y}$ we
obtain that ${\langle{V^{-1}_{y}}\rangle}^{\prime}(e):T_{e}\mathcal{E}\to
E_{y}$ is a continuous linear map. Using (2) and $V_{y}^{-1}(y)=Id_{E_{y}}$,
the representation of
${\langle{V_{y}^{-1}}\rangle}^{\prime}\in\Gamma(\mathcal{L}(T\mathcal{E},E_{y}))$
in trivializations, where $V_{y,\tau}^{-1}:\mathcal{M}\to
L(\mathbb{E},\mathbb{E})$, reads

${\langle{V_{y}^{-1}}\rangle}_{\tau}^{\prime}(e)(\delta y,\delta
e_{\tau})=\delta e_{\tau}+((V_{y,\tau}^{-1})^{\prime}(y)\delta
y)e_{\tau}\quad\forall(\delta y,\delta e_{\tau}),$

which is of the form (3), implying (4) and linearity. Let $\hat{e}\in E_{y}$.
Since $\kappa_{e}(\hat{e})\in V_{e}\cong E_{y}$ we get the representation
$\kappa_{e}(\hat{e})_{\tau}\sim(0_{y},\widehat{\delta e}_{\tau})$. Thus, we
obtain $Q_{e}\kappa_{e}=Id_{E_{y}}$.

To show (5) we compute by the calculus rule for inverse matrices and
$V^{-1}_{y,\tau}(y)=Id_{\mathbb{E}}$:

$\displaystyle(V_{y,\tau}^{-1})^{\prime}(y)\delta
y=-V^{-1}_{y,\tau}(y)V_{y,\tau}^{\prime}(y)\delta
y\,V^{-1}_{y,\tau}(y)=-V_{y,\tau}^{\prime}(y)\delta y.$

∎

######  Definition 2.4.

Let $e\in\mathcal{E}$ and $y=p(e)$. We call a vector back-transport
$V^{-1}_{y}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$ _consistent_ with a
connection map $Q:T\mathcal{E}\to\mathcal{E}$ at $e$, if
$Q_{e}={\langle{V^{-1}_{y}}\rangle}^{\prime}(e)$.

## 3\. Definition of Newton’s method

Let $F:\mathcal{X}\rightarrow\mathcal{E}$ be a differentiable mapping between
a Banach manifold $\mathcal{X}$ and a vector bundle
$p:\mathcal{E}\to\mathcal{M}$. By the composition

$y:=p\circ F:\mathcal{X}\to\mathcal{M},\;y(x):=p(F(x))\in\mathcal{M},$

we can compute the base point $y(x)\in\mathcal{M}$ of $F(x)\in\mathcal{E}$ for
given $x\in\mathcal{X}$. Consider the following root finding problem

$F(x)=0_{{y(x)}}.$

In contrast to the classical case, the linear space $E_{y(x)}$ in which $F(x)$
is evaluated now depends on $x$. Hence, iterative methods will have to deal
with the situation that $E_{y(x)}$ changes during the iteration.

To derive Newton’s method for this problem we need to define a suitable Newton
direction $\delta x\in T_{x}\mathcal{X}$. The tangent map of $F$ is a mapping
$F^{\prime}:T\mathcal{X}\rightarrow T\mathcal{E}$. Since $F^{\prime}(x)\delta
x\in T_{F(x)}\mathcal{E}$ and $F(x)\in E_{y(x)}$, these two quantities cannot
be added, and thus the classical Newton equation $F^{\prime}(x)\delta
x+F(x)=0$ is not well defined.

A _connection map_ $Q:T\mathcal{E}\rightarrow\mathcal{E}$ on $\mathcal{E}$
allows us to resolve this issue. With its help we can define the following
linear mapping at $x\in\mathcal{X}$, which maps into the correct space:

$Q_{F(x)}\circ F^{\prime}(x):T_{x}\mathcal{X}\to E_{y(x)}.$

Then the _Newton equation_ is well defined as the following linear operator
equation

$Q_{F(x)}\circ F^{\prime}(x)\delta x+F(x)=0_{{y(x)}}.$

If $Q_{F(x)}\circ F^{\prime}(x)$ is invertible, then the Newton direction
$\delta x\in T_{x}\mathcal{X}$ is given as the unique solution of this
equation, and $\delta x=0$ if and only if $F(x)=0$.

The classical additive Newton update $x_{+}=x+\delta x$ is also not well
defined since $x\in\mathcal{X}$ and $\delta x\in T_{x}\mathcal{X}$ cannot be
added. To obtain a new iterate, we have to map $\delta x\in T_{x}\mathcal{X}$
back to the manifold $\mathcal{X}$, which can be done by a retraction, a
popular concept, used widely in numerical methods on manifolds [1, Chap. 4]:

######  Definition 3.1 (Retraction).

A _retraction_ on a manifold $\mathcal{X}$ is a smooth mapping
$R:T\mathcal{X}\rightarrow\mathcal{X}$, where
$R_{x}:T_{x}\mathcal{X}\to\mathcal{X}$ for a fixed $x\in\mathcal{X}$ satisfies
the following properties:

  * (i)

$R_{x}(0_{x})=x$

  * (ii)

$R_{x}^{\prime}(0_{x})=Id_{T_{x}\mathcal{X}}$

Thus, after successfully computing the Newton direction we use a retraction to
generate the Newton step

$x_{+}:=R_{x}(\delta x).$

The result is the following local algorithm:

Algorithm 1 Newton’s method on vector bundles

0: $x_{0}$ (starting point)

for k = 1,2,… do

$\delta x_{k}\leftarrow Q_{F(x_{k})}\circ F^{\prime}(x_{k})\delta
x_{k}+F(x_{k})=0_{{y(x_{k})}}$

$x_{k+1}=R_{x_{k}}(\delta x_{k})$

end for

## 4\. Newton-Differentiability and Strict Differentiability

For the analysis of Newton’s method we will carry over two differentiability
concepts, which are known on linear spaces, but slightly non-standard in the
context of manifolds. The first is the so called _Newton-differentiability_
[17, 20, 25], a concept which is tailored for the analysis of local
convergence of Newton’s method, even for semismooth problems, the second one
is _strict differentiability_ [18, 21], a notion that is stronger than Fréchet
differentiability, but weaker than continuous differentiability. As usual, we
define these concepts by looking at the problem in local charts and showing
invariance with respect to changes of charts.

Consider $f:\mathcal{X}\to\mathcal{Y}$ where $\mathcal{X}$ and $\mathcal{Y}$
are both $C^{1}$ Banach manifolds. Let $(U,\phi)$ be a chart of $\mathcal{X}$
and $(V,\psi)$ be a chart of $\mathcal{Y}$. For $(U,\phi)$ and $(V,\psi)$
denote by $\Phi$ and $\Psi$ the corresponding vector bundle charts of
$T\mathcal{X}$ and $T\mathcal{Y}$ according to Remark 2.1. We define the
pullback

$f_{\phi,\psi}:=\psi\circ f\circ\phi^{-1}:\phi(U)\to\mathbb{Y}.$

Using this chart representation, we can define Newton-differentiability of $f$
with respect to
$f^{\prime}\in\Gamma(\mathcal{L}(T\mathcal{X},f^{*}T\mathcal{Y}))$ (which need
not be the classical derivative) in the following way:

######  Definition 4.1 (Newton-differentiability of mappings between
manifolds).

Let $f:\mathcal{X}\to\mathcal{Y}$ be locally Lipschitz continuous and
$f^{\prime}\in\Gamma(\mathcal{L}(T\mathcal{X},f^{*}T\mathcal{Y}))$ be locally
bounded.

We call $f$ _Newton-differentiable at a point $x_{0}\in\mathcal{X}$ with
respect to $f^{\prime}$_ if the chart representations of $f$ and $f^{\prime}$
satisfy

$\lim_{\xi\to\xi_{0}}\frac{\|f^{\prime}_{\Phi,\Psi}(\xi)(\xi-\xi_{0})-(f_{\phi,\psi}(\xi)-f_{\phi,\psi}(\xi_{0}))\|_{\mathbb{Y}}}{\|\xi-\xi_{0}\|_{\mathbb{X}}}=0,$

where $\xi_{0}=\phi(x_{0})$ and $\xi\in\phi(U)$. We call $f^{\prime}$ a
_Newton-derivative_ of $f$ at $x_{0}$.

Be aware that Newton-derivatives are not unique, that’s why this definition
refers to a given pair $f,f^{\prime}$. As we will see in the following
discussion, local Lipschitz continuity of $f$ and local boundedness of
$f^{\prime}$ are required to render Newton-differentiability independent of
charts.

Analogously, we can define strict differentiability of
$f:\mathcal{X}\to\mathcal{Y}$ in the following way:

######  Definition 4.2 (Strict differentiability of mappings between
manifolds).

Let $f:\mathcal{X}\to\mathcal{Y}$. $f$ is called _strictly differentiable_ at
$x_{0}\in\mathcal{X}$, if there is $f^{\prime}(x_{0})\in
L(T_{x_{0}}\mathcal{X},T_{f(x_{0})}\mathcal{Y})$, such that the chart
representations of $f$ and $f^{\prime}$ satisfy the following condition:
For every $\varepsilon>0$ there exists a neighborhood $U$ of
$\xi_{0}=\phi(x_{0})$ such that for $\xi,\eta\in U$

$\|f^{\prime}_{\Phi,\Psi}(\xi_{0})(\xi-\eta)-(f_{\phi,\psi}(\xi)-f_{\phi,\psi}(\eta))\|_{\mathbb{Y}}<\varepsilon\|\xi-\eta\|_{\mathbb{X}}.$

The mapping $f^{\prime}(x_{0})$ is called _strict derivative_ of $f$ at
$x_{0}$.

In linear spaces it is well known, and also not hard to verify, that
continuous differentiability implies Newton-differentiability, as well as
strict differentiability. Since the chart representation of a $C^{1}$-mapping
$f:\mathcal{X}\to\mathcal{Y}$ is a $C^{1}$-mapping between vector spaces, we
can conclude, that $f$ is also Newton-differentiable and strictly
differentiable.

In linear spaces we have the following chain rule for the Newton-
differentiability [10] and strict differentiability, which we will use to
verify that our definition is independent of the used charts:

######  Lemma 4.3.

Let $\mathbb{X},\;\mathbb{Y}$ and $\mathbb{Z}$ be normed linear spaces.
Consider $f:\mathbb{X}\to\mathbb{Y}$ and $g:\mathbb{Y}\to\mathbb{Z}$.

  1. (i)

Let $f$ and $g$ be Newton-differentiable with respect to Newton-derivatives
$f^{\prime}$ and $g^{\prime}$ in open sets $V$ and $U$, respectively, with
$U\subset\mathbb{X}$, $f(U)\subset V\subset\mathbb{Y}$. Assume that $f$ is
locally Lipschitz continuous and $g^{\prime}$ is locally bounded. Then $g\circ
f:\mathbb{X}\to\mathbb{Z}$ is Newton-differentiable with respect to a Newton-
derivative $g^{\prime}(f(\cdot))f^{\prime}(\cdot):\mathbb{X}\to\mathbb{Z}$.

  2. (ii)

Let $f$ and $g$ be strictly differentiable with strict derivative $f^{\prime}$
and $g^{\prime}$ in open sets $V$ and $U$, respectively, with
$U\subset\mathbb{X}$, $f(U)\subset V\subset\mathbb{Y}$. Then $g\circ
f:\mathbb{X}\to\mathbb{Z}$ is strictly differentiable with strict derivative
$g^{\prime}(f(\cdot))f^{\prime}(\cdot):\mathbb{X}\to\mathbb{Z}$.

###### Proof.

Let $x,y,x_{0}\in U$. Consider the remainder term

$\displaystyle\|g^{\prime}(f(x_{0}))f^{\prime}(x_{0})(x-y)-(g\circ f(x)-g\circ
f(y))\|_{\mathbb{Z}}$ (6)
$\displaystyle=\|g^{\prime}(f(x_{0}))(f(x)-f(y))-(g(f(x))-g(f(y)))+R(x,y,x_{0})\|_{\mathbb{Z}}$

where
$R(x,y,x_{0}):=g^{\prime}(f(x_{0}))f^{\prime}(x_{0})(x-y)-g^{\prime}(f(x_{0}))(f(x)-f(y))$.
Since $g^{\prime}$ is locally bounded in the Newton-differentiable case and
$x_{0}$ is fixed in the strict differentiable case, there exists a local
constant $C>0$ such that

$\|g^{\prime}(f(x_{0}))\|_{\mathbb{Y}\to\mathbb{Z}}\leq C.$

Thus, we obtain

$\displaystyle\|R(x,y,x_{0})\|_{\mathbb{Z}}$
$\displaystyle=\|g^{\prime}(f(x_{0}))\left[f^{\prime}(x_{0})(x-y)-(f(x)-f(y)\right]\|_{\mathbb{Z}}$
$\displaystyle\leq C\cdot\|f^{\prime}(x_{0})(x-y)-(f(x)-f(y))\|_{\mathbb{Y}}$

Hence, we can estimate (6) by

$\displaystyle\|g^{\prime}(f(x_{0}))f^{\prime}(x_{0})(x-y)-(g\circ f(x)-g\circ
f(y))\|_{\mathbb{Z}}$ (7)
$\displaystyle\leq\|g^{\prime}(f(x_{0}))(f(x)-f(y))-(g(f(x))-g(f(y)))\|_{\mathbb{Z}}+C\cdot\|f^{\prime}(x_{0})(x-y)-(f(x)-f(y))\|_{\mathbb{Y}}.$

Now consider the different cases:

(i): Set $x=x_{0}$. Let $y$ be fixed. Newton-differentiability of $f$ at $x$
yields

$\|f^{\prime}(x)(x-y)-(f(x)-f(y))\|_{\mathbb{Y}}=o(\|x-y\|_{\mathbb{X}})$

as $x\to y$. Since $g$ is Newton-differentiable at $f(x)\in V$, we get that

$\|g^{\prime}(f(x))(f(x)-f(y))-(g(f(x))-g(f(y)))\|_{\mathbb{Z}}=o(\|f(x)-f(y)\|_{\mathbb{Y}}).$

By local Lipschitz-continuity of $f$, we obtain that
$\|f(x)-f(y)\|_{\mathbb{Y}}=\mathcal{O}(\|x-y\|_{\mathbb{X}})$ as $x\to y$.
Using this in (7), we get for the remainder term

$\displaystyle\|g^{\prime}(f(x))f^{\prime}(x)(x-y)-(g\circ f(x)-g\circ
f(y))\|_{\mathbb{Z}}=o(\|x-y\|_{\mathbb{X}})$

as $x\to y$, and thus Newton-differentiability of $g\circ f$ with respect to
$g^{\prime}(f(\cdot))f^{\prime}(\cdot)$.

(ii): Let $\varepsilon>0$ and $x_{0}\in X$ be fixed. Using the strict
differentiability of $f$ at $x_{0}$, there exists a neighborhood $W\subset U$
such that for $x,y\in W$:

$\|f^{\prime}(x_{0})(x-y)-(f(x)-f(y))\|_{\mathbb{Y}}<\frac{\varepsilon}{2C}\|x-y\|_{\mathbb{X}}.$

Thus, (7) yields

$\displaystyle\|g^{\prime}(f(x_{0}))f^{\prime}(x_{0})(x-y)-(g\circ f(x)-g\circ
f(y))\|_{\mathbb{Z}}$
$\displaystyle\leq\|g^{\prime}(f(x_{0}))(f(x)-f(y))-(g(f(x))-g(f(y)))\|_{\mathbb{Z}}+\frac{\varepsilon}{2}\|x-y\|_{\mathbb{X}}.$

Using that $\|f^{\prime}(x_{0})\|_{\mathbb{X}\to\mathbb{Y}}$ is finite and $f$
is strictly differentiable at $x_{0}$, for every $\tilde{\varepsilon}>0$ there
is a neighborhood such that

$\displaystyle\|f(x)-f(y)\|_{\mathbb{Y}}$
$\displaystyle\leq\|f(x)-f(y)-f^{\prime}(x_{0})(x-y)\|_{\mathbb{Y}}+\|f^{\prime}(x_{0})(x-y)\|_{\mathbb{Y}}$
(8)
$\displaystyle<\tilde{\varepsilon}\|x-y\|_{\mathbb{X}}+\|f^{\prime}(x_{0})\|_{\mathbb{X}\to\mathbb{Y}}\|x-y\|_{\mathbb{X}}$
$\displaystyle\leq\widetilde{C}\|x-y\|_{\mathbb{X}}.$

Since $g$ is strictly differentiable at $f(x_{0})$, we obtain by possibly
shrinking $W$ that

$\|g^{\prime}(f(x_{0}))(f(x)-f(y))-(g(f(x))-g(f(y)))\|_{\mathbb{Z}}<\frac{\varepsilon}{2\widetilde{C}}\|f(x)-f(y)\|_{\mathbb{Y}}.$

Using (8), we can in summary estimate the remainder term by

$\|g^{\prime}(f(x_{0}))f^{\prime}(x)(x-y)-(g\circ f(x)-g\circ
f(y))\|_{\mathbb{Z}}<\varepsilon\|x-y\|_{\mathbb{X}}$

and thus $g\circ f$ is strictly differentiable with strict derivative
$g^{\prime}(f(\cdot))f^{\prime}(\cdot)$. ∎

######  Proposition 4.4.

Newton-differentiability and strict differentiability of
$f:\mathcal{X}\to\mathcal{Y}$ are independent of the choice of charts of
$\mathcal{X}$ and $\mathcal{Y}$.

###### Proof.

Let $\phi_{i}$ and $\psi_{i}$ be charts of $\mathcal{X}$ and $\mathcal{Y}$
such that $f$ is Newton-, respectively strictly, differentiable at
$x_{0}\in\mathcal{X}$. Let $\phi_{j}$ be another chart of $\mathcal{X}$ and
$\psi_{j}$ be another chart of $\mathcal{Y}$. Consider the mapping

$\psi_{j}\circ f\circ\phi_{j}^{-1}=T_{ij}^{\mathcal{X}}\circ(\psi_{i}\circ
f\circ\phi_{i}^{-1})\circ T_{ji}^{\mathcal{Y}}.$

$T_{ji}^{\mathcal{Y}}$ and $T_{ij}^{\mathcal{X}}$ are continuously
differentiable and thus Newton-differentiable, as well as strictly
differentiable. By applying the chain rule twice, we obtain Newton- or strict
differentiability of $\psi_{j}\circ f\circ\phi_{j}^{-1}$. ∎

## 5\. Local convergence of Newton’s method

Similar to the case of linear spaces we will now study the local convergence
of Newton’s method. This will require some preparation. To formulate local
superlinear convergence requires a metric on $\mathcal{X}$ to measure the
distance of iterates. In our general setting we are considering Banach
manifolds which may not be endowed with a Riemannian metric. Thus, we will
discuss a slightly more general way to define a metric on a manifold. Second,
we will derive a geometric criterion on Newton- and strict differentiability.
This will be especially useful later to connect our _a-priori_ analysis of
local convergence with some computable _a-posteriori_ quantities, which are
defined in the spirit of Deuflhard [9].

### 5.1. Local norms and a metric on manifolds

In Riemannian geometry, manifolds are equipped with a Riemannian metric, based
on inner products on the tangent bundle [13, VII §6]. However, in the case of
linear spaces, it is known that the convergence theory of Newton’s method is
not restricted to Hilbert spaces, but can be applied in general Banach spaces.
Hence, we will present a slightly more general notion of a metric, replacing
the usual inner products by general norms. In the infinite dimensional case,
some care has to be taken, concerning continuity properties.

######  Definition 5.1.

Consider a function $f:\mathcal{E}\to\mathbb{R}$. We call $f$ _fibrewise
uniformly continuous_ around $D\subset E_{y}$, if for any local trivialization
$\tau$, the function

$f_{\tau}:=f\circ\tau^{-1}:\tau(p^{-1}(U))\to\mathbb{R}$

satisfies the following condition:
For all $\varepsilon>0$ there exists a neighborhood $V\subset\mathcal{M}$ of
$y$ and $\delta>0$, such that for all $(y,e_{\tau})\in\tau(D)$ we have the
estimate:

$|f_{\tau}(y,e_{\tau})-f_{\tau}(\xi,\eta_{\tau})|<\varepsilon\quad\forall(\xi,\eta_{\tau})\in
p^{-1}(U):\xi\in V,\|\eta_{\tau}-e_{\tau}\|_{\mathbb{E}}<\delta.$

It is not hard to show that this notion is independent of the choice of
trivialization, taking into account that transition mappings are linear
isomorphisms on $\mathcal{E}$.

Clearly, fibrewise uniform continuity is a stronger condition than continuity,
since $\delta$ can only depend on $y$ and not on $e_{\tau}$. In particular, we
conclude, setting $\eta_{\tau}=e_{\tau}$:

$\sup_{e_{\tau}\in\tau(D)}|f_{\tau}(y,e_{\tau})-f_{\tau}(\xi,e_{\tau})|<\varepsilon\quad\forall\xi\in
V.$ (9)

On a vector bundle $p:\mathcal{E}\to\mathcal{M}$ we can define a _continuous
norm_ as follows:

######  Definition 5.2.

Consider a function $\|\cdot\|:\mathcal{E}\to[0,\infty[$ with the following
properties:

  * i)

For each $y\in\mathcal{M}$ the restriction $\|\cdot\|_{y}$ to $E_{y}$ is a
norm on $E_{y}$ which is equivalent to the $\|\cdot\|_{\mathbb{E}}$-norm that
makes $\mathbb{E}$ a Banach space. Thus, $(E_{y},\|\cdot\|_{y})$ is a Banach
space. We denote by $\mathbb{S}_{y}\subset E_{y}$ the unit sphere with respect
to $\|\cdot\|_{y}$.

  * ii)

For each $y\in\mathcal{M}$, $\|\cdot\|$ is fibrewise uniformly continuous
around the unit sphere $\mathbb{S}_{y}\subset E_{y}$.

We call $\|\cdot\|$ a _continuous norm_ on $\mathcal{E}$.

Our definition includes Riemannian metrics, as well as Finsler metrics, but is
more general than those: no differentiability assumption is imposed, since
this is not needed for our specific purpose. In particular, non-differentiable
norms, such as $1$-norms or $\infty$-norms fit into our framework.

######  Lemma 5.3.

Let $y\in\mathcal{M}$ and $\|\cdot\|:\mathcal{E}\to[0,\infty)$ be a continuous
norm. Consider its representation $\|\cdot\|_{\tau}$ in a local trivialization
around $y\in\mathcal{M}$. Then for every $1>\varepsilon>0$ there is a
neighborhood $V$ of $y$, such that

$(1-\varepsilon)\|e_{\tau}\|_{\tau,y}\leq\|e_{\tau}\|_{\tau,\xi}\leq(1+\varepsilon)\|e_{\tau}\|_{\tau,y}\quad\forall\xi\in
V,e_{\tau}\in\mathbb{E}.$

###### Proof.

Since $\|\lambda e_{\tau}\|_{\tau,y}=|\lambda|\|e_{\tau}\|_{\tau,y}$ we may
assume $\|e_{\tau}\|_{\tau,y}=1$. Now our result is a direct consequence of
(9). ∎

To define a metric on a manifold $\mathcal{X}$ we will consider a continuous
norm on the tangent bundle $T\mathcal{X}$. The following integral over a
(piecewise) $C^{1}$-curve $\alpha:[a,b]\rightarrow\mathcal{X}$ is well
defined, because the integrand is (piecewise) continuous on $[a,b]$:

$L(\alpha):=\int_{a}^{b}\|\alpha^{\prime}(t)\|_{\alpha(t)}\,dt.$

The value of this integral can be interpreted as the length of the curve
$\alpha$. The following derivations are analogous to the construction of a
Riemannian distance (cf. e.g. [13, VII §6]), and generalize them from the case
of a Hilbert space norm to the case of a Banach space norm.

To measure the “distance“ between $x$ and $y$ on $\mathcal{X}$, we form the
infimum over the lengths of all curves connecting $x$ and $y$. If $x$ and $y$
cannot be connected, we set $d(x,y)=\infty$. According to this we define the
map

$\displaystyle d:\mathcal{X}\times\mathcal{X}$
$\displaystyle\rightarrow\overline{\mathbb{R}}:=\mathbb{R}\cup\\{\infty\\}$
$\displaystyle(x,y)$ $\displaystyle\mapsto\inf\\{L(\alpha)\ |\
\alpha:[a,b]\rightarrow\mathcal{X}\text{ piecewise $C^{1}$-curve s.t.
}\alpha(a)=x,\alpha(b)=y\\}.$

In the following we will always assume that $\mathcal{X}$ is connected. Then
the axioms of a metric follow readily. Symmetry $d(x,y)=d(y,x)$ and non-
negativity, $d(x,y)\geq 0$, are obvious from the definition. It is known from
topology that on a connected manifold, two points can always be connected by a
piecewise smooth curve [12], and thus $d(x,y)<\infty\ \forall
x,y\in\mathcal{X}$. The triangle inequality follows straightforwardly from the
fact that the length of curves adds up if they are concatenated. It thus
remains to show positive definiteness of $d$, which is the only result that
requires fibrewise uniform continuity.

To this end, we first prove some results which relates the mapping $d$ to the
local norms. Let $(U,\phi)$ be a local chart at $x_{\star}\in\mathcal{X}$ and
$\Phi:\pi^{-1}(U)\to U\times\mathbb{X}$ be the corresponding natural vector
bundle chart on the tangent bundle $\pi:T\mathcal{X}\to\mathcal{X}$. We define
the open ball with radius $r>0$ around 0 with respect to the local norm
$\|\cdot\|_{x_{\star}}$ (with representation $\|\cdot\|_{\Phi,x_{\star}}$) as
$rB_{x_{\star}}:=\\{v\in\mathbb{X}:\|v\|_{\Phi,x_{\star}}<r\\}$.

######  Lemma 5.4.

Let $x_{\star}\in\mathcal{X}$ and $(U,\phi)$ a local chart, such that w.l.o.g.
$\phi(x_{\star})=0$. Let $x,y\in U$ with representatives $x_{\phi}$ and
$y_{\phi}$ in the chart. Let $1>\varepsilon>0$. Then there exists a radius
$r=r(\varepsilon)>0$ such that for every $C^{1}$-curve
$\alpha:[a,b]\to\mathcal{X}$ connecting $x$ and $y$ the following holds:

  1. (a)

If the image $\alpha_{\phi}:[a,b]\to\mathbb{X}$ lies in the open ball
$rB_{x_{\star}}$, in particular $x_{\phi},\;y_{\phi}\in rB_{x_{\star}}$, then
the following properties hold:

    1. (i)

$(1-\varepsilon)\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}}\leq L(\alpha)$

    2. (ii)

$d(x,y)\leq(1+\varepsilon)\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}}$

  2. (b)

If $\alpha_{\phi}$ is leaving the ball $rB_{x_{\star}}$, i.e.
$\alpha_{\phi}(a)=x_{\phi}\in rB_{x_{\star}}$ but $\alpha_{\phi}\not\subset
rB_{x_{\star}}$, then it holds that

$L(\alpha)\geq(1-\varepsilon)(r-\|x_{\phi}\|_{\Phi,x_{\star}}).$

###### Proof.

Since $\|\cdot\|$ is a continuous norm on $T\mathcal{X}$, according to Lemma
5.3 for $1>\varepsilon>0$ there exists a neighborhood $V$ of $x_{\star}$, such
that

$(1-\varepsilon)\|v\|_{\Phi,x_{\star}}\leq\|v\|_{\Phi,\xi}\leq(1+\varepsilon)\|v\|_{\Phi,x_{\star}}\;\forall\xi\in
V,v\in\mathbb{X}.$

The image of $V$ in the chart contains a $\|\cdot\|_{\Phi,x_{\star}}$-ball
$rB_{x_{\star}}$ around $\phi(x_{\star})=0$ with radius $r=r(\varepsilon)>0$.
Let $x,y\in U$ and $\alpha:[a,b]\to\mathcal{X}$ be a $C^{1}$-curve connecting
$x$ and $y$.

  1. (a)

Assume that the image $\alpha_{\phi}$ lies in $rB_{x_{\star}}$. Using that the
curve integral in vector spaces is always greater than or equal to the
distance of the end points, we can estimate the length of $\alpha$ by

$\displaystyle(1-\varepsilon)\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}}$
$\displaystyle\leq(1-\varepsilon)\int_{a}^{b}\|\alpha_{\phi}^{\prime}(t)\|_{\Phi,x_{\star}}\;dt\overset{\alpha(t)\in
V}{\leq}\int_{a}^{b}\|\alpha^{\prime}(t)\|_{\alpha(t)}\;dt$
$\displaystyle=L(\alpha)\leq(1+\varepsilon)\int_{a}^{b}\|\alpha_{\phi}^{\prime}(t)\|_{\Phi,x_{\star}}dt.$

Choosing the connecting line of $x_{\phi}$ and $y_{\phi}$ for $\alpha_{\phi}$
this yields $d(x,y)\leq(1+\varepsilon)\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}}$.

  2. (b)

If $\alpha_{\phi}$ leaves the open ball $rB_{x_{\star}}$, there must be a
first intersection point $s_{\phi}=\alpha_{\phi}(c)$, $c\in[a,b]$, with the
sphere $r\mathbb{S}_{x_{\star}}\subset\mathbb{X}$ around $0$. Let
$\widetilde{\alpha}_{\phi}$ be the part of $\alpha_{\phi}$ connecting
$x_{\phi}$ and $s_{\phi}$. Then by the norm equivalence and the inverse
triangle inequality:

$\displaystyle
L(\widetilde{\alpha})=\int_{a}^{c}\|\widetilde{\alpha}^{\prime}(t)\|_{\widetilde{\alpha}(t)}dt$
$\displaystyle\geq(1-\varepsilon)\int_{a}^{c}\|\widetilde{\alpha}_{\phi}^{\prime}(t)\|_{\Phi,x_{\star}}dt$
$\displaystyle\geq(1-\varepsilon)(\|s_{\phi}\|_{\Phi,x_{\star}}-\|x_{\phi}\|_{\Phi,x_{\star}})=(1-\varepsilon)(r-\|x_{\phi}\|_{\Phi,x_{\star}}).$

Thus, we get $L(\alpha)\geq(1-\varepsilon)(r-\|x_{\phi}\|_{\Phi,x_{\star}})$.

∎

######  Proposition 5.5.

Let $1>\varepsilon>0$. Then there is a neighborhood $W\subseteq U$ of
$x_{\star}$ such that

$(1-\varepsilon)\cdot\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}}\leq
d(x,y)\leq(1+\varepsilon)\cdot\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}}\ \forall
x,y\in W,$

where $x_{\phi},y_{\phi}\in\mathbb{X}$ are representatives of $x$ and $y$ in
the chart.

###### Proof.

W.l.o.g. assume $\phi(x_{\star})=0$. By Lemma 5.4, we directly obtain

$d(x,y)\leq(1+\varepsilon)\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}}\;\forall
x,y\in\phi^{-1}(rB_{x_{\star}}),$

where $r>0$ is chosen sufficiently small. Now let $\alpha$ be an arbitrary
curve connecting $x$ and $y$. Lemma 5.4 yields

$\displaystyle\alpha_{\phi}\subset rB_{x_{\star}}$ $\displaystyle\Rightarrow
L(\alpha)\geq(1-\varepsilon)\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}},$
$\displaystyle\alpha_{\phi}\not\subset rB_{x_{\star}}$
$\displaystyle\Rightarrow
L(\alpha)\geq(1-\varepsilon)(r-\|x_{\phi}\|_{\Phi,x_{\star}}).$

Thus, we obtain

$d(x,y)\geq(1-\varepsilon)\cdot\min\\{\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}},r-\|x_{\phi}\|_{\Phi,x_{\star}}\\}.$
(10)

Choosing $W:=\phi^{-1}(\frac{r}{3}B_{x_{\star}})$ yields
$d(x,y)\geq(1-\varepsilon)\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}}$ and thus our
claim. ∎

######  Corollary 5.6.

Let $\mathcal{X}$ be a connected $C^{1}$ Banach manifold with the Hausdorff
property. Then $d$ defines a metric on $\mathcal{X}$. Moreover, the induced
topology coincides with the topology on $\mathcal{X}$ induced by the atlas.

###### Proof.

Let $x\neq y$. Let $(U,\phi)$ be a local chart at $x$ such that w.l.o.g.
$\phi(x)=x_{\phi}=0$, and let $\Phi:\pi^{-1}(U)\rightarrow U\times\mathbb{X}$
be the natural vector bundle chart on the tangent bundle
$\pi:T\mathcal{X}\rightarrow\mathcal{X}$.
Since $\mathcal{X}$ satisfies the Hausdorff property and $x\neq y$ holds,
there is a $\|\cdot\|_{\Phi,x}$-ball $rB_{x}$ around $0$ with radius $r>0$
such that $y\not\in\phi^{-1}(rB_{x})$. Possibly decreasing $r$ first, we
obtain by (10)

$d(x,y)\geq(1-\varepsilon)\cdot\min\\{\|y_{\phi}\|_{\Phi,x},r\\}=(1-\varepsilon)\cdot
r>0.$

Moreover, for $y\in\phi^{-1}(r\mathbb{S}_{x})$ we obtain by Prop. 5.5

$(1-\varepsilon)\cdot\|y_{\phi}\|_{\Phi,x}\leq
d(x,y)\leq(1+\varepsilon)\cdot\|y_{\phi}\|_{\Phi,x}.$

Since $\|\cdot\|_{\Phi,x}$ is equivalent to $\|\cdot\|_{\mathbb{X}}$, this
implies that every $\mathbb{X}$-ball contains a $d$-ball and vice versa. Thus,
the topology induced by $d$ coincides with the topology induced by the atlas
of $\mathcal{X}$. ∎

Now consider a retraction $R:T\mathcal{X}\rightarrow\mathcal{X}$. For
$C^{1}$-retractions of this kind it is well known that the following property
holds [1] by the inverse function theorem.

######  Proposition 5.7.

Let $x_{\star}\in\mathcal{X}$ and let $R$ be a $C^{1}$-retraction. Then there
exists a neighborhood $V\subseteq T\mathcal{X}$ of $(x_{\star},0)\in
T\mathcal{X}$ such that $R:V\rightarrow R(V)$ is a diffeomorphism.

Finally, we can relate retractions, local norms and the metric on
$\mathcal{X}$ defined by the local norms.

######  Proposition 5.8.

To $x_{\star}\in\mathcal{X}$ and $1>\varepsilon>0$ there exists a neighborhood
$V$ of $x_{\star}$ such that for all $x,y,z\in V$ the following holds:

$(1-\varepsilon)\|R^{-1}_{z}(x)-R^{-1}_{z}(y)\|_{z}\leq
d(x,y)\leq(1+\varepsilon)\|R^{-1}_{z}(x)-R^{-1}_{z}(y)\|_{z}.$

###### Proof.

Choose a chart $(U,\phi)$ of $\mathcal{X}$ at $x_{\star}$ and denote by
$\Phi:\pi^{-1}(U)\to U\times\mathbb{X}$ the natural vector bundle chart on the
tangent bundle $\pi:T\mathcal{X}\to\mathcal{X}$. Let $x_{\star,\phi},\
x_{\phi},\ y_{\phi}$ and $z_{\phi}$ be representatives of $x_{\star},x,y$ and
$z$ in the chart. Let $R_{\phi}^{-1}$ be the chart representation of $R^{-1}$.
We show that

$\lim_{x_{\phi},y_{\phi},z_{\phi}\rightarrow
x_{\star,\phi}}\frac{\|R_{\phi}^{-1}(z_{\phi},x_{\phi})-R_{\phi}^{-1}(z_{\phi},y_{\phi})\|_{\Phi,x_{\star}}}{\|x_{\phi}-y_{\phi}\|_{\Phi,x_{\star}}}=1.$

Since $R^{-1}$ is continuously differentiable, $R^{-1}$ is also strictly
differentiable. Thus, by additionally using the properties of a retraction,
there exists a neighborhood $V$, such that for arbitrary $\varepsilon>0$ we
obtain, denoting by $r_{R^{-1}}(x_{\phi},y_{\phi})$ the remainder term of
strict differentiability:

$\displaystyle\|R_{\phi}^{-1}(z_{\phi},x_{\phi})-R_{\phi}^{-1}(z_{\phi},y_{\phi})\|_{\mathbb{X}}$
$\displaystyle=\|(R_{\phi}^{-1})^{\prime}(x_{\star,\phi},x_{\star,\phi})(x_{\phi}-y_{\phi})+r_{R^{-1}}(x_{\phi},y_{\phi})\|_{\mathbb{X}}$
$\displaystyle=\|R_{\phi}^{\prime}(R_{\phi}^{-1}(x_{\star,\phi},x_{\star,\phi}))(x_{\phi}-y_{\phi})+r_{R^{-1}}(x_{\phi},y_{\phi})\|_{\mathbb{X}}$
$\displaystyle=\|x_{\phi}-y_{\phi}+r_{R^{-1}}(x_{\phi},y_{\phi})\|_{\mathbb{X}}$
$\displaystyle\leq\|x_{\phi}-y_{\phi}\|_{\mathbb{X}}+\varepsilon\|x_{\phi}-y_{\phi}\|_{\mathbb{X}}.$

Using that $\|\cdot\|_{\Phi,x_{\star}}$ is equivalent to
$\|\cdot\|_{\mathbb{X}}$ and by possibly shrinking $V$, we obtain the desired
assertion by Prop. 5.5. ∎

### 5.2. Newton- and Strict Differentiability in Geometric Form

In order to analyse local convergence of Newton’s method, we want to prove a
result about a Newton- or strictly differentiable mapping
$F:\mathcal{X}\to\mathcal{E}$ between a manifold $\mathcal{X}$ and a vector
bundle $p:\mathcal{E}\to\mathcal{M}$, which can be stated independently of the
choice of charts.

In the following, we assume that the mapping

$y=p\circ F:\mathcal{X}\to\mathcal{M},\;y(x):=p(F(x))\in\mathcal{M},$

which computes the base point of $F(x)\in\mathcal{E}$ for any
$x\in\mathcal{X}$, is locally Lipschitz continuous. We may use the linear map
$V^{-1}_{y}(y_{0})\in L(E_{y_{0}},E_{y})$ given by a vector back-transport
$V_{y}^{-1}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$ to transport elements
$F(x_{0})\in E_{y_{0}}$ into the fibre $E_{y}$.

######  Proposition 5.9.

Let $F:\mathcal{X}\to\mathcal{E}$. Let
$V^{-1}_{y}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$ be a vector back-
transport, $Q:T\mathcal{E}\to\mathcal{E}$ be a connection map and
$R:T\mathcal{X}\to\mathcal{X}$ be a retraction.

  1. (i)

Let $F:\mathcal{X}\to\mathcal{E}$ be Newton-differentiable at a point
$\xi\in\mathcal{X}$ with respect to a fibrewise linear mapping
$F^{\prime}\in\Gamma(\mathcal{L}(T\mathcal{X},F^{*}T\mathcal{E}))$. If
$V^{-1}_{y}$ is consistent with $Q$ or $F(\xi)=0$, then it holds

$\underset{x\to\xi}{\lim}\frac{\|(Q_{F(x)}\circ
F^{\prime}(x))(R_{x}^{-1}(x)-R_{x}^{-1}(\xi))-(F(x)-V_{y(x)}^{-1}(y(\xi))F(\xi))\|_{E_{y(x)}}}{d_{\mathcal{X}}(x,\xi)}=0.$

  2. (ii)

Let $F$ be strictly differentiable at $a\in\mathcal{X}$. If $V^{-1}_{y}$ is
consistent with $Q$ or $F(a)=0$ then for every $\varepsilon>0$ there exists a
neighborhood $W$ of $a$ such that for all $x,\xi\in W$ it holds

$\displaystyle\|(Q_{F(a)}\circ F^{\prime}(a))(R_{a}^{-1}(x)$ $\displaystyle-
R_{a}^{-1}(\xi))-(V^{-1}_{y(a)}(y(x))F(x)-V_{y(a)}^{-1}(y(\xi))F(\xi))\|_{E_{y(a)}}$
$\displaystyle<\varepsilon\|R_{a}^{-1}(x)-R_{a}^{-1}(\xi)\|_{a}.$

###### Proof.

Choose a chart $\phi$ of $\mathcal{X}$ and a vector bundle chart $\eta$ of the
vector bundle $\mathcal{E}$. In the following, we use $\phi$ or $\eta$ as an
index to denote the chart representation of elements of $\mathcal{X}$ or
$\mathcal{E}$, respectively. We begin by discussing the numerators in $(i)$
and $(ii)$ in a unified way. Then for the proof of $(i)$ we will fix $\xi$ and
consider the case $x=a$ and $x\to\xi$. For the proof of $(ii)$ we will fix $a$
and consider $x,\xi\to a$.

Let $R_{a,\phi}^{-1}$ be a representation of the inverse retraction in charts.
Since $R_{a}^{-1}$ is a $C^{1}$-mapping and using
$(R_{a}^{-1})^{\prime}(a)=Id_{T_{a}\mathcal{X}}$, we obtain

$R_{a,\phi}^{-1}(x_{\phi})-R_{a,\phi}^{-1}(\xi_{\phi})=(R^{-1}_{a,\phi})^{\prime}(a_{\phi})(x_{\phi}-\xi_{\phi})+r_{R}=(x_{\phi}-\xi_{\phi})+r_{R}$

where $r_{R}$ is a remainder term. Setting $\delta
x_{\phi}=x_{\phi}-\xi_{\phi}$ and $\delta
y_{\eta}:=y(x)_{\eta}-y(\xi)_{\eta}\in\mathbb{M}$, we obtain the chart
representation of

$(Q_{F(a)}\circ F^{\prime}(a))(R_{a}^{-1}(x)-R_{a}^{-1}(\xi))$

by

$(F_{\eta})^{\prime}(a_{\phi})(\delta
x_{\phi}+r_{R})-B_{y(a),\eta}(F_{\eta}(a_{\phi}))\delta y_{\eta}.$ (11)

Next, we consider the representation of

$V_{y(a)}^{-1}(y(x))F(x)-V_{y(a)}^{-1}(y(\xi))F(\xi),$

which is of the form

$V^{-1}_{y(a),\eta}(y(x)_{\eta})F_{\eta}(x_{\phi})-V^{-1}_{y(a),\eta}(y(\xi)_{\eta})F_{\eta}(\xi_{\phi}).$
(12)

Using the differentiability of the mapping $V_{y,\eta}^{-1}:\mathbb{M}\to
L(\mathbb{E},\mathbb{E})$, we can write:

$V_{y(a),\eta}^{-1}(y(x)_{\eta})-V_{y(a),\eta}^{-1}(y(\xi)_{\eta})=(V_{y(a),\eta}^{-1})^{\prime}(y(a)_{\eta})\delta
y_{\eta}+r_{V}.$

Inserting this into (12) we obtain by linearity of $V_{y}^{-1}(y)$

$\displaystyle((V_{y(a),\eta}^{-1})^{\prime}(y(a)_{\eta})\delta
y_{\eta})F_{\eta}(\xi_{\phi})+V_{y(a),\eta}^{-1}(y(x)_{\eta})(F_{\eta}(x_{\phi})-F_{\eta}(\xi_{\phi}))+r_{V}F_{\eta}(\xi_{\phi}).$
(13)

Writing the difference $F_{\eta}(x_{\phi})-F_{\eta}(\xi_{\phi})$ as

$F_{\eta}(x_{\phi})-F_{\eta}(\xi_{\phi})=(F_{\eta})^{\prime}(a_{\phi})\delta
x_{\phi}+r_{F}.$

and subtracting (13) from (11) we finally obtain the following representation
of the numerators of $(i)$ and $(ii)$ in charts:

$\displaystyle(Id_{E_{y(a)}}-V_{y(a),\eta}^{-1}(y(x)_{\eta}))(F_{\eta})^{\prime}(a_{\phi})\delta
x_{\phi}$ $\displaystyle-B_{y(a),\eta}(F_{\eta}(a_{\phi}))\delta
y_{\eta}-((V_{y(a),\eta}^{-1})^{\prime}(y(a)_{\eta})\delta
y_{\eta})F_{\eta}(\xi_{\phi})$
$\displaystyle+(F_{\eta})^{\prime}(a_{\phi})r_{R}-V_{y(a),\eta}^{-1}(y(x)_{\eta})r_{F}-r_{V}F_{\eta}(\xi_{\phi}).$

Now consider the different cases.
$(i)$: Set $a=x$ and let $F$ be Newton-differentiable at $\xi$. Since
$V_{y}^{-1}(y)=Id_{E_{y}}$ for $y\in\mathcal{M}$ and $x=a$ our representation
reduces to

$\displaystyle-B_{y(x),\eta}(F_{\eta}(x_{\phi}))\delta
y_{\eta}-((V_{y(x),\eta}^{-1})^{\prime}(y(x)_{\eta})\delta
y_{\eta})F_{\eta}(\xi_{\phi})+(F_{\eta})^{\prime}(x_{\phi})r_{R}-r_{F}-r_{V}F_{\eta}(\xi_{\phi}).$

Since $R_{x}^{-1}$ is continuously differentiable, it is also Newton-
differentiable and thus the remainder term $r_{R}$ is of order
$o(\|x_{\phi}-\xi_{\phi}\|_{\mathbb{X}})$ as $x_{\phi}\to\xi_{\phi}$. Since
$F$ is Newton-differentiable with respect to $F^{\prime}$,
$(F_{\eta})^{\prime}(x_{\phi})$ is locally bounded. Thus, the remainder term
$(F_{\eta})^{\prime}(x_{\phi})r_{R}$ is still of order
$o(\|x_{\phi}-\xi_{\phi}\|_{\mathbb{X}})$ as $x_{\phi}\to\xi_{\phi}$. Since
$F$ is Newton-differentiable $r_{F}$ is also of order
$o(\|x_{\phi}-\xi_{\phi}\|_{\mathbb{X}})$ as $x_{\phi}\to\xi_{\phi}$. The
remainder term $r_{V}$ depends on $y(x)_{\eta}$ and $y(\xi)_{\eta}$ and is of
order $o(\|y(x)_{\eta}-y(\xi)_{\eta}\|_{\mathbb{M}})$. Since the mapping $y$
is locally Lipschitz continuous, $r_{V}F_{\eta}(\xi_{\phi})$ is of order
$o(\|x_{\phi}-\xi_{\phi}\|_{\mathbb{X}})$ as $x_{\phi}\to\xi_{\phi}$.

Thus, we have to discuss the remaining two terms

$-B_{y(x),\eta}(F_{\eta}(x_{\phi}))\delta
y_{\eta}-((V_{y(x),\eta}^{-1})^{\prime}(y(x)_{\eta})\delta
y_{\eta})F_{\eta}(\xi_{\phi}).$ (14)

Using the bilinearity of $B_{y(x),\eta}$ we can write (14) as

$\displaystyle-B_{y(x),\eta}(F_{\eta}(x_{\phi})-F_{\eta}(\xi_{\phi}))\delta
y_{\eta}-\big{[}B_{y(x),\eta}(F(\xi_{\phi}))\delta
y_{\eta}+((V_{y(x),\eta}^{-1})^{\prime}(y(x)_{\eta})\delta
y_{\eta})(F_{\eta}(\xi_{\phi}))\big{]}$

Since $F$ is Newton-differentiable and $x\mapsto B_{y(x),\eta}$ is locally
bounded, the first term is of order
$\mathcal{O}(\|x_{\phi}-\xi_{\phi}\|\|\delta y_{\eta}\|)$, and thus, by
Lipschitz continuity of $y$, of order $o(\|x_{\phi}-\xi_{\phi}\|)$. If
$V^{-1}_{y}$ is consistent with the connection map $Q$, i.e.
$B_{y(x),\eta}=-(V_{y(x),\eta}^{-1})^{\prime}(y(x)_{\eta})$, or $F(\xi)=0$ the
second term in braces vanishes. Thus, the numerator of $(i)$ is of order
$o(\|x_{\phi}-\xi_{\phi}\|_{\mathbb{X}})$ as $x_{\phi}\to\xi_{\phi}$. Finally,
using Prop. 5.5 to estimate $d_{\mathcal{X}}(x,\xi)$, we obtain the desired
result.
$(ii)$: Let $F$ be strictly differentiable at $a\in\mathcal{X}$. Let
$x,\xi\in\mathcal{X}$. If $V^{-1}_{y}$ is consistent with the connection map
$Q$ we have

$B_{y(a),\eta}(F_{\eta}(a_{\phi}))\delta
y_{\eta}=-((V_{y(a),\eta}^{-1})^{\prime}(y(a)_{\eta})\delta
y_{\eta})F_{\eta}(a_{\phi}).$

Otherwise, we assume that $F(a)=0$. In both cases our representation reads
(the sign in the second line depends on these cases):

$\displaystyle(Id_{E_{y(a)}}-V_{y(a),\eta}^{-1}(y(x)_{\eta}))(F_{\eta})^{\prime}(a_{\phi})\delta
x_{\phi}$ $\displaystyle\pm((V_{y(a),\eta}^{-1})^{\prime}(y(a)_{\eta})\delta
y_{\eta})(F_{\eta}(a_{\phi})-F_{\eta}(\xi_{\phi}))$
$\displaystyle+(F_{\eta})^{\prime}(a_{\phi})r_{R}-V_{y(a),\eta}^{-1}(y(x)_{\eta})r_{F}-F_{\eta}(\xi_{\phi})r_{V}.$

Since $(F_{\eta})^{\prime}(a_{\phi})$ is fixed, we obtain that
$(F_{\eta})^{\prime}(a_{\phi})\delta x_{\phi}$ is of order
$\mathcal{O}(\|x_{\phi}-\xi_{\phi}\|_{\mathbb{X}})$. Using that
$V_{y(a),\eta}^{-1}(y(x)_{\eta})\to Id_{E_{y(a)}}$ for $y(x)\to y(a)$, and
$x\mapsto y(x)$ is continuous, we get that
$Id_{E_{y(a)}}-V_{y(a),\eta}^{-1}(y(x)_{\eta})$ is of order
$\omega(\|x_{\phi}-a_{\phi}\|_{\mathbb{X}})$ as $x\to a$. Thus, the first line
vanishes for $x,\xi\to a$.

By strict differentiability, we have that
$F_{\eta}(a_{\phi})-F_{\eta}(\xi_{\phi})$ is of order
$\omega(\|\xi_{\phi}-a_{\phi}\|_{\mathbb{X}})$ as $\xi\to a$. The mapping $y$
is locally Lipschitz continuous, and thus $\delta y_{\eta}$ is of order
$\mathcal{O}(\|x_{\phi}-\xi_{\phi}\|_{\mathbb{X}})$. In addition
$(V_{y(a),\eta}^{-1})^{\prime}(y(a)_{\eta})$ is bilinear. Thus, the second
line also vanishes for $x,\xi\to a$.

The mappings $R_{a}^{-1}$ and $V^{-1}_{y}$ are continuously differentiable and
thus strictly differentiable. Using in addition that
$(F_{\eta})^{\prime}(a_{\phi})$ is constant, $V_{y(a),\eta}^{-1}(y(x)_{\eta})$
is locally bounded and $F$ is strictly differentiable, all the terms in the
third line vanish for $x,\xi\to a$. By using Prop. 5.5 and Prop. 5.8 this
finally yields the desired result $(ii)$. ∎

### 5.3. Local superlinear convergence

In this section we want to prove the local superlinear convergence of Newton’s
method. In the spirit of Deuflhard [9], our proof will not rely on quantities,
which may allow a qualitative _a-priori_ convergence result, but rather on
quantities for which good _a-posteriori_ algorithmic estimates are accessible.
This will be the basis of an affine covariant damping strategy, elaborated
below. Nevertheless, we will also show some results which allow an a-priori
analysis.

Let $V^{-1}_{y}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$ be a vector back-
transport. Let $Q:T\mathcal{E}\to\mathcal{E}$ be a connection map and
$R:T\mathcal{X}\to\mathcal{X}$ be a retraction. For a fixed $x\in\mathcal{X}$
we can locally perform _pullbacks_

$\displaystyle R_{x}^{-1}:\mathcal{X}$ $\displaystyle\to T_{x}\mathcal{M}$
$\displaystyle\hat{x}$
$\displaystyle\mapsto\hat{\textbf{x}}:=R_{x}^{-1}(\hat{x})$

Since $R$ is a retraction, we obtain $\textbf{x}=R_{x}^{-1}(x)=0_{x}$. For the
Newton method, defined in Section 3, we consider the following affine-
covariant quantity at $x\neq z\in\mathcal{X}$

$\theta_{z}({x}):=\frac{\big{\|}(Q_{F(x)}\circ
F^{\prime}(x))^{-1}\left[(Q_{F(x)}\circ
F^{\prime}(x))(\textbf{x}-\textbf{z})-(F(x)-V_{y(x)}^{-1}(y(z))F(z))\right]\big{\|}_{x}}{\|\textbf{x}-\textbf{z}\|_{x}}.$

The use of this quantity gives us a very simple result on local superlinear
convergence of Newton’s method, which serves two purposes. First, it will be
the basis for an a-priori result for Newton-differentiable mappings, second,
it yields an algorithmic idea to monitor local convergence.

######  Proposition 5.10.

Let $\mathcal{X}$ be a manifold and $p:\mathcal{E}\to\mathcal{M}$ a vector
bundle. Consider a mapping $F:\mathcal{X}\to\mathcal{E}$ and a section
$F^{\prime}\in\Gamma(\mathcal{L}(T\mathcal{X},F^{*}T\mathcal{E}))$. Let
$Q:T\mathcal{E}\to\mathcal{E}$ be a connection map and
$R:T\mathcal{X}\to\mathcal{X}$ be a retraction. Let $x_{\star}\in\mathcal{X}$
be a zero of $F$ and assume that all Newton steps $x_{k}$ are well defined.
Assume that

$\lim_{x\to x_{\star}}\theta_{x_{\star}}(x)=0.$ (15)

Then Newton’s method converges locally to $x_{\star}$ with a superlinear rate,
i.e.

$d_{\mathcal{X}}(x_{\star},x_{k+1})\leq\theta_{x_{\star}}(x_{k})d_{\mathcal{X}}(x_{\star},x_{k}).$

###### Proof.

Let $x\in\mathcal{X}$. Set $x_{+}:=R_{x}(\delta x)$, where $\delta x\in
T_{x}\mathcal{X}$ is the Newton direction at $x$. Using the pullback
$\textbf{x}_{+}=R_{x}^{-1}(x_{+})=\delta x$ and $F(x_{\star})=0$ we get the
following equation in the tangent space $T_{x}\mathcal{X}$:

$\|\textbf{x}_{+}-\textbf{x}_{\star}\|_{x}=\|(Q_{F(x)}\circ
F^{\prime}(x))^{-1}[(Q_{F(x)}\circ
F^{\prime}(x))(\textbf{x}-\textbf{x}_{\star})-(F(x)-V^{-1}_{y(x)}(y(x_{\star}))F(x_{\star}))]\|_{x}.$

By definition of $\theta_{x_{\star}}(x)$ it follows

$\|\textbf{x}_{+}-\textbf{x}_{\star}\|_{x}=\theta_{{x}_{\star}}({x})\cdot\|\textbf{x}-\textbf{x}_{\star}\|_{x}.$
(16)

Consider a neighborhood $V$ of $x_{\star}$, where Prop. 5.8 holds for some
$1>\varepsilon>0$. Since $\displaystyle\lim_{x\to
x_{\star}}\theta_{x_{\star}}(x)=0$, we find a metric ball
$r\mathcal{B}_{x_{\star}}=\\{x\in\mathcal{X}:d_{\mathcal{X}}(x,x_{\star})<r\\}\subset
V$ of radius $r>0$, such that

$\theta_{x_{\star}}(x)\leq\frac{1}{2}\frac{1-\varepsilon}{1+\varepsilon}\
\forall x\in r\mathcal{B}_{x_{\star}}.$

Now choose a starting point $x_{0}\in r\mathcal{B}_{x_{\star}}$ and consider
the sequence of Newton steps given by $x_{k+1}:=x_{k,+}$ for $k\geq 0$.
Assuming for induction that $x_{k}\in 2^{-k}r\mathcal{B}_{x_{\star}}$, we
obtain by using (16):

$\displaystyle d_{\mathcal{X}}(x_{k+1},x_{\star})$
$\displaystyle\leq\theta_{x_{\star}}(x_{k})\frac{1+\varepsilon}{1-\varepsilon}d_{\mathcal{X}}(x_{k},x_{\star})<r2^{-(k+1)}.$

Thus, all Newton steps remain in $r\mathcal{B}_{x_{\star}}$ and $x_{k}\to
x_{\star}$. This implies $\theta_{x_{\star}}(x_{k})\to 0$ for $k\to\infty$ and
thus superlinear convergence. ∎

We now also want to give conditions for local superlinear convergence which
can be used for a-priori analysis. With the help of a local norm on
$\mathcal{X}$ and a fibrewise norm on $\mathcal{E}$ we can define a norm of a
linear operator $A:E_{y}\to T_{x}\mathcal{X}$:

$\|A\|_{E_{y}\rightarrow T_{x}\mathcal{X}}:=\underset{\|e\|_{E_{y}}\leq
1}{\sup}\|Ae\|_{T_{x}\mathcal{X}}.$

######  Proposition 5.11.

Let $F:\mathcal{X}\to\mathcal{E}$ be Newton-differentiable at
$x_{\star}\in\mathcal{X}$ with respect to a Newton derivative
$F^{\prime}\in\Gamma(\mathcal{L}(T\mathcal{X},F^{*}T\mathcal{E}))$, where
$F(x_{\star})=0$. Assume that for $x\in\mathcal{X}$ the operator norm of
$(Q_{F(x)}\circ F^{\prime}(x))^{-1}$ is uniformly bounded, i.e. there exists
$\beta<\infty$ such that

$\|(Q_{F(x)}\circ F^{\prime}(x))^{-1}\|_{E_{y}\rightarrow
T_{x}\mathcal{X}}\leq\beta.$

Then Newton’s method converges locally to $x_{\star}$ at a superlinear rate.

###### Proof.

Let $\varepsilon\in(0,1)$. Using that the operator norm of $(Q_{F(x)}\circ
F^{\prime}(x))^{-1}$ is bounded and applying Prop. 5.8, we can estimate
$\theta_{{x}_{\star}}({x})$ in a neighborhood $V$ of $x_{\star}$ as follows:

$\displaystyle\theta_{x_{\star}}(x)$
$\displaystyle\leq\beta\cdot(1+\varepsilon)\cdot\frac{\|(Q_{F(x)}\circ
F^{\prime}(x))(R_{x}^{-1}(x)-R_{x}^{-1}(x_{\star}))-(F(x)-V_{y}^{-1}(y_{\star})F(x_{\star}))\|_{E_{y}}}{d_{\mathcal{X}}(x,x_{\star})}.$

Since $F(x_{\star})=0$ and $F$ is Newton-differentiable at $x_{\star}$, we can
apply Prop. 5.9 (i) and obtain $\underset{x\to
x_{\star}}{\lim}\theta_{x_{\star}}(x)=0$.

∎

### 5.4. Monitoring local convergence

Let us now define a computable quantity to monitor local convergence. For
this, we set $x=x_{k}$,
$y:=y(x_{k})=p(F(x_{k})),\;y_{\star}:=y(x_{\star})=p(F(x_{\star}))$ and
consider the affine-covariant quantity $\theta_{x_{\star}}(x)$ that we have
seen in the proof of the local convergence:

$\theta_{{x}_{\star}}({x})=\frac{\|(Q_{F(x)}\circ
F^{\prime}(x))^{-1}\left[(Q_{F(x)}\circ
F^{\prime}(x))(\textbf{x}-\textbf{x}_{\star})-(F(x)-V^{-1}_{y}(y_{\star})F(x_{\star}))\right]\|_{x}}{\|\textbf{x}-\textbf{x}_{\star}\|_{x}}.$

Since the target point $x_{\star}$ is not available, we replace $x_{\star}$ by
the next iterate $x_{+}:=x_{k+1}$, correspondingly the pullback
$\textbf{x}_{\star}$ by $\textbf{x}_{+}=\delta x\in T_{x}{\mathcal{X}}$, and
$y_{\star}$ by $y_{+}=p(F(x_{+}))$. By using $\textbf{x}=0_{x}$ and the
definition of the $k$-th Newton direction $\delta
x=\textbf{x}_{+}-\textbf{x}$, we obtain:

$\displaystyle\theta_{{x}_{+}}({x})$ $\displaystyle=\frac{\|(Q_{F(x)}\circ
F^{\prime}(x))^{-1}\left[(Q_{F(x)}\circ
F^{\prime}(x))(\textbf{x}-\textbf{x}_{+})-(F(x)-V^{-1}_{y}(y_{+})F(x_{+}))\right]\|_{x}}{\|\textbf{x}-\textbf{x}_{+}\|_{x}}$
$\displaystyle\overset{}{=}\frac{\|(Q_{F(x)}\circ
F^{\prime}(x))^{-1}V^{-1}_{y}(y_{+})F(x_{+})\|_{x}}{\|\textbf{x}-\textbf{x}_{+}\|_{x}}$

Hence, we can calculate $\theta_{{x}_{+}}({x})$ at the computational cost of
the next simplified Newton direction $\overline{\delta x_{+}}$ for our
original problem with starting point $x_{0}=x_{k}=x$. Namely, this is the
solution $\overline{\delta x_{+}}\in T_{x}\mathcal{X}$ of the equation

$Q_{F(x)}\circ F^{\prime}(x)\overline{\delta
x_{+}}+V^{-1}_{y}(y_{+})F(x_{+})=0_{{y}}.$ (17)

Note, that a vector back-transport is needed here since $Q_{F(x)}\circ
F^{\prime}(x)\overline{\delta x_{+}}$ and $F(x_{+})$ do not lie in the same
fibre. Thus, we can rewrite $\theta_{x_{+}}(x)$ as

$\theta_{{x}_{+}}({x})=\frac{\|\overline{\delta x_{+}}\|_{x}}{\|\delta
x\|_{x}}.$ (18)

######  Lemma 5.12.

Let $F$ be Newton-differentiable at $x_{\star}$ with respect to a Newton
derivative $F^{\prime}$, where $F(x_{\star})=0$. Assume that the operator norm
of $(Q_{F(x)}\circ F^{\prime}(x))^{-1}$ is uniformly bounded by
$\beta<\infty$. Then it holds:

$\lim_{x\to x_{\star}}\theta_{x_{+}}(x)=0.$

###### Proof.

Using that the operator norm of $(Q_{F(x)}\circ F^{\prime}(x))^{-1}$ is
bounded and applying Prop. 5.8, we can estimate $\theta_{{x}_{+}}({x})$ as
follows:

$\displaystyle\theta_{x_{+}}(x)$ $\displaystyle\leq
C\cdot\frac{\|(Q_{F(x)}\circ
F^{\prime}(x))(R_{x}^{-1}(x)-R_{x}^{-1}(x_{+}))-(F(x)-V_{y}^{-1}(y_{+})F(x_{+}))\|_{E_{y}}}{d_{\mathcal{X}}(x,x_{+})}.$

Consider the numerator of $\theta_{x_{+}}(x)$.

$\displaystyle\|(Q_{F(x)}\circ
F^{\prime}(x))(R_{x}^{-1}(x)-R_{x}^{-1}(x_{+}))-(F(x)-V_{y}^{-1}(y_{+})F(x_{+}))\|_{E_{y}}$
$\displaystyle\leq\|(Q_{F(x)}\circ
F^{\prime}(x))(R_{x}^{-1}(x)-R_{x}^{-1}(x_{\star}))-(F(x)-V_{y}^{-1}(y_{\star})F(x_{\star}))\|_{E_{y}}$
$\displaystyle\quad+\|(Q_{F(x)}\circ
F^{\prime}(x))(R_{x}^{-1}(x_{\star})-R_{x}^{-1}(x_{+}))-(V_{y}^{-1}(y_{\star})F(x_{\star})-V_{y}^{-1}(y_{+})F(x_{+}))\|_{E_{y}}$

Since $F$ is Newton-differentiable at $x_{\star}$ and $F(x_{\star})=0$, we can
apply by Prop. 5.9 (i) and obtain

$\|(Q_{F(x)}\circ
F^{\prime}(x))(R_{x}^{-1}(x)-R_{x}^{-1}(x_{\star}))-(F(x)-V_{y}^{-1}(y_{\star})F(x_{\star}))\|_{E_{y}}=o(d_{\mathcal{X}}(x,x_{\star})).$
(19)

Since $V_{y}^{-1}$ is differentiable, $F^{\prime}$, $F$ and $V_{y}^{-1}$ are
locally bounded and $F$ and $y$ are locally Lipschitz continuous, we can
estimate the second summand analogously to the proof of Prop. 5.9 by

$\|(Q_{F(x)}\circ
F^{\prime}(x))(R_{x}^{-1}(x_{\star})-R_{x}^{-1}(x_{+}))-(V_{y}^{-1}(y_{\star})F(x_{\star})-V_{y}^{-1}(y_{+})F(x_{+}))\|_{E_{y}}\leq\widetilde{C}d_{\mathcal{X}}(x_{\star},x_{+}).$
(20)

Since Newton’s method converges superlinearly, we obtain
$d_{\mathcal{X}}(x_{\star},x_{+})=o(d_{\mathcal{X}}(x,x_{\star}))$ as $x\to
x_{\star}$. Thus, combining (19) and (20), the numerator is of order
$o(d_{\mathcal{X}}(x,x_{\star}))$ as $x\to x_{\star}$. Estimating the
denominator of $\theta_{x_{+}}(x)$ by
$d_{\mathcal{X}}(x,x_{+})\geq|d_{\mathcal{X}}(x,x_{\star})-d_{\mathcal{X}}(x_{\star},x_{+})|$,
we obtain the desired result. ∎

## 6\. An Affine Covariant Damping Strategy

In the following we want to develop a method that can also deal with initial
values $x_{0}\in\mathcal{X}$ that are not sufficiently close to the solution.
Especially in Newton’s method applied in optimization on Riemannian manifolds
some strategies including BFGS, Levenberg-Marquardt and trust region methods
were introduced, see e.g. [4, 8, 24]. In a linear setting it is well-known
that damped Newton methods are one way to globalize the convergence of
Newton’s method ([4, 8, 11, 13, 19]). Here, the step size of the Newton
direction is scaled by a factor $\lambda\in(0,1]$. Bortoli et. al. provided a
damped Newton’s method to solve the problem of finding singularities of vector
fields defined on Riemannian manifolds in [5, 6], where A damping factor
$\lambda$ is chosen by a linear line search together with a merit function.

We will also use a damping strategy to globalize our method. The choice of the
damping factor is more geometrically motivated here and follows an affine
covariant strategy in the spirit of Deuflhard [9]. Since we will not use any
Riemannian metric, our way of globalization also works for non-Riemannian
manifolds. To prepare the choice of our damping factor, we first define a so
called Newton path. Our strategy will then be to follow this path by suitably
scaling down the Newton directions until the local convergence area of
Newton’s method is reached.

### 6.1. Newton path

First, we define an algebraic Newton path, a generalization of the Newton path
in linear spaces [9, Sec. 3.1.4]. Denote by $x(0)$ the starting point of the
path. For $\lambda\in[0,1]$ and $x(\lambda)\in\mathcal{X}$ we denote by
$y(\lambda):=p(F(x(\lambda)))$ the base point of $F(x(\lambda))$ on the base
manifold $\mathcal{M}$ of $\mathcal{E}$. Consider a vector back-transport
$V_{y}^{-1}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$. We consider the Newton
path problem, which is based on the idea of scaling down the residual by a
factor of $1-\lambda$:

${\langle{V^{-1}_{y(0)}}\rangle}(F(x(\lambda)))=(1-\lambda)F(x(0)),\;\lambda\in[0,1].$
(21)

In contrast to the case of linear spaces, a vector back-transport is needed
here since $F(x(\lambda))$ and $F(x(0))$ do not lie in the same fibre. The
vector back-transport allows us to formulate the Newton path problem in the
fixed fibre $E_{y(0)}$, i.e. on a linear space. We call $x(\lambda)$ the
algebraic Newton path starting at $x(0)$.

######  Remark 6.1.

For a mapping $g:\mathbb{X}\rightarrow\mathbb{Y}$ between linear spaces
$\mathbb{X}$ and $\mathbb{Y}$ the Newton path is often defined as the solution
of the ordinary differential equation [9, Eq. (3.24)]:

$\frac{dx_{d}(\lambda)}{d\lambda}=-g^{\prime}(x_{d}(\lambda))^{-1}g(x_{d}(0)).$

We may also generalize this idea and define the _differential Newton path_ as
the trajectory of the differential equation

$Q_{F(x_{d}(\lambda))}\circ
F^{\prime}(x_{d}(\lambda))x_{d}^{\prime}(\lambda)+F(x_{d}(\lambda))=0.$ (22)

In contrast to the case of linear spaces the algebraic and the differential
Newton path do not coincide in general.

######  Proposition 6.2.

Assume that $F:\mathcal{X}\to\mathcal{E}$ is strictly differentiable at $x(0)$
and

$\|({\langle{V_{y(0)}^{-1}}\rangle}^{\prime}(F(x(0)))F^{\prime}(x(0)))^{-1}\|_{E_{y(0)}\to
T_{x(0)}\mathcal{X}}$

is finite. Then for sufficiently small $\lambda$ there exists a solution
$x(\lambda)$ of the Newton path problem (21) and the simplified Newton method
locally converges to this solution with a linear rate.

###### Proof.

Application of the implicit function theorem [26], which also holds for
strictly differentiable mappings (cf. e.g. [21, Chap. 25]), on

$g(\lambda,x):={\langle{V^{-1}_{y(0)}}\rangle}(F(x))-(1-\lambda)F(x(0))$

yields the existence of $x(\lambda)$ for sufficiently small $\lambda$ and
convergence of the simplified Newton steps towards $x(\lambda)$. ∎

######  Remark 6.3.

Repeated application of Proposition 6.2, using a homotopy technique yields a
piecewise algebraic Newton path that either ends in a solution $x_{\star}$, at
a point, where the linearization
${\langle{V_{y(0)}^{-1}}\rangle}^{\prime}(F(x(0)))F^{\prime}(x(0))$ is
singular, or at the boundary of the domain of definition of $F$ (cf. the
discussion in [9, Sec. 3.1.4]).

By using the chain rule, we obtain the following expression for the
computation of simplified Newton directions $\overline{\delta x^{\lambda}}\in
T_{x}\mathcal{X}$ at an initial guess $x\in\mathcal{X}$:

${\langle{V_{y(0)}^{-1}}\rangle}^{\prime}(F(x(0)))F^{\prime}(x(0))\overline{\delta
x^{\lambda}}+{\langle{V_{y(0)}^{-1}}\rangle}(F(x))-(1-\lambda)F(x(0))=0.$

Using $V_{y(0)}^{-1}(y(0))=Id_{E_{y(0)}}$, we calculate the first (simplified)
Newton direction $\delta x^{\lambda}$ for the Newton path problem as a
solution of the following equation:

${\langle{V_{y(0)}^{-1}}\rangle}^{\prime}(F(x(0)))F^{\prime}(x(0))\delta
x^{\lambda}+\underbrace{F(x(0))-(1-\lambda)F(x(0))}_{=\lambda F(x(0))}=0.$
(23)

######  Lemma 6.4.

Let $V^{-1}_{y}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$ be consistent with a
linear connection map $Q:T\mathcal{E}\to\mathcal{E}$. Then the damped Newton
direction $\lambda\delta x$ at $x$ of the original problem conicides with the
first Newton direction of the Newton path problem and is tangent to the
algebraic and to the differential Newton path starting at $x(0)=x$. In
particular, we obtain

$\lambda\delta x=\delta x^{\lambda}=\lambda x^{\prime}(0)=\lambda
x_{d}^{\prime}(0).$ (24)

###### Proof.

Consider the Newton path problem (21). Implicit differentiation at $x(0)$ with
respect to $\lambda$ yields the tangent $x^{\prime}(0)$ by

${\langle{V_{y(0)}^{-1}}\rangle}^{\prime}(F(x(0)))F^{\prime}(x(0))x^{\prime}(0)+F(x(0))=0.$

The first (simplified) Newton direction $\delta x^{\lambda}$ for the Newton
path problem with fixed $\lambda$ at the current starting point $x(0)=x$ can
be computed by (23):

${\langle{V_{y(0)}^{-1}}\rangle}^{\prime}(F(x(0)))F^{\prime}(x(0))\delta
x^{\lambda}+\lambda F(x(0))=0.$

Thus, the Newton direction $\delta x^{\lambda}$ for the Newton path problem is
tangent to the algebraic Newton path.

Using the linearity of the connection map $Q$, we can compute the damped
Newton direction $\lambda\delta x$ for our original problem at $x(0)$ by

$Q_{F(x(0))}\circ F^{\prime}(x(0))(\lambda\delta x)+\lambda F(x(0))=0.$

Comparison with (22) yields $\lambda\delta x=x_{d}^{\prime}(0)$. Using the
consistency of $V^{-1}_{y}$ and $Q$ at $e=F(x(0))$, i.e.
$Q_{F(x(0))}={\langle{V_{y(0)}^{-1}}\rangle}^{\prime}(F(x(0)))$, this finally
yields

$\delta x^{\lambda}=\lambda\delta x.$

In particular, the Newton direction $\delta x$ is tangent to the Newton path
at $x(0)$. ∎

### 6.2. Computation of Damping Factors

Lemma 6.4 shows that if we choose the vector back-transport and the connection
map consistent, the first Newton direction for the Newton path problem
coincides with the Newton direction for the original problem scaled by a
damping factor $\lambda\in[0,1]$. If we successively choose the current
iterate $x=x_{k}$ for the starting point $x(0)$ of the Newton path, we obtain
a damped Newton method. More precisely, for a previously computed Newton
direction and a damping factor $\lambda$ we compute the Newton step

$x_{+}=R_{x}(\lambda\delta x).$

For the choice of the damping factor we again consider our Newton path problem
(21). The idea is to choose $\lambda$ sufficiently small such that the
simplified Newton method for solving (21) with starting point $x(0)=x$ is
likely to converge to the target point $x(\lambda)$ on the Newton path. To
monitor the local convergence, we use the estimator $\theta_{x_{+}}({x})$ at
the current iterate $x$ for $\theta_{{x}(\lambda)}({x})$. According to (18)
and using (24), we have to compute

$\theta_{x_{+}}({x})=\theta_{R_{x}(\lambda\delta
x)}({x})=\frac{\|\overline{\delta x_{+}^{\lambda}}\|_{x}}{\|\lambda\delta
x\|_{x}}.$

Thus, we need the next simplified Newton direction $\overline{\delta
x_{+}^{\lambda}}$ for the Newton path problem (21) at initial guess $x$. This
direction is given by the solution of the equation

${\langle{V_{y(x)}^{-1}}\rangle}^{\prime}(F(x))F^{\prime}(x)\overline{\delta
x^{\lambda}_{+}}+V^{-1}_{y(x)}(y(x_{+}))F(x_{+})-(1-\lambda)F(x)=0.$

These calculations are repeated with decreasing damping factor until
$\theta_{x_{+}}({x})<\Theta_{acc}$ for some acceptable contraction
$\Theta_{acc}$ holds. To achieve this, the damping factor $\lambda$ is
readjusted iteratively in the following way. If
$\theta_{x_{+}}({x})\geq\Theta_{acc}$, choose $\lambda_{+}\in(0,1]$ such that
for user defined parameters $0<\Theta_{des}<\Theta_{acc}$ the inequality
$\frac{\lambda_{+}}{\lambda}\cdot\theta_{x_{+}}({x})\leq\Theta_{des}$ holds,
i.e. we compute the next damping factor by

$\lambda_{+}:=\min\left(1,\cfrac{\lambda\Theta_{des}}{\theta_{x_{+}}(x)}\right)$.

We summarise the results in an algorithm, which is a modification of [9, Alg.
NLEQ-ERR]:

Algorithm 2 Affine covariant damped Newton’s method

0: $x,\;\lambda\text{ (initial guesses)};\;\lambda_{fail},\;TOL$,
$\Theta_{des}<\Theta_{acc}$ (parameters)

1: repeat

2: solve $\delta x\leftarrow(Q_{F(x)}\circ F^{\prime}(x))\delta x+F(x)=0$

3: repeat

4: compute $x_{+}=R_{x}(\lambda\delta x)$

5: solve $\overline{\delta
x^{\lambda}_{+}}\leftarrow{\langle{V_{y(x)}^{-1}}\rangle}^{\prime}(F(x))F^{\prime}(x)\overline{\delta
x^{\lambda}_{+}}+V^{-1}_{y(x)}(y(x_{+}))F(x_{+})-(1-\lambda)F(x)=0$

6: compute $\theta_{x_{+}}(x)=\cfrac{\|\overline{\delta
x_{+}^{\lambda}}\|_{x}}{\|\lambda\delta x\|_{x}}$

7: update
$\lambda\leftarrow\min\left(1,\cfrac{\lambda\Theta_{des}}{\theta_{x_{+}}(x)}\right)$

8: if $\lambda<\lambda_{fail}$ then

9: terminate: “Newton’s method failed“

10: end if

11: until $\theta_{x_{+}}(x)\leq\Theta_{acc}$

12: update $x\leftarrow x_{+}$

13: if $\lambda=1\text{ and }\theta_{x_{+}}(x)\leq\frac{1}{4}\text{ and
}\|\delta x\|_{x}\leq TOL$ then

14: terminate: “Desired Accuracy reached“, $x_{out}=x_{+}$

15: end if

16: until maximum number of iterations is reached

######  Proposition 6.5.

Let $F$ be strictly differentiable at $x$ and $V^{-1}_{y}$ be consistent with
$Q$. Then there exists $\widehat{\lambda}>0$ such that

$\forall\lambda\leq\widehat{\lambda}\;:\;\theta_{R_{x}(\lambda\delta
x)}(x)\leq\Theta_{acc},$

and thus the inner loop terminates after finitely many iterations.

###### Proof.

If $\theta_{R_{x}(\lambda\delta x)}(x)>\Theta_{acc}$, we obtain

$\lambda_{+}\leq\cfrac{\lambda\Theta_{des}}{\theta_{R_{x}(\lambda\delta
x)}(x)}\leq\frac{\Theta_{des}}{\Theta_{acc}}\lambda.$

Since $\Theta_{des}<\Theta_{acc}$, this yields
$\lambda_{+}<C\cdot\lambda\text{ with }C<1$. Now choose $\widehat{\lambda}>0$
sufficiently small such that the Newton path with starting point $x(0)=x$
exists (Prop. 6.2). Since

$\theta_{R_{x}(\lambda\delta x)}({x})=\frac{\|\overline{\delta
x_{+}^{\lambda}}\|_{x}}{\|\delta x^{\lambda}\|_{x}}.$

measures the ratio between the first and second simplified Newton step for the
Newton path problem and the simplified Newton method converges locally to
$x(\lambda)$, we obtain

$\theta_{R_{x}(\lambda\delta
x)}(x)\leq\Theta_{acc}\;\forall\lambda\leq\widehat{\lambda}.$

∎

######  Remark 6.6.

By the choice of $\Theta_{des}\in]0,1[$ it is possible to adjust how
aggressive the step size strategy acts. If $\Theta_{des}\approx 0$, then
Newton’s method follows the Newton path very closely and takes short steps. If
$\Theta_{des}\approx 1$, then larger steps will be taken, but the methods
might perform less robustly for highly nonlinear problems. The choices
$\Theta_{des}=0.5$ and $\Theta_{acc}=1.1\Theta_{des}$ work well in practice.

## 7\. Applications

In this section we discuss the two simplest applications of Newton’s method on
vector bundles. First, the tangent bundle of a Banach manifold $\mathcal{X}$
is considered. Like in [6, 2], Newton’s method is then used to find fixed
points of vector fields $\nu\in\Gamma(T\mathcal{X})$. Second, considering the
_cotangent bundle_ $T^{*}\mathcal{X}$, Newton’s method can also be applied in
optimization on manifolds and to find stationary points of _covector fields_.

If $\mathcal{X}$ is a Riemannian manifold, in both applications the _Levi-
Civita connection_ (see e.g. [13]) is often used to compute the Newton
direction. This connection induces the parallel transport along geodesics and
the exponential map. Computing these classical parallel transports can be
computationally very expensive. Thus, instead of starting with a connection
and deriving a vector transport from it, we take the opposite route. We start
with a computationally tractable vector back-transport
$V^{-1}_{y}\in\Gamma(\mathcal{L}(\mathcal{E},E_{y}))$, and derive a consistent
connection $Q$ by differentiation. Consistency is needed to apply our
globalization strategy. Since retractions are anyway used in algorithms, we
will discuss how vector transports on $T\mathcal{X}$ and $T^{*}\mathcal{X}$
can be derived from retractions.

### 7.1. Fixed points of vector fields

Consider the tangent bundle $\pi:T\mathcal{X}\to\mathcal{X}$ of a Banach
manifold $\mathcal{X}$ and a vector field $\nu\in\Gamma(T\mathcal{X})$, i.e.
$\nu:\mathcal{X}\to T\mathcal{X}$ with $\pi(\nu(x))=x\;\forall
x\in\mathcal{X}$. Our aim is to apply Newton’s method on $\nu:\mathcal{X}\to
T\mathcal{X}$ to compute a zero $x\in\mathcal{X}$ of the vector field, i.e. a
point $x\in\mathcal{X}$ such that

$\nu(x)=0_{x}\in T_{x}\mathcal{X}.$

The computation of the Newton direction requires a connection map
$Q:T(T\mathcal{X})\to T\mathcal{X}$, which we define with the help of a vector
back-transport
$V^{-1}_{x}\in\Gamma(\mathcal{L}(T\mathcal{X},T_{x}\mathcal{X}))$. As seen
before in Lemma 2.3, differentiating ${\langle{V_{x}^{-1}}\rangle}\in
C^{1}(T\mathcal{X},T_{x}\mathcal{X})$, leads to the consistent connection map
at $\nu(x)\in T\mathcal{X}$ with $\pi(\nu(x))=x$:

$Q_{\nu(x)}:={\langle{V^{-1}_{x}}\rangle}^{\prime}(\nu(x)):T_{\nu(x)}(T\mathcal{X})\to
T_{x}\mathcal{X}.$

#### Vector back-transports derived from retractions.

From a numerical point of view, a natural way to generate vector transports on
the tangent bundle $\pi:T\mathcal{X}\to\mathcal{X}$ is by differentiating
retractions $R:T\mathcal{X}\to\mathcal{X}$, which are anyway required to
define the Newton step.

Keeping $x\in\mathcal{X}$ fixed, the derivative of $R_{x}$ at a point $v\in
T_{x}\mathcal{X}$ is a linear mapping

$R^{\prime}_{x}(v):T_{x}\mathcal{X}\to T_{R_{x}(v)}\mathcal{X}.$

Since $R_{x}(0_{x})=x$ and $R^{\prime}_{x}(0_{x})=Id_{T_{x}\mathcal{X}}$
holds, we can also view this as a section

$V_{x}\in\Gamma(\mathcal{L}(\mathcal{X}\times
T_{x}\mathcal{X},T\mathcal{X}))\;\text{ by
}V_{x}(\xi):=R_{x}^{\prime}(R_{x}^{-1}(\xi)),$ (25)

i.e. a vector transport. Using
$(R_{x}^{-1})^{\prime}(x)=Id_{T_{x}\mathcal{X}}$ we compute in trivializations
$(V_{x,\tau}^{\prime}(x)\delta
x)v_{\tau}=R_{x,\tau}^{\prime\prime}(0_{x})(\delta x,v_{\tau})$, or in short:

$V_{x,\tau}^{\prime}(x)=R_{x,\tau}^{\prime\prime}(0_{x})\in
L(T_{x}\mathcal{X},L(\mathbb{X},\mathbb{X})).$

The corresponding vector back-transport is defined by the inverse of the
derivative of the retraction, i.e. we compute:

$V_{x}^{-1}(\xi):=R_{x}^{\prime}(R_{x}^{-1}(\xi))^{-1}:T_{\xi}\mathcal{X}\to
T_{x}\mathcal{X},$

######  Remark 7.1.

In the Newton iteration we use $\xi=x_{+}=R_{x}(\delta x)$, and thus
$R_{x}^{-1}(\xi)=\delta x$. Hence, $V_{x}^{-1}(\xi)=R_{x}^{\prime}(\delta x)$,
and the inverse retraction is not needed for the evaluation of the vector
back-transport.

Lemma 2.3 allows us to define a connection via the natural inclusion:

$Q_{v}={\langle{V^{-1}_{x}}\rangle}^{\prime}(v):T_{v}(T\mathcal{X})\to
T_{x}\mathcal{X}.$

By (5) we get $R_{x,\tau}^{\prime\prime}(0_{x})(\delta
x,v_{\tau})=B_{x,\tau}(v_{\tau})\delta x$ and thus for $\delta v\sim(\delta
x,\delta v_{\tau})$:

$Q_{v}\delta v\sim Q_{v,\tau}(\delta x,\delta v_{\tau})=\delta
v_{\tau}-R_{x,\tau}^{\prime\prime}(0_{x})(\delta x,v_{\tau}).$ (26)

#### Embedded submanifolds.

If $\mathcal{X}$ is an embedded submanifold of a Hilbert space $H$ we can use
the embedding $E_{H}:T\mathcal{X}\to H$ with $E_{H}(\xi):T_{\xi}\mathcal{X}\to
H$ and the orthogonal projection $P(x):H\to T_{x}\mathcal{X}$ on the tangent
space to define a vector back-transport locally by

$\displaystyle V_{x}^{-1}(\xi):=P(x)E_{H}(\xi)\in
L(T_{\xi}\mathcal{X},T_{x}\mathcal{X})$

Consider a vector field $\nu:\mathcal{X}\to T\mathcal{X}$. By our natural
inclusion $\varphi$, we obtain the $C^{1}$-mapping
${\langle{V_{x}^{-1}}\rangle}:T\mathcal{X}\to T_{x}\mathcal{X}$ with
${\langle{V_{x}^{-1}}\rangle}(\nu)(\xi)=P(x)(E_{H}\nu)(\xi)$. Differentiating
this with respect to $\xi$ at $\xi=x$, we obtain

$Q_{\nu(x)}\nu^{\prime}(x)\delta
x={\langle{V_{x}^{-1}}\rangle}^{\prime}(\nu(x))\nu^{\prime}(x)\delta
x=P(x)(E_{H}\nu)^{\prime}(x)\delta x\in T_{x}\mathcal{X},$

which defines the consistent connection map
$Q_{\nu(x)}={\langle{V_{x}^{-1}}\rangle}^{\prime}(\nu(x))$. The _covariant
derivative_ $Q\circ\nu^{\prime}$ of a vector field $\nu$ w.r.t. the connection
map $Q$ can therefore be determined by projecting the euclidean directional
derivatives onto $T\mathcal{X}$ by the orthogonal projection. The connection
which belongs to this covariant derivative is sometimes called tangential
connection. It actually defines the Levi-Civita connection on $T\mathcal{X}$,
see e.g. [14, Chap. 5].

### 7.2. Variational problems on manifolds

Consider a twice differentiable function $f:\mathcal{X}\rightarrow\mathbb{R}$,
defined on a Banach manifold $\mathcal{X}$. In order to find a critical point,
we want to apply Newton’s method on the _cotangent bundle_ $T^{*}\mathcal{X}$
to compute a zero of the _covector field_ $f^{\prime}:\mathcal{X}\rightarrow
T^{*}\mathcal{X}$, i.e. a point $x\in\mathcal{X}$ such that

$f^{\prime}(x)=0_{x}^{*}\in T_{x}\mathcal{X}^{*}.$

Thus, we need a _dual connection map_
$Q_{f^{\prime}(x)}^{*}:T_{f^{\prime}(x)}(T^{*}\mathcal{X})\rightarrow
T_{x}^{*}\mathcal{X}$ on the _dual bundle_ $T^{*}\mathcal{X}$. Again, such a
connection map can be derived from a vector transport. We will first discuss
dual connection maps in general and come back to the cotangent bundle
afterwards.

#### Dual vector bundles and dual connections.

Let $p:\mathcal{E}\to\mathcal{M}$ be a vector bundle. The _dual bundle_
$p^{*}:\mathcal{E}^{*}\to\mathcal{M}$ is defined as a vector bundle with
fibres via $(p^{*})^{-1}(y)=E_{y}^{*}$, i.e. the dual space of $E_{y}$. We can
view this as a special case
$\mathcal{E}^{*}=\mathcal{L}(\mathcal{E},\mathcal{M}\times\mathbb{R})$. For
example the dual bundle of the tangent bundle $T\mathcal{X}$ is the cotangent
bundle $T^{*}\mathcal{X}$.

We denote the dual pairing for $\ell\in\Gamma(\mathcal{E}^{*})$ and
$e\in\Gamma(\mathcal{E})$ by $\ell(e):\mathcal{M}\rightarrow\mathbb{R}$. Its
derivative at a point $y\in\mathcal{M}$ is given by
$\ell(e)^{\prime}(y):T_{y}\mathcal{M}\to\mathbb{R}$. If $\mathcal{E}$ admits a
connection map it is possible to define a dual connection map on the dual
bundle $\mathcal{E}^{*}$ as follows [14, Chap. 4].

######  Definition 7.2.

Let $Q$ be a connection map on the vector bundle
$p:\mathcal{E}\rightarrow\mathcal{M}$. The _dual connection map_
$Q^{*}:T\mathcal{E}^{*}\to\mathcal{E}^{*}$ on the dual vector bundle
$p^{*}:\mathcal{E}^{*}\rightarrow\mathcal{M}$ is defined by

$((Q^{*}\circ\ell^{\prime})(y)\delta y)(e):=\ell(e)^{\prime}(y)\delta
y-\ell((Q\circ e^{\prime})(y)\delta y)\;\forall
e\in\Gamma(\mathcal{E}),\;\forall\delta y\in T_{y}\mathcal{M}$

In trivializations the connection map $Q$ is represented as in (3) by

$Q_{e}\delta e\sim Q_{e,\tau}(\delta y,\delta e_{\tau})=\delta
e_{\tau}-B_{y,\tau}(e_{\tau})\delta y\in\mathbb{E}.$ (27)

Using this, and the representation of $\ell^{\prime}(y)\delta y$ by $(\delta
y,\delta\ell_{\tau})$ and $e^{\prime}(y)\delta y$ by $(\delta y,\delta
e_{\tau})$ we obtain by the product rule and cancellation of the term
$\ell_{\tau}(\delta e_{\tau})(y)\delta y$:

$\displaystyle((Q_{\ell,\tau}^{*}\circ\ell_{\tau}^{\prime})(y)\delta
y)(e_{\tau}(y))$
$\displaystyle=\ell_{\tau}(e_{\tau})^{\prime}(y)-\ell_{\tau}(y)(\delta
e_{\tau}-B_{y,\tau}(e_{\tau}(y))\delta y)$
$\displaystyle=\delta\ell_{\tau}(e_{\tau}(y))+\ell_{\tau}(y)(B_{y,\tau}(e_{\tau}(y))\delta
y).$

Thus, $(Q^{*}\circ\ell^{\prime})(y)\delta y)(e)$ does not depend on
$e_{\tau}^{\prime}(y)$, but on $e_{\tau}(y)$ only, so indeed
$(Q^{*}\circ\ell^{\prime})(y)\delta y\in E_{y}^{*}$ with the representation

$Q^{*}_{\ell}\delta\ell\sim Q^{*}_{\ell,\tau}(\delta
y,\delta\ell_{\tau})=\delta\ell_{\tau}(\cdot)+\ell\circ
B_{y,\tau}(\cdot)\delta y\in\mathbb{E}^{*}.$ (28)

Comparison of (27) and (28) shows that if the dual connection map $Q^{*}$
corresponds to a connection map $Q$ on $\mathcal{E}$ the bilinear form
$B_{y,\tau}$ is used in both representations.
Now consider a vector transport
$V_{y}\in\Gamma(\mathcal{L}(\mathcal{M}\times\mathcal{E},E_{y})$. We can
define a _covector back-transport_
$V_{y}^{*}\in\Gamma(\mathcal{L}(\mathcal{E}^{*},E_{y}^{*}))$, which acts as a
vector back-transport on the dual bundle by using pointwise adjoints
$V_{y}^{*}(\hat{y}):=(V_{y}(\hat{y}))^{*}\in L(E_{\hat{y}}^{*},E_{y}^{*})$,
i.e.

$V_{y}^{*}(\hat{y})\ell:=\ell\circ V_{y}(\hat{y})\quad\forall\ell\in
E_{\hat{y}}^{*}.$

We can define a connection map on $\mathcal{E}^{*}$ via the covector back-
transport by setting

$Q_{\ell}^{*}:={\langle{V^{*}_{y}}\rangle}^{\prime}(\ell):T_{\ell}\mathcal{E}^{*}\to
E^{*}_{y},\;y=p^{*}(\ell).$ (29)

######  Lemma 7.3.

The choice (29) defines the dual connection map on $\mathcal{E}^{*}$
corresponding to the connection map
$Q_{e}={\langle{V_{y}^{-1}}\rangle}^{\prime}(e)$ at $e$ with
$y=p(e)=p^{*}(\ell)$ on $\mathcal{E}$ derived from the vector transport
$V_{y}$.

###### Proof.

Let $\ell\in\Gamma(\mathcal{E}^{*})$, $e\in\Gamma(\mathcal{E})$, and $\delta
y\in T_{y}\mathcal{M}$. In trivializations, if $\ell(y)$ is represented by
$(y,\ell_{\tau}(y))$ and $\ell^{\prime}(y)\delta y$ by $(\delta
y,\delta\ell_{\tau})$, we obtain by using
${\langle{V_{y}^{*}}\rangle}(\ell)=\ell\circ V_{y}(p^{*}(\ell))$ and (2):

${\langle{V_{y}^{*}}\rangle}^{\prime}(\ell(y))\ell^{\prime}(y)\delta
y\sim\delta\ell_{\tau}+\ell\circ V_{y,\tau}^{\prime}(y)\delta y.$

Since $B_{y,\tau}(e_{\tau}(y))\delta y=-((V_{y,\tau}^{-1})^{\prime}(y)\delta
y)e_{\tau}(y)=(V_{y,\tau}^{\prime}(y)\delta y)e_{\tau}(y)$ by (4) and (5), we
obtain the desired result. ∎

######  Remark 7.4.

Classically, connections are closely related to covariant derivatives:

$\nabla_{\delta y}e(y):=Q\circ e^{\prime}(y)\delta y\mbox{ for
}y\in\mathcal{M},e\in\Gamma(\mathcal{E}),\delta y\in\Gamma(T\mathcal{M}),$

in which case Definition 7.2 yields a product rule:

$\ell(e)^{\prime}(y)\delta y=\nabla_{\delta
y}^{*}\ell(y)(e)+\ell(\nabla_{\delta y}e(y)).$

On Riemannian manifolds the Levi-Civita connection is widely used on
$T\mathcal{M}$. In this case, dual connections can also be defined with the
help of a Riesz isomorphism $\mathcal{R}:T\mathcal{M}\to T^{*}\mathcal{M}$:

$\nabla_{\delta y}^{*}\ell:=\mathcal{R}(\nabla_{\delta
y}\mathcal{R}^{-1}(\ell)).$

However, this expression is often expensive to evaluate numerically.

#### Covector back-transports via retractions.

Consider the cotangent bundle $\pi^{*}:T^{*}\mathcal{X}\to\mathcal{X}$. Since
the cotangent bundle is the dual vector bundle to the tangent bundle it admits
a corresponding dual connection map. In order to define the dual connection
map which fits to the connection map on $T\mathcal{X}$ induced by the
retraction, we first define the covector back-transport corresponding to
$V_{x}\in\Gamma(\mathcal{X}\times T_{x}\mathcal{X},T\mathcal{X})$ given by
(25). For $v^{*}\in T_{\xi}^{*}\mathcal{X}$ we set

$V^{*}_{x}(\xi)(v^{*}):=v^{*}\circ
R_{x}^{\prime}(R_{x}^{-1}(\xi))=R_{x}^{\prime}(R_{x}^{-1}(\xi))^{*}(v^{*})\in
T_{x}^{*}\mathcal{X}.$

Thus, we obtain a linear mapping

$V^{*}_{x}(\xi)=R_{x}^{\prime}(R_{x}^{-1}(\xi))^{*}:T^{*}_{\xi}\mathcal{X}\rightarrow
T_{x}^{*}\mathcal{X},$

which defines a covector back-transport
$V_{x}^{*}\in\Gamma(\mathcal{L}(T^{*}\mathcal{X},T_{x}^{*}\mathcal{X}))$ on
the cotangent bundle.

By using the natural inclusion $\varphi$ and differentiating
${\langle{V_{x}^{*}}\rangle}$, we obtain the dual connection map at $v^{*}\in
T^{*}\mathcal{X}$ with $x=\pi^{*}(v^{*})\in\mathcal{X}$:

$Q_{v^{*}}^{*}:={\langle{V^{*}_{x}}\rangle}^{\prime}(v^{*}):T_{v^{*}}(T^{*}\mathcal{X})\rightarrow
T_{x}^{*}\mathcal{X}.$

Combining (26) and (28) we obtain in trivializations

$Q^{*}_{v^{*}}\delta v^{*}\sim Q^{*}_{v^{*},\tau}(\delta x,\delta
v^{*}_{\tau})=\delta v^{*}_{\tau}+v^{*}_{\tau}\circ
R^{\prime\prime}_{x,\tau}(0_{x})(\delta x,\cdot).$ (30)

#### Embedded submanifolds.

Consider an embedded submanifold $\mathcal{X}$ of a Hilbert space $H$. We can
use the embedding $E_{H}:T\mathcal{X}\to H$ with $E_{H}(x):T_{x}\mathcal{X}\to
H$ and the orthogonal projection $P(\xi):H\to T_{\xi}\mathcal{X}$ on the
tangent space to define a vector transport locally by

$V_{x}(\xi):=P(\xi)E_{H}(x)\in L(T_{x}\mathcal{X},T_{\xi}\mathcal{X}).$

A covector back-transport is then given by taking pointwise adjoints
$V_{x}^{*}(\xi):=(V_{x}(\xi))^{*}$, i.e.

$V^{*}_{x}(\xi)\ell=\ell\circ V_{x}(\xi)=\ell\circ P(\xi)\circ
E_{H}(x)\quad\forall\ell\in T_{\xi}^{*}\mathcal{X}.$

Consider a covector field $\ell_{H}:\mathcal{X}\to H^{*}$ and its restriction
$\ell\in T^{*}\mathcal{X}$, given by $\ell(\xi):=\ell_{H}(\xi)\circ
E_{H}(\xi)$. Differentiating
${\langle{V_{x}^{*}}\rangle}(\ell)(\xi)=\ell_{H}(\xi)\circ E_{H}(\xi)\circ
V_{x}(\xi)$ with respect to $\xi$ at $\xi=x$ yields

$\displaystyle{\langle{V_{x}^{*}}\rangle}^{\prime}(\ell(x))\ell^{\prime}(x)\delta
x$ $\displaystyle=\ell_{H}^{\prime}(x)\delta x+\ell_{H}(x)(E_{H}\circ
V_{x})^{\prime}(x)\delta x$ $\displaystyle=\ell_{H}^{\prime}(x)\delta
x+\ell_{H}(x)(E_{H}\circ P)^{\prime}(x)E_{H}(x)\delta x,$

or, suppressing the embeddings notationally:

$\displaystyle Q^{*}_{\ell(x)}\ell^{\prime}(x)\delta
x={\langle{V_{x}^{*}}\rangle}^{\prime}(\ell(x))\ell^{\prime}(x)\delta
x=\ell_{H}^{\prime}(x)\delta x+\ell_{H}(x)P^{\prime}(x)\delta x\in
T^{*}_{x}\mathcal{X}.$ (31)

Vice versa, if $\ell\in T^{*}\mathcal{X}$ is given, we may extend $\ell$ to
$\ell_{H}:\mathcal{X}\to H^{*}$, for example by specifying $\ell_{H}(x)$ on
$T_{x}\mathcal{X}^{\perp}$. Then by its intrinsic definition
$Q^{*}_{\ell(x)}\ell^{\prime}(x)\delta x$ is independent of the extension, and
thus also (31) is independent of the extension.

If $\mathcal{X}$ is given by a _constraint_ of the form $\mathcal{X}=\\{x\in
H:c(x)=0\\}$, where $c:H\to R$ is a differentiable mapping between Hilbert
spaces, such that $c^{\prime}(x):H\to R$ is surjective, then we can find a
_Lagrangian multiplier_ $\lambda(x)\in R^{*}$, such that
$(\ell_{H}(x)+\lambda(x)c^{\prime}(x))w=0$ for all $w\in
T_{x}\mathcal{X}^{\perp}$. Using
$\mathrm{ker}\,c^{\prime}(x)=T_{x}\mathcal{X}$ this relation can be written as

$0=(\ell_{H}(x)+\lambda(x)c^{\prime}(x))(Id_{H}-P(x))v=\ell_{H}(x)(Id_{H}-P(x))v+\lambda(x)c^{\prime}(x)v\quad\forall
v\in H.$

Differentiation with respect to $x$ in direction $\delta x\in
T_{x}\mathcal{X}$ yields

$0=(\ell_{H}^{\prime}(x)\delta x(Id_{H}-P(x))-\ell_{H}(x)P^{\prime}(x)\delta
x+\lambda^{\prime}(x)\delta
x\,c^{\prime}(x)+\lambda(x)c^{\prime\prime}(x)\delta x)v\quad\forall v\in H$

and thus, testing with $v\in T_{x}\mathcal{X}$, so that $(Id_{H}-P(x))v=0$ and
$c^{\prime}(x)v=0$, we get:

$\lambda(x)c^{\prime\prime}(x)(\delta x,v)=\ell_{H}(x)P^{\prime}(x)\delta
x\,v\quad\forall v\in T_{x}\mathcal{X}.$

Hence, (31) reads in this case:

$\displaystyle Q^{*}_{\ell(x)}\ell^{\prime}(x)\delta
x=\ell_{H}^{\prime}(x)\delta x+\lambda(x)c^{\prime\prime}(x)\delta x\in
T^{*}_{x}\mathcal{X}.$ (32)

#### Newton’s method and optimization.

Given a dual connection map
$Q_{f^{\prime}(x)}^{*}:T_{f^{\prime}(x)}(T^{*}\mathcal{X})\rightarrow
T_{x}^{*}\mathcal{X}$, we can determine the Newton direction $\delta x\in
T_{x}\mathcal{X}$ to find a zero of the covector field
$f^{\prime}:\mathcal{X}\rightarrow T^{*}\mathcal{X}$ by solving the following
equation in $T_{x}^{*}\mathcal{X}$:

$Q_{f^{\prime}(x)}^{*}\circ f^{\prime\prime}(x)\delta
x+f^{\prime}(x)=0_{x}^{*}.$ (33)

Since this is an equation in a dual space, $\delta x$ has to fulfill

$(Q^{*}_{f^{\prime}(x)}\circ f^{\prime\prime}(x)\delta
x)v+f^{\prime}(x)v=0\quad\forall v \in T_{x}\mathcal{X}.$

Alternatively, we can use a second order model of the pullback $f\circ
R_{x}:T_{x}\mathcal{X}\to\mathbb{R}$ of $f$ at $x$ with respect to the same
retraction:

$(f\circ R_{x})(0_{x}+\delta x)=f(x)+(f\circ R_{x})^{\prime}(0_{x})\delta
x+\frac{1}{2}(f\circ R_{x})^{\prime\prime}(0_{x})(\delta x,\delta
x)+o(\|\delta x\|_{x}^{2}).$

If $(f\circ R_{x})^{\prime\prime}(0_{x})$ is positive definite, then a Newton-
SQP direction can be computed by

$\min_{\delta x\in T_{x}\mathcal{X}}\;(f\circ R_{x})^{\prime}(0_{x})\delta
x+\frac{1}{2}(f\circ R_{x})^{\prime\prime}(0_{x})(\delta x,\delta
x)\quad\Leftrightarrow\quad(f\circ R_{x})^{\prime\prime}(0_{x})\delta
x+(f\circ R_{x})^{\prime}(0_{x})=0_{x}^{*}.$ (34)

######  Proposition 7.5.

Let $x\in\mathcal{X}$. Let $Q^{*}:T(T^{*}\mathcal{X})\to T^{*}\mathcal{X}$ be
a dual connection map derived from a retraction
$R_{x}:T_{x}\mathcal{X}\to\mathcal{X}$. Then

$\displaystyle(f\circ R_{x})^{\prime}(0_{x})$ $\displaystyle=f^{\prime}(x),$
$\displaystyle(f\circ R_{x})^{\prime\prime}(0_{x})$
$\displaystyle=Q_{f^{\prime}(x)}^{*}\circ f^{\prime\prime}(x).$

Thus, the Newton direction computed by (33) coincides with the Newton-SQP
direction computed by (34) if $(f\circ R_{x})^{\prime\prime}(0_{x})$ is
positive definite.

###### Proof.

Let $v\in T_{x}\mathcal{X}$. Using that $R_{x}$ is a retraction, we obtain:

$(f\circ
R_{x})^{\prime}(0_{x})v=f^{\prime}(R_{x}(0_{x}))R_{x}^{\prime}(0_{x})v=f^{\prime}(x)v.$

Next, we have for $\delta x\in T_{x}\mathcal{X}$

$(f\circ R_{x})^{\prime\prime}(0_{x})(\delta
x,v)=\frac{d}{d\xi}\left(f^{\prime}(R_{x}(\xi))R^{\prime}_{x}(\xi)\delta
x\right)|_{\xi=0_{x}}v.$

Consider the trivializations
$\tau_{T\mathcal{X}}:T\mathcal{X}\to\mathcal{X}\times\mathbb{X}$ and
$\tau_{x}:\mathcal{X}\times T_{x}\mathcal{X}\to\mathcal{X}\times\mathbb{X}$.
Using (1), we compute for $\xi\in T_{x}\mathcal{X}$:

$\displaystyle f^{\prime}_{\tau}(R_{x}(\xi))R_{x,\tau}^{\prime}(\xi)\delta
x\circ\tau_{x}=(f^{\prime}(R_{x}(\xi))\circ\tau_{T\mathcal{X}}^{-1})\circ(\tau_{T\mathcal{X}}\circ
R_{x}^{\prime}(\xi)\delta
x\circ\tau_{x}^{-1})\circ\tau_{x}=f^{\prime}(R_{x}(\xi))R_{x}^{\prime}(\xi)\delta
x.$

On the one hand, computing the derivative at $\xi=0_{x}$ yields, with
$(R^{\prime}_{x,\tau}(0_{x})\circ\tau_{x})(v)=\tau_{x}(v)=v_{\tau}$ for $v\in
T_{x}\mathcal{X}$:

$\displaystyle\frac{d}{d\xi}\left(f^{\prime}_{\tau}(R_{x}(\xi))R_{x,\tau}^{\prime}(\xi)\delta
x\circ\tau_{x}\right)|_{\xi=0_{x}}v=f^{\prime\prime}_{\tau}(x)(\delta
x,v_{\tau})+f^{\prime}_{\tau}(x)R^{\prime\prime}_{x,\tau}(0_{x})(\delta
x,v_{\tau}).$

On the other hand, in trivializations we get with (30), using
$v^{*}=f^{\prime}(x)$ and $\delta v^{*}\sim(\delta
x,f_{\tau}^{\prime\prime}(x)\delta x)$:

$(Q_{f^{\prime}(x)}^{*}\circ f^{\prime\prime}(x)\delta
x)v=f_{\tau}^{\prime\prime}(x)(\delta x,v_{\tau})+f_{\tau}^{\prime}(x)\circ
R_{x,\tau}^{\prime\prime}(0_{x})(\delta x,v_{\tau}).$

This yields

$(f\circ R_{x})^{\prime\prime}(0_{x})\delta x=Q_{f^{\prime}(x)}^{*}\circ
f^{\prime\prime}(x)\delta x\text{ in }T_{x}^{*}\mathcal{X}.$

Since $\delta x$ is an arbitrary tangent vector it holds that

$(f\circ R_{x})^{\prime\prime}(0_{x})=Q_{f^{\prime}(x)}^{*}\circ
f^{\prime\prime}(x).$

Thus, the Newton equation (33) and the optimality constraint (34) coincide. ∎

######  Remark 7.6.

Our affine covariant damping strategy is well suited to find stationary points
of $f$. If the computation of a local minimizer of $f$ is desired, different
strategies from nonlinear optimization should be employed, such as linesearch
or trust-region methods, that enforce descent in $f$ during the iteration.

If $\mathcal{X}$ is embedded into a Hilbert space $H$, $f_{H}:H\to\mathbb{R}$
and $f=f_{H}|_{\mathcal{X}}$, we may consider the constrained problem

$\min_{x\in\mathcal{X}}f(x)\quad\Leftrightarrow\quad\min_{x\in
H}f_{H}(x)\;\text{ subject to }\;x\in\mathcal{X}.$

A stationary point is then given as $x\in\mathcal{X}$, such that
$f^{\prime}(x)v=f_{H}^{\prime}(x)v=0$ for all $v\in T_{x}\mathcal{X}$. Then in
view of (31) we obtain for the connection, induced by the orthogonal
projection:

$Q^{*}_{f^{\prime}(x)}f^{\prime\prime}(x)\delta
x=f_{H}^{\prime\prime}(x)\delta x+f_{H}^{\prime}(x)P^{\prime}(x)\delta x.$

In the case $\mathcal{X}=\\{x\in H:c(x)=0\\}$ this relation becomes

$Q^{*}_{f^{\prime}(x)}f^{\prime\prime}(x)\delta
x=f_{H}^{\prime\prime}(x)\delta x+\lambda(x)c^{\prime\prime}(x)\delta x.$

where $(f^{\prime}_{H}(x)+\lambda(x)c^{\prime}(x))v=0$ for all $v\in
T_{x}\mathcal{X}$ due to (32). Hence, in this case we retain the well known
Lagrange-Newton step, used in constrained optimization.

## 8\. Conclusion and future research

In our study of Newton’s method for a mapping $F:\mathcal{X}\to\mathcal{E}$
from a manifold into a vector bundle we have found a number of structural
insights. The most basic distinction from the classical case is the need for a
connection on $\mathcal{E}$ to render the Newton equation well defined.
Together with a geometric version of Newton differentiability this already
allows a local convergence theory of Newton’s method. A Banach type version of
a Riemannian metric can be used as a flexible framework to formulate
superlinear convergence.

For the development of further algorithmic strategies, like monitoring local
convergence or globalization, vector back-transports are required. They make
it possible to compare residuals from different fibres and to compute
simplified Newton steps. We propose an affine covariant globalization scheme,
which works purely with quantities that can be computed in terms of the domain
$\mathcal{X}$. In the global regime, where residuals are not small, it is
necessary that the employed connection is consistent with the vector back-
transport in order to guarantee that the Newton direction is tangential to the
algebraic Newton path. If $\mathcal{E}$ is the tangent bundle $T\mathcal{X}$
or the cotangent bundle $T^{*}\mathcal{X}$, then vector back-transports and
connections can be derived from retractions on $\mathcal{X}$ by
differentiation. In this way an algorithmic quantity on $\mathcal{X}$, a
retraction, induces some geometric structure on $\mathcal{X}$, namely a
connection.

Our general approach can be used to tackle various classes of problems
numerically, posed on manifolds of finite and infinite dimension and thus
opens the door for future research. Possible applications are the simulation
and optimal control of geometric variational problems and differential
equations, problems of stationary action, or shape optimization. Depending on
the structure of the problem, alternative globalization schemes can be
devised, for example, residual based schemes or descent methods from nonlinear
optimization.

## References

  * [1] P-A Absil, Robert Mahony, and Rodolphe Sepulchre.  Optimization algorithms on matrix manifolds.  Princeton University Press, 2008.
  * [2] Ioannis K Argyros and Saïd Hilout.  Newton’s method for approximating zeros of vector fields on Riemannian manifolds.  Journal of Applied Mathematics and Computing, 29:417–427, 2009.
  * [3] Ronny Bergmann, Roland Herzog, Julián Ortiz López, and Anton Schiela.  First-and second-order analysis for optimization problems with manifold-valued constraints.  Journal of Optimization Theory and Applications, 195(2):596–623, 2022.
  * [4] Dimitri P Bertsekas.  Constrained optimization and Lagrange multiplier methods.  Academic press, 2014.
  * [5] MAA Bortoloti, Teles A Fernandes, and Orizon P Ferreira.  An efficient damped Newton-type algorithm with globalization strategy on Riemannian manifolds.  Journal of Computational and Applied Mathematics, 403:113853, 2022.
  * [6] Marcio Antônio de A Bortoloti, Teles A Fernandes, Orizon P Ferreira, and Jinyun Yuan.  Damped Newton’s method on Riemannian manifolds.  Journal of Global Optimization, 77:643–660, 2020.
  * [7] Deckelnick, Klaus, Herbert, Philip J., and Hinze, Michael.  A novel w1,∞ approach to shape optimisation with lipschitz domains.  ESAIM: COCV, 28:2, 2022.
  * [8] John E Dennis Jr and Robert B Schnabel.  Numerical methods for unconstrained optimization and nonlinear equations.  SIAM, 1996.
  * [9] Peter Deuflhard.  Newton methods for nonlinear problems: affine invariance and adaptive algorithms, volume 35.  Springer Science & Business Media, 2005.
  * [10] Michael Hintermüller.  Semismooth Newton methods and applications.  Department of Mathematics, Humboldt-University of Berlin, 2010.
  * [11] Alexey F Izmailov and Mikhail V Solodov.  Newton-type methods for optimization and variational problems, volume 3.  Springer, 2014.
  * [12] John L Kelley.  General topology.  Courier Dover Publications, 2017.
  * [13] Serge Lang.  Fundamentals of differential geometry, volume 191.  Springer Science & Business Media, 2012.
  * [14] John M Lee.  Introduction to Riemannian manifolds, volume 2.  Springer, 2018.
  * [15] Changshuo Liu and Nicolas Boumal.  Simple algorithms for optimization on Riemannian manifolds with constraints.  Applied Mathematics & Optimization, 82(3):949–981, 2020.
  * [16] Jerrold E. Marsden and Tudor S. Ratiu.  Introduction to mechanics and symmetry, volume 17 of Texts in Applied Mathematics.  Springer-Verlag, New York, 1994.  A basic exposition of classical mechanical systems.
  * [17] Robert Mifflin.  Semismooth and semiconvex functions in constrained optimization.  SIAM Journal on Control and Optimization, 15(6):959–972, 1977.
  * [18] Albert Nijenhuis.  Strong derivatives and inverse mappings.  The American Mathematical Monthly, 81(9):969–980, 1974.
  * [19] James M Ortega and Werner C Rheinboldt.  Iterative solution of nonlinear equations in several variables.  SIAM, 2000.
  * [20] Liqun Qi and Jie Sun.  A nonsmooth version of Newton’s method.  Mathematical programming, 58(1):353–367, 1993.
  * [21] Eric Schechter.  Handbook of Analysis and its Foundations.  Academic Press, 1996.
  * [22] Anton Schiela and Julian Ortiz.  An SQP method for equality constrained optimization on Hilbert manifolds.  SIAM Journal on Optimization, 31(3):2255–2284, 2021.
  * [23] Volker H. Schulz, Martin Siebenborn, and Kathrin Welker.  Towards a Lagrange–Newton Approach for PDE Constrained Shape Optimization, pages 229–249.  Springer International Publishing, Cham, 2015.
  * [24] Steven Thomas Smith.  Optimization techniques on Riemannian manifolds.  arXiv preprint arXiv:1407.5965, 2014.
  * [25] Michael Ulbrich.  Semismooth Newton methods for variational inequalities and constrained optimization problems in function spaces.  SIAM, 2011.
  * [26] Eberhard Zeidler.  Nonlinear Functional Analysis and it’s Applications.  Fixed-Point Theorems, page 897, 1986.