Inexact Newton Methods for Solving Generalized Equations on Riemannian Manifolds

In recent years, constrained generalized equations on Banach spaces, i.e., finding a solution to the inclusion

where $\mathbb{X}$ and $\mathbb{Y}$ are two Banach spaces, $C\subset\mathbb{X}$ is a nonempty, closed, and convex set, $f\colon\mathbb{X}\to\mathbb{Y}$ is a mapping, and $F\colon\mathbb{X}\rightrightarrows\mathbb{Y}$ is a set-valued mapping, have gained increased attention [18, 7]. This is attributed to the fact that the model (1) covers many well-known problems, such as constrained variational inequality and split variational inequality problem [15, 34], nonlinear equations, systems of equations and inequalities, optimality condition in mathematical programming and optimal control, and equilibrium problem. The readers are referred to [3, 5, 4, 36, 21, 17, 30, 28, 26, 9, 24, 22, 23, 8, 33, 31, 38] for a detailed study of (1) with $C=\mathbb{X}$.

For a Riemannian manifold ${\cal M}$, a closed set $\Omega\subset{\cal M}$ with a nonempty interior, a continuously differentiable mapping $f\colon{\cal M}\to\mathbb{R}^{m}$, and a set-valued mapping $F\colon{\cal M}\rightrightarrows\mathbb{R}^{m}$, we consider the generalized equation

Evidently, (2) covers the nonlinear equation $f(p)=0$ ($F\equiv 0)$ and the nonlinear inclusion problem $f(p)\in K$ ($F\equiv-K$) for a fixed cone $K\subset\mathbb{R}^{m}$ [52]. In this paper, we shall prove that problem (2) also covers the problem of finding a singularity of the sum of two vector fields of the form

where $V\colon{\cal M}\to{\cal T}{\cal M}$ is a single-valued vector field, $Z\colon{\cal M}\rightrightarrows{\cal T}{\cal M}$ is a set-valued vector field. In particular, we demonstrate that (2) can also be used to obtain a solution for a variational inequality problem and the Karush–Kuhn–Tucker (KKT) conditions for a constrained optimization problem on manifolds.

Problem (3) has been extensively investigated [5, 28] and solved using Newton’s method for $Z\equiv 0$ [6, 25, 51, 42, 2, 19]. This problem naturally arises, for example, in the first-order optimality conditions of the minimization problem

where $\varsigma\colon{\cal M}\to\overline{\mathbb{R}}\coloneqq\mathbb{R}\cup\{\pm\infty\}$ is a differentiable function defined over $\operatorname{int}\Omega$ (the interior of $\Omega$) and $\vartheta\colon{\cal M}\to\overline{\mathbb{R}}$ is non-differentiable. In fact, one can consider (3) with $V$ representing the Riemannian gradient of $\varsigma$ ($\operatorname{grad}\varsigma$), $Z$ representing the Riemannian subdifferential of $\vartheta$ ($\partial\vartheta$), and $\Omega=\operatorname{int}\Omega$, i.e.,

Problem (4) is associated with several important applications, including sparse principal component analysis [32], sparse blind deconvolution [54], unsupervised feature selection [49], and image restoration [12, 11].

The extensive scope of generalized equations and the growing interest in optimization on manifolds [47, 14, 1] in recent years have motivated us to explore the integration of these two areas in this paper. Our focus is on studying a Riemannian version of the inexact Newton method proposed by [16] with the aim of solving problem (2). Given an initial point $p_{0}\in\mathcal{M}$, our method generates a sequence of iterations $\{p_{k}\}$ as follows:

where $R_{k}\colon\mathcal{M}\rightrightarrows\mathbb{R}^{m}$ is a sequence of set-valued mappings with closed graphs representing the inexactness, and $\mathcal{D}f$ denotes the differential of $f$. In other words, the method involves: selecting an initial point $p_{0}$ on the manifold (sufficiently close to a solution), solving a subproblem to find $v_{k}$ in the intersection above (under certain conditions, it is possible to guarantee that it is nonempty), and computing the next iteration $p_{k+1}$ by applying the exponential map to $(p_{k},v_{k})$. It is noteworthy that whenever $v_{k}$ is sufficiently small, (5) can be expressed as:

