Korpelevich Method for Solving Bilevel Variational Inequalities on Riemannian Manifolds

Abstract

The bilevel variational inequality on Riemannian manifolds refers to a mathematical problem involving the interaction between two levels of optimization, where one level is constrained by the other level. In this context, we present a variant of Korpelevich’s method specifically designed for solving bilevel variational inequalities on Riemannian manifolds with nonnegative sectional curvature and pseudomonotone vector fields. This variant aims to find a solution that satisfies certain conditions. Through our proposed algorithm, we are able to generate iteration sequences that converge to a solution, given mild conditions. Finally, we provide an example to demonstrate the effectiveness of our algorithm.

1. Introduction

Variational inequalities, initially introduced by Stampacchia, have garnered significant attention, and have been extensively explored in various disciplines, including economics, transportation, network, structural analysis, supply chain management, and game theory. They have proven to be invaluable tools for addressing practical problems in these fields.

As mentioned by Németh [1] in 2003, variational inequalities on manifolds have been utilized to formulate numerous problems in applied fields. Manifolds, as non-linear spaces, provide a more general framework for addressing these problems. Generalizing optimization methods from Euclidean spaces to Riemannian manifolds offers several important advantages. For instance, as demonstrated in [2,3,4,5], constrained optimization problems can be reframed as unconstrained problems from the perspective of Riemannian geometry. Another advantage is that, by introducing an appropriate Riemannian metric, optimization problems with non-convex objective functions can be transformed into convex ones. Therefore, the natural and intriguing extension of the concepts and techniques of variational inequality theory, and related topics, from Euclidean spaces to Riemannian manifolds is significant. However, it is crucial to acknowledge that this endeavor is nontrivial. For further information, please refer to the cited references [1,6].

The projection method is known to be convergent for solving bilevel variational inequalities when the cost operator is cocoercive. However, it may not converge if the cost operator is merely monotone. To address this limitation, the extragradient method, also known as the double projection method, has been introduced. Unlike the projection method, the extragradient method retains convergence, even when dealing with pseudomonotone cost operators. Consequently, the extragradient method has been extended to solve problems involving pseudomonotone variational inequalities (see, for example, [7,8,9,10,11]).

Solving variational inequalities on manifolds is a challenging task. Recent studies, based on [1,6,12,13,14], have focused on developing methods for variational inequalities on manifolds. Tang and Huang [15] investigated a variant of Korpelevich’s method for pseudomonotone variational inequalities on Hadamard manifolds. Liou, Obukhovskii, and Yao [16] justified the existence of a solution for a variational inequality problem on Riemannian manifolds using the properties of topological characteristics. Tang et al. [17,18] explored the proximal point algorithm and a projection-type method for variational inequalities with pseudomonotone vector fields on Hadamard manifolds. Li, Zhou, and Huang [19] derived some gap functions for generalized mixed variational inequalities on Hadamard manifolds under appropriate conditions. Tang et al. [20] established existence results for a class of hemivariational inequality problems on Hadamard manifolds, while Hung et al. [21] examined mixed quasi-hemivariational inequality problems on Hadamard manifolds and obtained global error bounds using regularized gap functions under suitable conditions. For further details on this topic, we recommend referring to [22,23,24,25,26].

Motivated by the aforementioned research, we propose a framework for investigating bilevel variational inequalities on Riemannian manifolds with nonnegative sectional curvature and pseudomonotone vector fields. In this framework, we explore a modification of Korpelevich’s method specifically tailored to solve bilevel variational inequalities on Riemannian manifolds. To establish the convergence of our method, we utilize the concept of quasi-Fejér convergence as introduced by Quiroz [2]. Under certain assumptions regarding continuity and pseudomonotonicity of vector fields on Riemannian manifolds, we provide a proof demonstrating that the sequence generated by our proposed method converges to a solution of the bilevel variational inequalities on Riemannian manifolds.

The remainder of this paper is structured as follows: Section 2 provides a comprehensive overview of fundamental concepts, notations, and significant findings in Riemannian geometry. It also introduces the notion of pseudomonotone vector fields, and presents pivotal results on variational inequality on Riemannian manifolds. Section 3 focuses on introducing the formulation of bilevel variational inequality on Riemannian manifolds with nonnegative sectional curvature, along with the application of Korpelevich’s method specifically for solving bilevel variational inequalities on Riemannian manifolds. Section 4 is dedicated to studying the convergence properties of the proposed method for solving bilevel variational inequalities on Riemannian manifolds.

2. Preliminaries

2.1. Riemannian Geometry

An m-dimensional Riemannian manifold is represented by the pair $(M,g)$, where M denotes an m-dimensional smooth manifold, and g denotes a smooth, symmetric positive definite $(0,2)$-tensor field on M, known as the Riemannian metric. For any point $x\in M$, the restriction $g_x:T_{x}M\times T_{x}M\to \mathbb{R}$ defines an inner product on the tangent space $T_{x}M$. The scalar product on $T_{x}M$ is defined as $\langle ·,·\rangle$ with the associated norm $\parallel .\parallel$.

Let $\gamma :[a,b]\subset \mathbb{R}\to M$. If there exists a partition of $[a,b]$ with partition points $\{t_0,t_1,\cdots ,t_n\}$, such that $a=t_0<t_1<\cdots <t_n=b$, and $\gamma$ restricted to each $[t_{k-1},t_k]$ for $k=1,2,\cdots ,n$ represents a smooth curve on M, then the curve represented by $\gamma$ is called a piecewise smooth curve.

Definition 1

([13]). Let $x,y\in M$ and $\gamma :[a,b]\to M$ be a piecewise smooth curve joining x and y (i.e., $\gamma \left(a\right)=x$ and $\gamma \left(b\right)=y$). The length of γ is given by

$$L\left(\gamma \right):={\int }_a^b{\parallel \dot{\gamma }\left(t\right)\parallel }_{\gamma \left(t\right)}\mathrm{d}t,$$

where $\dot{\gamma }$ denotes the first derivative of γ with respect to t.

Theorem 1

([13]). Let $(M,g)$ be a connected Riemannian manifold, let ${\mathrm{\Gamma }}_{x,y}^M$ be the set of all piecewise smooth curves joining x and y in M. The function