Although it may appear that obtaining $v_{k}$ requires solving the subproblem in (5) exactly, the map $R_{k}$ is specifically introduced to circumvent this necessity. This is evident in the particular case of (5) where $R_{k}(p_{k})$ is defined as the closed ball centered at $0$ with a radius of $\eta_{k}\|f(p_{k})\|_{e}$, with $\eta_{k}$ being a forcing sequence of non-negative real numbers converging to 0, and $F\equiv 0$. In this scenario, the subproblem in (5) consists of finding a $v_{k}$ that satisfies

where $\|\cdot\|_{e}$ denotes the Euclidean norm, which can be interpreted as an inexact Newton method for by solving $f(p)=0$. The convergence analysis presented in this paper is conducted using (5) because it is more general and can be applied to other potential particular cases of (2).

Assuming that the set-valued mapping $f+F$ in (2) is metrically regular at $\bar{p}\in\Omega$ for $0$ and that $R_{k}$ satisfies a suitable boundedness condition, we demonstrate that a sequence $\{p_{k}\}$ generated by (6) exhibits both linear and quadratic convergence towards $\bar{p}$, with the exact nature of the convergence depending on the specific assumptions regarding $R_{k}$. These results can be obtained without requiring prior knowledge of the sequence of mappings $R_{k}$ in terms of problem-specific data. However, it is necessary to ensure that a sequence $\{u_{k}\}$ in $R_{k}(p_{k})$ converges to $0$ at the same rate as the sequence $\{p_{k}\}$ converges to $\bar{p}$. This requirement is a standard assumption in the context of inexact Newton-type methods, even when applied to nonlinear equations.

Under the condition of metric regularity of a linearization of $f+F$ at $\bar{p}$ for $0$, and provided that certain additional conditions are met, we present variations of the aforementioned results. In these variations, a neighborhood of $\bar{p}$ is assumed to be known, which allows for a more suitable choice of the initial point $p_{0}$ for the sequence $\{p_{k}\}$. We also provide a semi-local convergence result, where the required conditions are related to $p_{0}$ rather than $\bar{p}$. This result is new even in the case where ${\cal M}$ is a Euclidean space.

To understand the concept of metric regularity well on Riemannian manifolds, we constructed examples of mappings that are metrically regular over the set of positive definite symmetric matrices equipped with a well-established Riemannian metric. Additionally, we present conditions that guarantee the metric regularity property for certain mappings, and in particular, we compare the metric regularity of $f+F$ with that of its linearization. Finally, some examples are given to show that our proposed concept is useful and a numerical example applied to the KKT system is given as well for the constrained Riemannian center of mass on the sphere to illustrate our theoretical results.

This work is organized as follows. In Section 2, some notations and basic concepts are reviewed. In Section 3 the metric regularity assumption is explored. In Section 4, local and semi-local convergence are studied for the proposed method. In Section 5 the relationship is investigated between (2) and (3), and some examples of classical problems which can be viewed as generalized equations are given. In Section 6, a numerical example is provided to illustrate our theoretical results. Finally, conclusions are presented in the last section.

In this section we recall some notations, definitions and basic properties of Riemannian manifolds used throughout the paper, which can be found in many introductory books on Riemannian geometry, for example [20, 41, 40, 50].

Suppose that ${\cal M}$ is a connected, $n$-dimensional smooth manifold. At each point $p\in{\cal M}$, the tangent space ${\cal T}_{p}{\cal M}$ is an $n$-dimensional vector space with its origin at $0_{p}$. The disjoint union of all tangent spaces, denoted as ${\cal T}{\cal M}$, is the tangent bundle of ${\cal M}$. We assume that ${\cal M}$ is equipped with a Riemannian metric, making it a Riemannian manifold. At each point $p\in{\cal M}$, this Riemannian metric is denoted by ${\langle}\cdot,\cdot{\rangle}_{p}\colon{\cal T}_{p}{\cal M}\times{\cal T}_{p}{\cal M}\to\mathbb{R}$, and the associated norm in ${\cal T}_{p}{\cal M}$ is represented as $\|\cdot\|_{p}$. The Riemannian distance between two points $p$ and $q$ in ${\cal M}$, denoted as $d(p,q)$, is defined as the infimum of the lengths of all piecewise smooth curve segments connecting $p$ to $q$. Additionally, the distance from a point $p$ to a subset ${\cal W}\subset{\cal M}$ is defined as $d(p,{\cal W})\coloneqq\inf_{q\in{\cal W}}d(p,q)$ and the interior of ${\cal W}$ is represented by $\operatorname{int}{\cal W}$.

A vector field $V$ on ${\cal M}$ is a correspondence that associates to each point $p\in{\cal M}$ a vector $V(p)\in{\cal T}_{p}{\cal M}$. The point $p$ is said to be a singularity of $V$ if and only if $V(p)=0_{p}$. The set of smooth vector fields on ${\cal W}\subseteq{\cal M}$ is denoted by ${\cal X}({\cal W})$.

The tangent vector of a smooth curve $\gamma\colon I\to{\cal M}$ defined on some open interval $I\subseteq\mathbb{R}$ is denoted by $\dot{\gamma}(t)$. For each $a,t\in I$, $a<t$, the Levi-Civita connection $\nabla\colon{\cal X}({\cal M})\times{\cal X}({\cal M})\to{\cal X}({\cal M})$ induces an isometry $P_{\gamma,a,t}\colon{\cal T}_{\gamma(a)}{\mathcal{M}}\to{\cal T}_{\gamma(t)}{\mathcal{M}}$ relative to the Riemannian metric on ${\cal M}$, given by $P_{\gamma,a,t},v=V(\gamma(t))$, where $V$ is the unique vector field on $\gamma$ such that $\nabla_{\dot{\gamma}(t)}V(\gamma(t))=0$ and $V(\gamma(a))=v$. The isometry $P_{\gamma,a,t}$ is the parallel transport along $\gamma$ joining $\gamma(a)$ to $\gamma(t)$. When the geodesic $\gamma$ connecting $p=\gamma(a)$ and $q=\gamma(t)$ is unique, the notation $P_{pq}$ will be used instead of $P_{\gamma,a,t}$. It is well-known that $P_{qp}\circ P_{pq}$ is equal to the identity map over ${\cal T}_{p}{\cal M}$.

The differential of a smooth function $f\colon{\cal M}\to\mathbb{R}$ at $p$ is the linear map ${\cal D}f(p)\colon{\cal T}_{p}{\cal M}\to\mathbb{R}$ which assigns to each $v\in{\cal T}_{p}{\cal M}$ the value

for every smooth curve $\gamma\colon I\to{\cal M}$ satisfying $\gamma(t_{0})=p$ and $\dot{\gamma}(t_{0})=v$. The gradient at $p$ of $f$, denoted as $\operatorname{grad}f(p)$, is defined by the unique tangent vector at $p$ such that ${\langle}\operatorname{grad}f(p),v{\rangle}_{p}={\cal D}f(p)[v]$ for all $v\in{\cal T}_{p}{\cal M}.$ For a smooth multifunction $f\coloneqq(f_{1},\ldots,f_{m})\colon{\cal M}\to\mathbb{R}^{m}$, its differential ${\cal D}f(p)\colon{\cal T}_{p}{\cal M}\to\mathbb{R}^{m}$ is given by

Note that ${\cal D}f(p)$ is a linear map from ${\cal T}_{p}{\cal M}$ into $\mathbb{R}^{m}$ for all $p\in{\cal M}$. The norm of a linear map $A\colon{\cal T}_{p}{\cal M}\to\mathbb{R}^{m}$ is defined by $\|A\|_{map}\coloneqq\sup\{\|Av\|_{e}\colon v\in{\cal T}_{p}{\cal M},\,\|v\|_{p}=1\}$ where $\|\cdot\|_{e}$ is the Euclidean norm on $\mathbb{R}^{m}$.