$$\mathrm{d}:M\times M\to \mathbb{R},\mathrm{d}(x,y):=inf\{L\left(\gamma \right):\gamma \in {\mathrm{\Gamma }}_{x,y}^M\},$$

defines a distance on M. A geodesic joining x and y in M is said to be minimal if its length equals $\mathrm{d}(x,y)$.

Definition 2

([13]). Let $(M,g)$ be a connected Riemannian manifold, and $\mathcal{X}\left(M\right)$ the Lie algebra of smooth vector fields on M. A function

$$\nabla :\mathcal{X}\left(M\right)\times \mathcal{X}\left(M\right)\to \mathcal{X}\left(M\right),(X,Y)\to {\nabla }_{X}Y,$$

with the properties

$$\begin{array}{cc}\hfill & {\nabla }_{fX+gY}Z=f{\nabla }_{X}Z+g{\nabla }_{Y}Z,\hfill \\ \hfill & {\nabla }_X(aY+bZ)=a{\nabla }_{X}Y+b{\nabla }_{X}Z,\hfill \\ \hfill & {\nabla }_X\left(fY\right)=X\left(f\right)Y+f{\nabla }_{X}Y,\hfill \\ \hfill & {\nabla }_X\langle Y,Z\rangle =\langle {\nabla }_{X}Y,Z\rangle +\langle Y,{\nabla }_{X}Z\rangle ,\hfill \end{array}$$

where $f,g:M\to \mathbb{R}$, $a,b\in \mathbb{R}$, $X,Y,Z\in \mathcal{X}\left(M\right)$, is called Riemannian connection or Levi-Civita connection on M.

Let ∇ be the Levi-Civita connection associated with the Riemannian metric and $\gamma$ be a smooth curve in M. A vector field X is said to be parallel along $\gamma :[0,1]\to M$ if ${\nabla }_{\dot{\gamma }}X=0$. If $\dot{\gamma }$ itself is parallel along $\gamma$ joining x to y,

$$\gamma \left(0\right)=x,\gamma \left(1\right)=y\mathrm{and}{\nabla }_{\dot{\gamma }}\dot{\gamma }=0\mathrm{on}[0,1],$$

we say that $\gamma$ is a geodesic, and in this case $\parallel \dot{\gamma }\parallel$ is constant. When $\parallel \dot{\gamma }\parallel =1$, $\gamma$ is said to be normalized.

The exponential map at x, denoted as ${exp}_x:T_{x}M\to M$ is well-defined on the tangent space $T_{x}M$. Specifically, a curve $\gamma :[0,1]\to M$ is a minimal geodesic joining x to y if and only if there exists a vector $v\in T_{x}M$ such that $\parallel v\parallel =\mathrm{d}(x,y)$ and $\gamma \left(t\right)={exp}_x\left(tv\right)$ for each $t\in [0,1]$. By the Hopf–Rinow Theorem, we know that if M is complete, then any pair of points in M can be joined by a minimal geodesic. Moreover, $(M,\mathrm{d})$ is a complete metric space, and bounded closed subsets are compact [27].

The set $A\subset M$ is said to be convex if contains a geodesic segment $\gamma$ whenever it contains the end points of $\gamma$, i.e., $\gamma \left(\right(1-t)a+tb)$ is in A whenever $x=\gamma \left(a\right)$ and $y=\gamma \left(b\right)$ are in A, and $t\in [0,1]$. Recall that, for a point $x\in M$, the convexity radius at x is defined by

$$r\left(x\right)=sup\{r>0\left|\begin{array}{cc}\hfill & \mathrm{each}\mathrm{ball}\mathrm{in}\mathbf{B}(x,r)\mathrm{is}\mathrm{strongly}\mathrm{convex}\hfill \\ \hfill & \mathrm{and}\mathrm{each}\mathrm{geodesic}\mathrm{in}\mathbf{B}(x,r)\mathrm{is}\mathrm{minimal}\hfill \end{array}\right\}.$$

2.2. Properties of Variational Inequalities

In the following, we will briefly examine the established definitions related to pseudomonotone vector fields and important properties of variational inequalities on Riemannian manifolds. These definitions and properties will form the basis for our subsequent analysis (see [1,6]).

Variational Inequalities on Riemannian Manifold (referred to as (RVI)): Let A be a nonempty set of the Riemannian manifold M, and V be a vector field on A. The variational inequalities on Riemannian manifold M is of finding $\overline{x}\in A$, such that

$$〈V\left(\overline{x}\right),{\dot{\gamma }}_{\overline{x}y}\left(0\right)〉\ge 0,\mathrm{for}\mathrm{each}y\in A\mathrm{and}\mathrm{each}{\gamma }_{\overline{x}y}\in {\mathrm{\Gamma }}_{\overline{x},y}^A.$$

(1)

Definition 3

([6]). Let $A\subset M$ be a closed convex set. A vector field V on A is said to be the following:

(1) 

monotone if, for all $x,y\in A$ and each ${\gamma }_{xy}\in {\mathrm{\Gamma }}_{x,y}^A$,

$$\langle V\left(x\right),{\dot{\gamma }}_{xy}\left(0\right)\rangle -\langle V\left(y\right),{\dot{\gamma }}_{xy}\left(1\right)\rangle \le 0;$$

(2)

(2) 

strictly monotone if, for all $x,y\in A$ and each ${\gamma }_{xy}\in {\mathrm{\Gamma }}_{x,y}^A$,

$$\langle V\left(x\right),{\dot{\gamma }}_{xy}\left(0\right)\rangle -\langle V\left(y\right),{\dot{\gamma }}_{xy}\left(1\right)\rangle <0;$$

(3)

(3) 

pseudomonotone monotone if, for all $x,y\in A$ and each ${\gamma }_{xy}\in {\mathrm{\Gamma }}_{x,y}^A$,

$$\langle V\left(x\right),{\dot{\gamma }}_{xy}\left(0\right)\rangle \Rightarrow \langle V\left(y\right),{\dot{\gamma }}_{xy}\left(1\right)\rangle \le 0.$$

(4)

Let $P_A$ denote the projection onto the set $A\subset M$. For each point $x\in M$, the projection $P_A\left(x\right)$ is defined as follows:

$$P_{A}x=\left\{\overline{x}\in A:\mathrm{d}(x,\overline{x})=\underset{z\in A}{inf}\mathrm{d}(x,z)\right\}.$$

(5)

Then, $P_{A}x\ne \varnothing$ for each $x\in M$ if A is closed. In general, $P_A$ is a set valued map, and has the following basic properties.

Theorem 2

([6]). Let $A\subset M$ be a nonempty closed set, and let $\overline{x}\in A$. Let $x\in M$ and ${\gamma }_{x\overline{x}}\in {\mathrm{\Gamma }}_{x,\overline{x}}$ be a minimal geodesic. If $\overline{x}\in P_{A}x$, then

$$\langle {\dot{\gamma }}_{x\overline{x}}\left(1\right),{\dot{\gamma }}_{\overline{x}z}\left(0\right)\rangle \ge 0\mathrm{for}\mathrm{each}z\in A\mathrm{and}\mathrm{each}{\gamma }_{\overline{x}z}\in {\mathrm{\Gamma }}_{\overline{x},z}^A.$$

(6)

Proposition 1

([6]). Let A be a locally convex closed subset of M. Then, there exists an open subset U of M with $A\subseteq U$ such that $P_A$ is single-valued and Lipschitz continuous on U.

Proposition 2

([14]). The metric projection onto a closed and convex set $A\subset M$ is a nonexpansive mapping, i.e.,

$$\mathrm{d}\left(P_A\left(x\right),P_A\left(y\right)\right)\le \mathrm{d}(x,y),\forall x,y\in M.$$

Proposition 3

([18]). Let $A\subset M$ be a nonempty closed convex set. Then, there holds

$${\mathrm{d}}^2\left(P_A\left(x\right),\overline{x}\right)\le {\mathrm{d}}^2(x,\overline{x})-{\mathrm{d}}^2(x,P_A\left(x\right)),\forall x\in Mand\overline{x}\in A.$$

Theorem 3

([6]). Let $A\subset M$ be a nonempty weakly convex set, and let $\overline{x}\in A$. Let V be a vector field on A. Then, there exists ${\overline{r}}_{\overline{x}}>0$ such that, for each $r\in (0,{\overline{r}}_{\overline{x}})$,

$$\overline{x}\in P_A\left({exp}_{\overline{x}}(-rV\left(\overline{x}\right))\right)\iff \overline{x}\mathrm{is}\mathrm{a}\mathrm{solution}\mathrm{of}\left(1\right).$$

(7)

Recall that a geodesic triangle $▵\left(p_1{p}_2{p}_3\right)$ of a Riemannian manifold is a set consisting of three points ($p_1$, $p_2$, and $p_3$), and three minimal geodesics joining these points. The most important property is described in Proposition 4.5, taken from [27].

Proposition 4

($\mathrm{Comparison}\mathrm{theorem}\mathrm{for}\mathrm{triangles}$). Let $▵\left(p_1{p}_2{p}_3\right)$ be a geodesic triangle. Denote, for each $i=1,2,3\left(mod3\right)$, by ${\gamma }_i:[0,l_i]\to M$ the geodesic joining $p_i$ to $p_{i+1}$, and set $l_i:=L\left({\gamma }_i\right)$ and ${\alpha }_i:=\angle \left({\dot{\gamma }}_i\left(0\right),-{\dot{\gamma }}_{i-1}\left(l_{i-1}\right)\right)$. Then,

(i) 

${\alpha }_1+{\alpha }_2+{\alpha }_3\le \pi$;

(ii) 

$l_i^2+l_{i+1}^2-2l_i{l}_{i+1}cos{\alpha }_{i+1}\le l_{i-1}^2$;

(iii) 

$l_{i+1}cos{\alpha }_{i+2}+l_{i}cos{\alpha }_i\ge l_{i+2}$.

If the Riemannian manifold possesses non-negative curvature, the following conclusion can be drawn.

Proposition 5

([2]). In a complete finite dimensional Riemannian manifold with nonnegative sectional curvature, we have

$$l_3^2\le l_1^2+l_2^2-2l_1{l}_{2}cos\alpha$$

(8)

where $l_i$ denotes the length of ${\gamma }_i(i=1,2)$, $l_3=\mathrm{d}({\gamma }_1\left(l_1\right),{\gamma }_2\left(l_2\right))$, and $\alpha =({\dot{\gamma }}_1\left(0\right),{\dot{\gamma }}_2\left(0\right))$.

3. The Algorithm

Firstly, we introduce the bilevel variational inequalities on Riemannian manifold M with nonnegative sectional curvature. Subsequently, we present the algorithm devised to solve these problem.

Bilevel Variational Inequalities on Riemannian Manifold (referred to as (RBVI)): Let $A\subset M$ be a nonempty closed convex set and U be a vector field on Sol$(V,A)$. Find $\overline{x}\in \mathrm{Sol}(V,A)$ such that

$$\langle U\left(\overline{x}\right),{\dot{\gamma }}_{\overline{x}x}\left(0\right)\rangle \ge 0,\mathrm{for}\mathrm{each}\mathrm{x}\in \mathrm{Sol}(V,A)\mathrm{and}\mathrm{each}{\gamma }_{\overline{x}x}\in {\mathrm{\Gamma }}_{\overline{x},x}^{\mathrm{Sol}(V,A)},$$

(9)

where V is a vector field on A, and Sol$(V,A)$ denotes the set of all solutions of the following variational inequality. Find $\overline{y}\in A$ such that

$$\langle V\left(\overline{y}\right),{\dot{\gamma }}_{\overline{y}y}\left(0\right)\rangle \ge 0,\mathrm{for}\mathrm{each}y\in A\mathrm{and}\mathrm{each}{\gamma }_{\overline{y}y}\in {\mathrm{\Gamma }}_{\overline{y},y}^A.$$

(10)

In what follows, we suppose that the vector fields V and U satisfy the following conditions:

$\left(H_1\right)$

V is continuous and pseudomonotone vector field on A.

$\left(H_2\right)$

U is continuous and pseudomonotone vector field on Sol$(V,A)$.

$\left(H_3\right)$