A vector field $V$ along a smooth curve $\gamma$ is said to be parallel if and only if $\nabla_{\dot{\gamma}}V=0$. The curve $\gamma$ is a geodesic when $\dot{\gamma}$ is self-parallel. When the geodesic equation $\nabla_{\dot{\gamma}}\dot{\gamma}=0$ is a second-order nonlinear ordinary differential equation, the geodesic $\gamma=\gamma_{v}(\cdot,p)$ is determined by its position $p$ and velocity $v$ at $p$. The restriction of a geodesic to a closed bounded interval is called a geodesic segment. Denote the unique geodesic segment $\gamma\colon[0,1]\to{\cal M}$ satisfying $\gamma(0)=p$ and $\gamma(1)=q$ by $\gamma_{pq}$. A geodesic segment joining $p$ to $q$ in $\mathcal{M}$ is said to be minimal if its length is equal to $d(p,q)$. A Riemannian manifold is complete if its geodesics are defined for all values of $t\in\mathbb{R}$. Hopf-Rinow’s theorem asserts that every pair of points in a complete, connected Riemannian manifold $\mathcal{M}$ can be joined by a (not necessarily unique) minimal geodesic segment. Due to the completeness of $\mathcal{M}$, the exponential map $\exp_{p}\colon{\cal T}_{p}\mathcal{M}\to\mathcal{M}$ is given by $\exp_{p}v=\gamma_{v}(1,p)$, for each $p\in\mathcal{M}$. In this paper, all manifolds are assumed to be connected, finite-dimensional, and complete.

The open and closed balls on ${\cal M}$ of radius $r>0$ centered at $p\in{\cal M}$ are defined, respectively, as ${\cal B}_{r}(p)\coloneqq\left\{q\in{\cal M}\colon d(p,q)<r\right\}$ and ${\cal B}_{r}[p]\coloneqq\left\{q\in{\cal M}\colon d(p,q)\leq r\right\}$. Analogously, the open and closed balls on ${\cal T}_{p}{\cal M}$ of radius $r>0$ centered at $u\in{\cal T}_{p}{\cal M}$ are defined, respectively, as $B_{r}(u)\coloneqq\left\{v\in{\cal T}_{p}{\cal M}\colon\|v-u\|_{p}<r\right\}$ and $B_{r}[u]\coloneqq\left\{v\in{\cal T}_{p}{\cal M}\colon\|v-u\|_{p}\leq r\right\}$. It is well-known that there exists $r>0$ such that $\exp_{p}\colon B_{r}(0_{p})\to{\cal B}_{r}(p)$ is a diffeomorphism, and ${\cal B}_{r}(p)$ is called a normal ball with center $p$ and radius $r$. Whenever ${\cal B}_{r}(p)$ is a normal ball, it and its closure will be denoted by $\operatorname{B}_{r}(p)$ and $\operatorname{B}_{r}[p]$, respectively. The injectivity radius of $\cal M$ at $p$, denoted by $r_{inj}(p)$, is the supremum of all $r>0$ such that ${\cal B}_{r}(p)$ is a normal ball. The equality

holds for all $q\in{\cal B}_{r}(p)$, where $\exp_{p}^{-1}\colon{\cal B}_{r}(p)\to{\cal T}_{p}{\cal M}$ denotes the inverse of the exponential map. Recall that there exist $r>0$ and $\delta>0$ such that, for every $q\in\operatorname{B}_{r}(p)$, ${\cal B}_{\delta}(q)$ is a normal ball and $\operatorname{B}_{r}(p)\subset{\cal B}_{\delta}(q)$, see [20, Theorem 3.7]. In this case, $\operatorname{B}_{r}(p)$ is called a totally normal ball of center $p$ and radius $r$. When $\mathcal{M}$ is a Hadamard manifold, that is, a complete, simply connected Riemannian manifold with nonpositive sectional curvature, $\operatorname{B}_{r}(p)$ is totally normal for all $r>0$ and $p\in\mathcal{M}$.

A sequence $\{p_{k}\}\subset{\cal M}$ is linearly convergent to $\bar{p}$ when there exist $\theta\in(0,1)$ and $k_{0}\in\mathbb{N}$ such that

It is said to be quadratically convergent to $\bar{p}$ when there exist $\theta>0$ and $k_{0}\in\mathbb{N}$ such that

We end this section by presenting the concept of Lipschitz continuity for the differential of continuously differentiable functions in the Riemannian context. This concept will be fundamental for obtaining the quadratic convergence rate for our algorithm.

Let $F\colon{\cal M}\rightrightarrows\mathbb{R}^{m}$ be a set-valued mapping, whose the graph of $F$ is the set $\operatorname{gph}F\coloneqq\{(p,x)\in{\cal M}\times\mathbb{R}^{m}\colon x\in F(p)\}$ with domain $\operatorname{dom}F\coloneqq\{p\in{\cal M}\colon F(p)\neq\emptyset\}$. The inverse of $F$ is defined as $x\mapsto F^{-1}(x)=\{p\in{\cal M}\colon x\in F(p)\}$.