The solution sets Sol$(V,A)$ and Sol(RBVI) of problem (RBVI) are nonempty.

Under the above assumptions, we extend Korpelevich’s method for Problems (9) and (10) on Riemannian manifolds.

According to Theorem 3, we know that x is a solution to Problem (1) if and only if $x\in P_A\left({exp}_x(-rV\left(x\right))\right)$. So, we generate a sequence $\left\{x^n\right\}$ through

$$x^{k+1}=P_A\left({exp}_{x^k}\left(-{\beta }_{k}V\left(x^k\right)\right)\right).$$

Korpelevich suggested an algorithm in Euclidean space of the form

$$y^k=P_A\left(x^k-{\alpha }_{k}V\left(x^k\right)\right),$$

(11)

and

$$x^{k+1}=P_A\left(x^k-{\alpha }_{k}V\left(y^k\right)\right).$$

(12)

If V is Lipschitz continuous with constant L and variational inequality problem has solution, then the sequence generated by (11) and (12) converges to solution of variational inequality problem, provided that ${\alpha }_k=\alpha \in (0,1/L)$; see [15]. In the case, when V is not Lipschitz continuous or the Lipschitz constant is not easy to compute, the extragradient method requires a line search procedure to compute the step size.

Building upon this foundation, we give the extragradient method for the lower-level variational inequality on Riemannian manifold as follows.

Take $\delta \in (0,1)$, $\overline{\beta }$, $\tilde{\beta }$ satisfying $0\le \overline{\beta }\le \tilde{\beta }$, and a sequence $\left\{{\beta }_k\right\}\subset [\overline{\beta },\tilde{\beta }]$. The method is initialized with any $x^0\in A$, and the iterative step is as follows.

Given $x^k\in A$, define $y^k:=P_A\left({exp}_{x^k}(-{\beta }_{k}V\left(x^k\right))\right)$; if $x^k=y^k$, then stop. Otherwise, take

$$\begin{array}{ccc}\hfill j\left(k\right)& :=& min\{j\in N^{+}:〈V({\gamma }_k\left(2^{-j}\right),{\gamma }_k^{\prime }\left(2^{-j}\right))〉\le -{\displaystyle \frac{\delta }{{\beta }_k}}\mathrm{d}(x^k,y^k)\},\hfill \\ \hfill {\alpha }_k& =& 2^{-j\left(k\right)},\hfill \\ \hfill {\mu }^k& :=& {\gamma }_k\left(2^{-j\left(k\right)}\right),\hfill \\ \hfill H_k& :=& \{x\in M:\langle V\left({\mu }^k\right),{\dot{\gamma }}_{x{\mu }^k}\left(1\right)\rangle \le 0,{\gamma }_{x{\mu }^k}\in {\mathrm{\Gamma }}_{x,{\mu }^k}\},\hfill \\ \hfill z^k& :=& P_A\left(P_{H_k}\left(x^k\right)\right).\hfill \end{array}$$

The following algorithm for solving the problem (RBVI) contains two loops. In each iteration of the outer loop, we apply Korpelevich’s method to the lower variational inequality on Riemannian manifold. Subsequently, starting from the iterate obtained in the outer loop, we compute $x^{k+1}:={exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right)$ for the upper variational inequality on Riemannian manifold. With this, we can now present the algorithm for solving the (RBVI) problem using Korpelevich’s method.

Algorithm 1.

Choose$x^0\in A$, $k=0$, $\delta \in (0,1)$, $\overline{\beta }$, $\tilde{\beta }$satisfying$0\le \overline{\beta }\le \tilde{\beta }$, positive sequences$\left\{{\beta }_k\right\}$, $\left\{{\lambda }_k\right\}$and$\left\{{ϵ}_k\right\}$, such that