A function $f\colon{\cal M}\to\mathbb{R}^{m}$ is said to be Lipschitz continuous relative to a set ${\cal W}\subset\operatorname{dom}f$ if there exists a constant $\kappa\geq 0$ such that

Let $\bar{p}\in\operatorname{int}\operatorname{dom}f$. The Lipschitz modulus of $f$ at $\bar{p}$ is defined by

We now introduce the following notations on $\mathbb{R}^{m}$: $\mathbb{B}_{r}[x]$ denotes the Euclidean closed ball of radius $r>0$ and center $x$, and $d_{e}$ denotes the Euclidean distance from a point to a set. The next concept plays an important role in role in this paper and it comes from [23, p. 279] in the metric spaces setting:

It is important to emphasize that one of the main assumptions used to guarantee the convergence of the proposed algorithm in this paper is metric regularity. This concept, in the context of Riemannian manifolds, has been explored in recent works such as [4, 2, 28]. We will now briefly discuss this property in the case where $\mathcal{M}\equiv\mathbb{R}^{n}$. If $f\colon\mathbb{R}^{n}\to\mathbb{R}^{n}$ is a differentiable function, the metric regularity of $f$ at $\bar{p}$ for $0$ is equivalent to stating that the inverse of the Jacobian matrix of $f$ at $\bar{p}$ exists, which is the standard regularity assumption applied to solve the nonlinear equation $f(p)=0$. On the other hand, if we are interested in solving a nonlinear system of equations and inequalities, for example,

where $x\in\mathbb{R}^{m}$ and $y\in\mathbb{R}^{s}$ are given parameters, and $g:\mathbb{R}^{n}\to\mathbb{R}^{m}$ and $h:\mathbb{R}^{n}\to\mathbb{R}^{s}$ are continuously differentiable functions, then we can associate problem (12) with the following generalized equation:

In this particular case, it is well known that the metric regularity of $f+F$ at $\bar{p}$ for $0$ is equivalent to the standard Mangasarian-Fromovitz constraint qualification at $\bar{p}$. Notably, the case where $F\equiv N_{C}$ is of particular interest, with $N_{C}$ denoting the normal cone to a closed convex set $C\subset\mathbb{R}^{m}$. The metric regularity of $f+N_{C}$ at $\bar{p}$ for $0$ is equivalent to the concept of strong metric regularity, meaning that $f+N_{C}$ is locally single-valued and Lipschitz continuous at $\bar{p}$ for $0$. Thus, if $f$ and $C$ are chosen such that $f+N_{C}\ni 0$ forms the KKT system for a constrained optimization problem, then strong metric regularity is equivalent to the linear independence of the gradients of the active constraints and the strong second-order sufficient condition. These details are thoroughly discussed in [24]; see also Examples 6 and 7 in Section 5.

We present in Subsection 3.1 some examples of set-valued mapping that satisfy the previous concept. The next lemma is a version in the Riemannian setting of Corollary 3F.3 given in [24]. Its proof is similar to the corresponding result in Euclidean space and will be omitted here.

In the theorem below, we demonstrate that the metric regularity condition of a mapping at $\bar{p}\in{\cal M}$ for $\bar{x}\in\mathbb{R}^{m}$ is equivalent to the same condition for its linearization at $\bar{p}$.

Next, we define the Aubin property for a set-valued mapping $\aleph\colon\mathbb{R}^{m}\rightrightarrows\mathcal{M}$. To this end, it is necessary to introduce the concept of excess between subsets of $\mathcal{M}$. For sets ${\cal W}_{1}$ and ${\cal W}_{2}$ in $\mathcal{M}$, the excess of ${\cal W}_{1}$ beyond ${\cal W}_{2}$ is defined as

with the convention that $e(\emptyset,{\cal W}_{2})=0$ for ${\cal W}_{2}\neq\emptyset$ and $e(\emptyset,{\cal W}_{2})=\infty$ otherwise.

The next result provides a relationship between the metric regularity of a set-valued mapping $\Phi\colon{\cal M}\rightrightarrows\mathbb{R}^{m}$ and the Aubin property for its inverse. Its proof follows from a straightforward adaptation of the demonstration in [24, Theorem 3E.6] and the concepts introduced above, and hence will be omitted.