$$\left\{\begin{array}{cc}\hfill & \left\{{\beta }_k\right\}\subset [\overline{\beta },\tilde{\beta }],\hfill \\ \hfill & {lim}_{k\to \infty }{\lambda }_k=0,{lim}_{k\to \infty }{ϵ}_k=0,{\sum }_{k=0}^{\infty }{ϵ}_k<\infty .\hfill \end{array}\right.$$

Step 1.

Given$x^k\in A$, compute

$$y^k:=P_A\left({exp}_{x^k}(-{\beta }_{k}V\left(x^k\right))\right),$$

(13)

and define${\gamma }_k\left(t\right):={exp}_{x^k}t{\dot{\gamma }}_{x^k{y}^k}\left(0\right)$.

Let

$$j\left(k\right):=min\left\{j\in N^{+}:〈V({\gamma }_k\left(2^{-j}\right),{\gamma }_k^{\prime }\left(2^{-j}\right))〉\le -{\displaystyle \frac{\delta }{{\beta }_k}}\mathrm{d}(x^k,y^k)\right\},$$

(14)

and

$${\mu }^k:={\gamma }_k\left(2^{-j\left(k\right)}\right).$$

(15)

Define

$$H_k:=\left\{x\in M:\langle V\left({\mu }^k\right),{\dot{\gamma }}_{x{\mu }^k}\left(1\right)\rangle \le 0,{\gamma }_{x{\mu }^k}\in {\mathrm{\Gamma }}_{x,{\mu }^k}\right\},$$

(16)

and compute

$${\omega }^k:=P_{H_k}\left(x^k\right),$$

(17)

$$z^k:=P_A\left({\omega }^k\right).$$

(18)

Step 2.

Set$x^{k+1}:={exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right)$, where

$${\lambda }_k\in \left(0,{\displaystyle \frac{\sqrt{{ϵ}_k}}{\parallel U\left(z^k\right)\parallel }}\right).$$

(19)

Then, increase k by 1, and go to Step 1.

Remark 1.

If $M={\mathbb{R}}^n$, then Algorithm 1 reduces to the algorithm proposed by Anh [10].

4. Convergence Results

In this section, we consider a nonempty closed convex subset A of a Riemannian manifold M with nonnegative sectional curvature. The following lemmas and theorems demonstrate the convergence of the algorithm for the (RBVI) problem.

Before proceeding, let us review the concept of quasi-Fejér convergence.

Definition 4

([2]). Let $(X,\mathrm{d})$ be a complete metric space and $A\subseteq X$ be a nonempty set. A sequence $\left\{x^k\right\}\subset X$, $k\ge 0$ is said to have quasi-Fejér convergence to A if, for every $y\in A$, there exists a sequence $\left\{{ϵ}_k\right\}\subseteq \mathbb{R}$, such that ${ϵ}_k\ge 0$, ${\sum }_{k=0}^{\infty }{ϵ}_k<+\infty$, and the following condition holds:

$${\mathrm{d}}^2(x^{k+1},y)\le {\mathrm{d}}^2(x^k,y)+{ϵ}_k.$$

Lemma 1.

In a complete metric space $(X,\mathrm{d})$, if $\left\{x_k\right\}\subset X$ is quasi-Fejér convergence to a nonempty set $A\subset X$, then $\left\{x_k\right\}$ is bounded. If, furthermore, a cluster point of $\left\{x_k\right\}$ belongs to A, then $\left\{x_k\right\}$ converges to a point of A.

Proof. 

Analogous to Burachik et al. [28], we replace the Euclidean norm with the Riemannian distance $\mathrm{d}$. □

Lemma 2.

Suppose the sequences $\left\{x_k\right\}$ and $\left\{z_k\right\}$ are generated by Algorithm 1. Let V be a continuous and pseudomonotone vector field on A, and $\overline{x}\in \mathrm{Sol}(V,A)$. Then, we have that

$$\mathrm{d}(z^k,\overline{x})\le \mathrm{d}(x^k,\overline{x})$$

(20)

Proof. 

Let $\overline{x}\in \mathrm{Sol}(V,A)$. That means

$$\langle V\left(\overline{x}\right),{\dot{\gamma }}_{\overline{x}x}\left(0\right)\rangle \ge 0,\mathrm{for}\mathrm{each}x\in A\mathrm{and}\mathrm{each}{\gamma }_{\overline{x}x}\in {\mathrm{\Gamma }}_{\overline{x},x}^A.$$

Due to the pseudomonotonicity of V, we can infer that

$$\langle V\left(x\right),{\dot{\gamma }}_{\overline{x}x}\left(1\right)\rangle \ge 0,\mathrm{for}\mathrm{each}x\in A.$$

By utilizing the fact that ${\mu }_k\in A$, we can proceed to infer that

$$\langle V\left({\mu }_k\right),{\dot{\gamma }}_{\overline{x}{\mu }_k}\left(1\right)\rangle \le 0,\mathrm{and}\overline{x}\in H_k.$$

Since ${\omega }^k=P_{H_k}\left(x^k\right)$, we can apply Proposition 3 to conclude that

$$\begin{array}{cc}\hfill {\mathrm{d}}^2({\omega }^k,\overline{x})& ={\mathrm{d}}^2\left(P_{H_k}\left(x^k\right),\overline{x}\right)\hfill \\ \hfill & \le {\mathrm{d}}^2(x^k,\overline{x})-{\mathrm{d}}^2\left(x^k,P_{H_k}\left(x^k\right)\right)\hfill \\ \hfill & \le {\mathrm{d}}^2(x^k,\overline{x}).\hfill \end{array}$$

Similarly, taking $z^k=P_A\left({\omega }^k\right)$, we obtain

$$\begin{array}{cc}\hfill {\mathrm{d}}^2(z^k,\overline{x})& ={\mathrm{d}}^2\left(P_A\left({\omega }^k\right),\overline{x}\right)\hfill \\ \hfill & \le {\mathrm{d}}^2\left({\omega }^k,\overline{x})-{\mathrm{d}}^2(x^k,P_A\left({\omega }^k\right)\right)\hfill \\ \hfill & \le {\mathrm{d}}^2({\omega }^k,\overline{x})\hfill \\ \hfill & \le {\mathrm{d}}^2(x^k,\overline{x}).\hfill \end{array}$$

This completes the proof. □

Lemma 3.

Under Assumptions $H_1$ to $H_3$, the sequence $\left\{x_k\right\}$ generated by Algorithm 1 is bounded.

Proof. 

Referring to Algorithm 1, we can observe that

$$x^{k+1}:={exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right).$$

Let $\overline{x}$ be a solution to the problem (RBVI). Suppose ${\gamma }_{z^k\overline{x}}:[0,1]\to M$ is a minimal geodesic segment linking $z^k$ to $\overline{x}$, and ${\gamma }_{z^k{x}^{k+1}}:[0,1]\to M$ is the geodesic segment linking $z^k$ to $x^{k+1}$ such that ${\dot{\gamma }}_{z^k{x}^{k+1}}\left(0\right)=-{\lambda }_{k}U\left(z^k\right)$, where $\alpha =\angle \left({\dot{\gamma }}_{z^k\overline{x}}\left(0\right),{\dot{\gamma }}_{z^k{x}^{k+1}}\left(0\right)\right)$.

According to Proposition 5, we have that

$$\begin{array}{cc}\hfill {\mathrm{d}}^2(x^{k+1},\overline{x})& \le {\mathrm{d}}^2(z^k,\overline{x})+{\lambda }_k^2{\parallel U\left(z^k\right)\parallel }^2\hfill \\ \hfill & -2{\lambda }_k\parallel U\left(z^k\right)\parallel \mathrm{d}(z^k,\overline{x})cos\alpha .\hfill \end{array}$$

(21)

From the fact that

$$\langle {\dot{\gamma }}_{z^k{z}^{k+1}}\left(0\right),{\dot{\gamma }}_{z^k\overline{x}}\left(0\right)\rangle ={\lambda }_k\parallel U\left(z^k\right)\parallel \mathrm{d}(z^k,\overline{x})cos\alpha ,$$

and using Inequality (21), we obtain

$$\begin{array}{cc}\hfill {\mathrm{d}}^2(x^{k+1},\overline{x})& \le {\mathrm{d}}^2(z^k,\overline{x})+{\lambda }_k^2{\parallel U\left(z^k\right)\parallel }^2\hfill \\ \hfill & +2{\lambda }_k\langle U\left(z^k\right),{\dot{\gamma }}_{z^k\overline{x}}\left(0\right)\rangle .\hfill \end{array}$$

(22)

Since $\overline{x}$ is a solution to the problem (RBVI), we have $\overline{x}\in \mathrm{Sol}(V,A)$. From Lemma 2, we see that

$$\mathrm{d}(z^k,\overline{x})\le \mathrm{d}(x^k,\overline{x}),$$

and combining inequality (22), we can conclude that

$$\begin{array}{cc}\hfill {\mathrm{d}}^2(x^{k+1},\overline{x})& \le {\mathrm{d}}^2(z^k,\overline{x})+{\lambda }_k^2\parallel U\left(z^k\right){\parallel }^2+2{\lambda }_k\langle U\left(z^k\right),{\dot{\gamma }}_{z^k\overline{x}}\left(0\right)\hfill \\ \hfill & \le {\mathrm{d}}^2(x^k,\overline{x})+{\lambda }_k^2{\parallel U\left(z^k\right)\parallel }^2+2{\lambda }_k\langle U\left(z^k\right),{\dot{\gamma }}_{z^k\overline{x}}\left(0\right)\rangle .\hfill \end{array}$$

It follows from the pseudomonotonicity of U on Sol$(V,A)$ that

$$\langle U\left(z^k\right),{\dot{\gamma }}_{z^k\overline{x}}\left(0\right)\rangle \le 0.$$

So, we obtain

$${\mathrm{d}}^2(x^{k+1},\overline{x})\le {\mathrm{d}}^2(x^k,\overline{x})+{\lambda }_k^2{\parallel U\left(z^k\right)\parallel }^2.$$

(23)

Combining the above Inequality (23), and applying Lemma 2, we know that

$$\sum _{k=0}^{\infty }{\lambda }_k^2{\parallel U\left(z^k\right)\parallel }^2<\sum _{k=0}^{\infty }{ϵ}_k<\infty .$$

So, the sequence $\left\{x_k\right\}$ is quasi-Fejér convergent concerning the solution of problem (RBVI), and $\left\{x_k\right\}$ is bounded. □

Lemma 4.

Suppose that Assumptions $H_1$–$H_3$ hold, and the sequences $\left\{x_k\right\}$ and $\left\{z_k\right\}$ are generated by Algorithm 1. Then, we have

$${\mathrm{d}}^2(x^{k+1},x^k)\le {\mathrm{d}}^2(z^k,x^k)+{\lambda }_k^2{\parallel U\left(z^k\right)\parallel }^2+2{\lambda }_k\langle U\left(z^k\right),{\dot{\gamma }}_{z^k{x}^k}\left(0\right)\rangle ,$$

(24)

and

$$\underset{k\to \infty }{lim}\mathrm{d}(x^{k+1},x^k)=\underset{k\to \infty }{lim}\mathrm{d}(z^k,x^k)=0.$$

(25)

Proof. 

From Lemma 3 and Proposition 5, let ${\gamma }_{z^k\overline{x}}:[0,1]\to M$ be a minimal geodesic segment linking $z^k$ to $x^k$, and ${\gamma }_{z^k{x}^{k+1}}:[0,1]\to M$ be the geodesic segment linking $z^k$ to $x^{k+1}$ with ${\dot{\gamma }}_{z^k{x}^{k+1}}\left(0\right)=-{\lambda }_{k}U\left(z^k\right)$, where $\alpha =\angle \left({\dot{\gamma }}_{z^k{x}^k}\left(0\right),{\dot{\gamma }}_{z^k{x}^{k+1}}\left(0\right)\right)$. We have

$${\mathrm{d}}^2(x^{k+1},x^k)\le {\mathrm{d}}^2(z^k,x^k)+{\lambda }_k^2\parallel U\left(z^k\right){\parallel }^2+2{\lambda }_k\langle U\left(z^k\right),{\dot{\gamma }}_{z^k{x}^k}\left(0\right)\rangle .$$

(26)

This is desired result (24).

By Algorithm 1 and Proposition 3, we have

$$\begin{array}{cc}\hfill {\mathrm{d}}^2(z^k,x^k)& ={\mathrm{d}}^2(P_A\left({\omega }^k\right),x^k)\hfill \\ \hfill & \le {\mathrm{d}}^2({\omega }^k,x^k)-{\mathrm{d}}^2({\omega }^k,P_A\left({\omega }^k\right))\hfill \\ \hfill & \le {\mathrm{d}}^2({\omega }^k,x^k).\hfill \end{array}$$

Applying Lemma 3, the sequence $\left\{x^k\right\}$ is a quasi-Fejér convergent sequence, and $\mathrm{d}(x^k,\overline{x})$ is a convergent sequence. Since ${\omega }^k=P_{H_k}\left(x^k\right)$ and ${lim}_{k\to \infty }\mathrm{d}({\omega }^k,x^k)=0$, then, we see that

$$\underset{k\to \infty }{lim}\mathrm{d}(z^k,x^k)=0.$$

Using Inequality (26) and ${lim}_{k\to \infty }{\lambda }_k=0$, we obtain

$$\underset{k\to \infty }{lim}\mathrm{d}(x^{k+1},x^k)=\underset{k\to \infty }{lim}\mathrm{d}(z^k,x^k)=0.$$

□

Theorem 4.

Suppose that the assumptions $H_1-H_3$ hold. Then, the two sequences $\left\{x^k\right\}$ and $\left\{z^k\right\}$ generated by Algorithm 1 converge to the same solution of Problem (RBVI).

Proof. 

By Lemma 1, we need to prove that the convergence points of $\left\{x^k\right\}$ and $\left\{z^k\right\}$ belong to Sol(RBVI). Let $\overline{x}$ and $\overline{z}$ be the convergence points of $\left\{x^k\right\}$ and $\left\{z^k\right\}$, respectively. Then, ${lim}_{k\to \infty }{x}^k=\overline{x}$ and ${lim}_{k\to \infty }{z}^k=\overline{z}$. So, we will have to show that

$$\underset{k\to \infty }{lim}\mathrm{d}\left(x^k,P_{\mathrm{Sol}(V,A)}\left({exp}_{x^k}\left(-{\lambda }_{k}U\left(x^k\right)\right)\right)\right)=0,$$

and

$$\underset{k\to \infty }{lim}\mathrm{d}\left(z^k,P_{\mathrm{Sol}(V,A)}\left({exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right)\right)\right)=0.$$

Now, using Proposition 3 and Lemma 4, we have

$$\begin{array}{cc}\hfill \underset{k\to \infty }{lim}{\mathrm{d}}^2& \left(x^k,P_{\mathrm{Sol}(V,A)}\left({exp}_{x^k}\left(-{\lambda }_{k}U\left(x^k\right)\right)\right)\right)\hfill \\ \hfill & =\underset{k\to \infty }{lim}{\mathrm{d}}^2\left(x^{k+1},P_{\mathrm{Sol}(V,A)}\left({exp}_{x^k}\left(-{\lambda }_{k}U\left(x^k\right)\right)\right)\right)\hfill \\ \hfill & \le \underset{k\to \infty }{lim}{\mathrm{d}}^2\left({exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right),P_{\mathrm{Sol}(V,A)}\left({exp}_{x^k}\left(-{\lambda }_{k}U\left(x^k\right)\right)\right)\right)\hfill \\ \hfill & \le \underset{k\to \infty }{lim}{\mathrm{d}}^2({exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right),{exp}_{x^k}\left(-{\lambda }_{k}U\left(x^k\right)\right)).\hfill \end{array}$$

Applying Proposition 5, we obtain

$$\begin{array}{cc}\hfill {\mathrm{d}}^2& \left({exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right),{exp}_{x^k}\left(-{\lambda }_{k}U\left(x^k\right)\right)\right)\hfill \\ \hfill & \le {\mathrm{d}}^2\left(x^k,{exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right)\right)\hfill \\ \hfill & +\parallel {\lambda }_{k}U\left(z^k\right){\parallel }^2+2{\lambda }_k〈U\left(z^k\right),{\dot{\gamma }}_{x^k{exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right)}\left(0\right)〉,\hfill \end{array}$$

and

$${\mathrm{d}}^2\left(x^k,{exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right)\right)\le {\mathrm{d}}^2(x^k,z^k)+{\parallel {\lambda }_{k}U\left(z^k\right)\parallel }^2+2{\lambda }_k〈U\left(z^k\right),{\dot{\gamma }}_{z^k{x}^k}\left(0\right)〉.$$

Combining the above inequalities and ${lim}_{k\to 0}{\lambda }_k=0$, ${lim}_{k\to \infty }\mathrm{d}(z^k,x^k)=0$, we obtain

$$\underset{k\to \infty }{lim}\mathrm{d}\left(x^k,P_{\mathrm{Sol}(V,A)}\left({exp}_{x^k}\left(-{\lambda }_{k}U\left(x^k\right)\right)\right)\right)=0,$$

and, so, ${lim}_{k\to \infty }{x}^k=\overline{x}\in \mathrm{Sol}\left(\mathrm{RBVI}\right)$. In a similar way, we can show that

$$\underset{k\to \infty }{lim}\mathrm{d}\left(z^k,P_{\mathrm{Sol}(V,A)}\left({exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right)\right)\right)=0.$$

Thus, ${lim}_{k\to \infty }{z}^k=\overline{z}\in \mathrm{Sol}\left(\mathrm{RBVI}\right)$. By Lemma 4, we have ${lim}_{k\to \infty }$$\mathrm{d}(z^k,x^k)=0$. So, two sequences, $\left\{x^k\right\}$ and $\left\{z^k\right\}$, generated by Algorithm 1 converge to the same solution of Problem (RBVI). □

The following example shows the effectiveness of our algorithm.

Example 1.

Let X denote the diagonal matrix $X=diag(x_1,\cdots ,x_n)$. We consider in this section the particular case $M={\mathbb{R}}_{++}^n$ with the metric $g=X^{-2}$. This space is a connected and complete finite dimensional Riemannian manifold with null sectional curvature. For any vectors u and v in the tangent plane at $x\in M$, we have

$$\langle u,v\rangle =\sum _{i=1}^n{\displaystyle \frac{u_i{v}_i}{x_i^2}},\forall u=\left(u_i\right)\in T_{x}M,v=\left(v_i\right)\in T_{x}M,x=\left(x_i\right)\in M.$$

It is easy to see that the (minimizing) geodesic curve $t\mapsto \gamma \left(t\right)$, verifying $\gamma \left(0\right)=x$, and ${\gamma }^{\prime }\left(0\right)=v$ is given by

$$\mathbb{R}\ni t\mapsto \left(x_1{e}^{{\displaystyle \frac{v_1}{x_1}}t},\cdots ,x_n{e}^{{\displaystyle \frac{v_n}{x_n}}t}\right).$$

Then, it implies that the exponential map can be expressed as

$${exp}_x\left(rv\right)=\left(x_1{e}^{{\displaystyle \frac{v_1}{x_1}}t},\cdots ,x_n{e}^{{\displaystyle \frac{v_n}{x_n}}t}\right).$$

Also, the (minimizing) geodesic segment $\gamma :[0,1]\to M$ joining the points x and y, $i.e$., $\gamma \left(0\right)=x$, $\gamma \left(1\right)=y$ is given by ${\gamma }_i\left(t\right)=x_i^{1-t}{y}_i^t,i=1,2,\cdots ,n$. Thus, the distance $\mathrm{d}$ on the metric space $({\mathbb{R}}_{++}^n,X^{-2})$ is defined by

$$\begin{array}{cc}\hfill \mathrm{d}(x,y)& ={\int }_0^1{\parallel {\gamma }^{\prime }\left(t\right)\parallel }_{\gamma \left(t\right)}dt={\int }_0^1\sqrt{{\sum }_{i=1}^n{\left({\displaystyle \frac{{\gamma }_i^{\prime }\left(t\right)}{{\gamma }_i\left(t\right)}}\right)}^2}dt\hfill \\ \hfill & =\sqrt{{\sum }_{i=1}^n{\left(ln{\displaystyle \frac{x_i}{y_i}}\right)}^2}.\hfill \end{array}$$

To obtain the expression of the inverse exponential map, we write

$$y={exp}_x\left({exp}_x^{-1}y\right)=\left(x_1{e}^{{\displaystyle \frac{{exp}_x^{-1}y}{x_1}}},\cdots ,x_n{e}^{{\displaystyle \frac{{exp}_x^{-1}y}{x_n}}}\right).$$

Therefore, we obtain ${exp}_x^{-1}y=\left(x_{1}ln{\displaystyle \frac{y_1}{x_1}},\cdots ,x_{n}ln{\displaystyle \frac{y_n}{x_n}}\right)$.

Applying Algorithm 1 to the case $({\mathbb{R}}_{++}^n,X^{-2})$, we can translate the iterative scheme into the following one. Having $x^k$, then let

$$y^k:=P_A\left({exp}_{x^k}\left(-{\beta }_{k}V\left(x^k\right)\right)\right)=P_A(x_1^k{e}^{-{\beta }_k{\displaystyle \frac{V\left(x^k\right)}{x_1^k}}},\cdots ,x_n^k{e}^{-{\beta }_k{\displaystyle \frac{V\left(x^k\right)}{x_n^k}}}),$$

and

$${\gamma }_k\left(t\right)={exp}_{x^k}t{\dot{\gamma }}_{x^k{y}^k}\left(0\right)=(x_1^k{e}^{t{\displaystyle \frac{{\dot{\gamma }}_{x^k{y}^k}\left(0\right)}{x_1^k}}},\cdots ,x_n^k{e}^{t{\displaystyle \frac{{\dot{\gamma }}_{x^k{y}^k}\left(0\right)}{x_n^k}}}).$$

Thus, we have

$${\gamma }_k^{\prime }\left(t\right)=\left({\dot{\gamma }}_{x^k{y}^k}\left(0\right)e^{t{\displaystyle \frac{{\dot{\gamma }}_{x^k{y}^k}\left(0\right)}{x_1^k}}},\cdots ,{\dot{\gamma }}_{x^k{y}^k}\left(0\right)e^{t{\displaystyle \frac{{\dot{\gamma }}_{x^k{y}^k}\left(0\right)}{x_n^k}}}\right),$$

and

$$\mathrm{d}(x^k,y^k)=\sqrt{{\sum }_{i=1}^n{\left(ln{\displaystyle \frac{x_i^k}{y_i^k}}\right)}^2},$$

respectively. Let

$$\begin{array}{ccc}\hfill j\left(k\right)& =& min\{j\in N^{+}:〈V({\gamma }_k\left(2^{-j}\right),{\gamma }_k^{\prime }\left(2^{-j}\right))〉\le -{\displaystyle \frac{\delta }{{\beta }_k}}\mathrm{d}(x^k,y^k)\},\hfill \\ \hfill {\mu }^k& =& {\gamma }_k\left(2^{-j\left(k\right)}\right),\hfill \\ \hfill H_k& =& \{x\in M:\langle V\left({\mu }^k\right),{\dot{\gamma }}_{x{\mu }^k}\left(1\right)\rangle \le 0,{\gamma }_{x{\mu }^k}\in {\mathrm{\Gamma }}_{x,{\mu }^k}\},\hfill \\ \hfill {\omega }^k& =& P_{H_k}\left(x^k\right),\hfill \\ \hfill z^k& =& P_A\left({\omega }^k\right),\hfill \\ \hfill x^{k+1}& =& {exp}_{z^k}\left(-{\lambda }_{k}U\left(z^k\right)\right),\hfill \end{array}$$

where ${\lambda }_k\in \left(0,{\displaystyle \frac{\sqrt{{ϵ}_k}}{\parallel U\left(z^k\right)\parallel }}\right)$, ${lim}_{k\to \infty }{\lambda }_k=0$, ${lim}_{k\to \infty }{ϵ}_k=0$, ${\sum }_{k=0}^{\infty }{ϵ}_k<\infty$. Now, consider $M={\mathbb{R}}_{++}^2$, $X=diag(x_1,x_2)$. Taking $x=(x_1,x_2)\in M$, we obtain $T_{x}M={\mathbb{R}}^2$. Let

$$A=\{x\in M:{(x_1-1)}^2+x_2^2\le 5,{(x_1+1)}^2+x_2^2\le 5,y_2\ge 1\},$$

which is obviously a closed and convex subset of $M={\mathbb{R}}_{++}^2$, and $f,h:A\to \mathbb{R}$is defined as

$$f\left(x\right)=1+x_1^2{x}_2^{-2},h\left(x\right)={\displaystyle \frac{1}{2}}\left(\right|{\displaystyle \frac{x_1^2+x_2^2}{x_2}}-{\displaystyle \frac{2}{x_2}}\left|+{\displaystyle \frac{x_1^2+x_2^2}{x_2}}+{\displaystyle \frac{2}{x_2}}\right),$$

and then $V\left(x\right)$ and $U\left(x\right)$ are given by $V\left(x\right)=gradf\left(x\right)=(2x_1,-2x_1^2{x}_2^{-3})$, and

$$U\left(x\right)=gradh\left(x\right)=\left\{\begin{array}{cc}(2x_1{x}_2,x_2^2-x_1^2),\hfill & x_1^2+x_2^2>2;\hfill \\ \left\{(2t{x}_1{x}_2,t(x_1^2-x_2^2+2)-2):t\in [0,1]\right\},\hfill & x_1^2+x_2^2=2;\hfill \\ (0,-2),\hfill & x_1^2+x_2^2<2.\hfill \end{array}\right.$$

We know that V and U are pseudomonotone vector fields. We can easily check that the bilevel variational inequalities on $M={\mathbb{R}}_{++}^2$ have a solution $(0,\sqrt{2})$. Hence, the sequences $\left\{x^k\right\}$ and $\left\{z^k\right\}$ generated by the method presented in this paper converges to a solution of bilevel variational inequalities.

5. Conclusions

In this work, we introduce the concept of pseudomonotone vector fields, and delve into bilevel variational inequalities on Riemannian manifolds. Subsequently, we propose a variant of Korpelevich’s method specifically tailored to solve bilevel variational inequalities on Riemannian manifolds characterized by non-negative sectional curvature and pseudomonotone vector fields.

Furthermore, we establish the convergence of the iteration sequences produced by our proposed algorithm under mild conditions. Additionally, we provide an example to showcase the validity and convergence properties of our algorithm.