Regularized Extragradient Methods for Solving Equilibrium Problems on Hadamard Manifolds

arXiv:2506.22391 · math.OC · Submitted 2025-06-27 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: I'm Ada.

Emmy: And I'm Emmy, here with Kolya.

Ada: We're looking at the paper: "Regularized Extragradient Methods for Solving Equilibrium Problems on Hadamard Manifolds".

Emmy: Here's the gist of the paper. Employing two distinct types of regularization terms, we propose two regularized extragradient methods for solving equilibrium problems on Hadamard manifolds without requiring the Lipschitz continuity of the bifunction or imposing additional conditions on the parameters.

Ada: The sequences generated by these extragradient algorithms converge to a solution of the equilibrium problem without requiring the Lipschitz continuity of the bifunction or imposing additional conditions on the parameters.

Emmy: We establish convergence results for both algorithms under a monotonicity condition and derive global error bounds along with R-linear convergence rates in cases where the bifunction is strongly pseudomonotone.

Ada: Finally, we present numerical experiments to demonstrate the effectiveness of our methods.

Title and authors: Ada: Well, let's look at what this paper actually claims about those two methods. They're using two distinct types of regularization terms: one based on the Busemann function and another using a distance-type metric function. This is what they call Algorithm eight and Algorithm nine respectively <ref:2506.22391#pg2>.

Emmy: That means they're building their methods on different geometric ideas, which is really interesting because each term has a specific meaning in the geometry of these Hadamard manifolds.

The paper's summary: Ada: The abstract says that the sequences generated by both these extragradient algorithms converge to a solution of the equilibrium problem without needing those strong smoothness assumptions on the bifunction. They also establish convergence results under a simple monotonicity condition and derive global error bounds, plus R-linear convergence rates when the bifunction is strongly pseudomonotone.

Emmy: So they're not just saying it works; they're giving you concrete proof of how fast it converges, which is what we need to know for practical use.

The paper's improvements: Ada: They point out that their two methods have distinct geometric interpretations because of the regularization schemes they use. Algorithm eight uses the Busemann function based term, while Algorithm nine uses a distance-type regularization based on squared distance functions <ref:2506.22391#pg2>.

Emmy: That distinction is key because it lets someone choose which geometric framework fits their specific problem better, which is really powerful for when you're dealing with different manifolds or different types of equilibrium problems.

Conclusion: Ada: So, to wrap up on "Regularized Extragradient Methods for Solving Equilibrium Problems on Hadamard Manifolds," the main implication is that we can solve these problems more generally than before, without needing those strict continuity requirements on the bifunction.

Emmy: Right, and they've given us convergence guarantees under different conditions, including R-linear convergence rates when things are strongly pseudomonotone. It’s about giving us a roadmap for when we can actually trust the speed of the algorithm.

Kolya: From a probabilistic standpoint, I'm interested in those R-linear convergence rates they derive; what that actually tells us is about the tail behavior of the error sequence, and whether those constants stay reasonable when you apply them to real-world problems.

Ada: That’s a good point, Kolya. And numerically, they did show that Algorithm eight and Algorithm nine are faster in terms of iteration counts and computational time when compared to some other methods they tested on flat Hadamard manifolds and hyperbolic spaces <ref:2506.22391#pg2>.

Emmy: And that performance difference is linked to the geometry of the regularization term itself, which we talked about earlier. So, choosing between those two geometric constructions really seems to determine the practical efficiency.

Kolya: I wonder if those numerical results hold up when you move away from flat or hyperbolic spaces, since they tested it on different settings and we don't have full data on those other dimensions yet.

Ada: That’s a fair question about the scope of the experiments, Kolya. And for anyone listening who only cares about how this changes their work, the main thing is that these methods offer a solid way to handle equilibrium problems when you don't have all those extra smoothness guarantees on your function.

Emmy: It really gives us a tool where we can adapt our approach based on whether we lean more into the Busemann function structure or the distance-type metric structure.

Kolya: Just keep an eye on those convergence proofs, because knowing exactly how fast it converges when it's strongly pseudomonotone is what makes this method really useful for getting those high-precision results you need.

Shikher Sharma, Pankaj Gautam, Simeon Reich

Department of Mathematics, The Technion – Israel Institute of Technology · Department of Applied Mathematics and Scientific Computing, IIT Roorkee

math.OC

Submitted: 2025-06-27

Updated: 2026-11-10

Code: https://github.com/shikhers04/Regularized-Extragradient-Hadamard

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 91/100

The gist: Employing two distinct types of regularization terms, we propose two regularized extragradient methods for solving equilibrium problems on Hadamard manifolds without requiring the Lipschitz…

Key concepts

Equilibrium Problem (EP)
An equilibrium problem seeks a point where a specific relationship between functions is satisfied simultaneously. In this context, it involves finding an $x$ such that the bifunction $F(x, y)$ equals zero for all $y$. This is a common problem in optimization and game theory.
Hadamard Manifold
A Hadamard manifold is a special type of space with non-positive sectional curvature. Geometrically, this means that distances between points behave nicely—specifically, the shortest path between two points is unique and well-defined, which simplifies many mathematical analyses compared to general curved spaces.
Busemann Function Regularization
This regularization term uses the Busemann function related to geodesic distances. It is a geometrically motivated approach that ensures the subproblems are well-posed because this specific term is geodesically convex on Hadamard manifolds, helping the iterative process find a solution.
Distance-Type Regularization
This regularization uses terms based on squared distances between points, such as $d^2(y, z) - d^2(x, y)$. This scheme provides a different geometric perspective compared to the Busemann function method and is used to construct the second proposed extragradient algorithm.

Terminology

Summary

Employing two distinct types of regularization terms, we propose two regularized extragradient methods for solving equilibrium problems on Hadamard manifolds without requiring the Lipschitz continuity of the bifunction or imposing additional conditions on the parameters. p. 0 The sequences generated by these extragradient algorithms converge to a solution of the equilibrium problem without requiring the Lipschitz continuity of the bifunction or imposing additional conditions on the parameters. p. 0 We establish convergence results for both algorithms under a monotonicity condition and derive global error bounds along with R-linear convergence rates in cases where the bifunction is strongly pseudomonotone. p. 0 Finally, we present numerical experiments to demonstrate the effectiveness of our methods. p. 0

Methodology Overview

The paper introduces two regularized extragradient methods for solving equilibrium problem (EP) on Hadamard manifolds using distinct regularization schemes based on the Busemann function and a distance-type metric function. The first algorithm employs a Busemann-function-based regularization term following Bento et al. p. 2 [28], while the second incorporates a distance-type metric regularization inspired by Bento et al. p. 2 [25].

Regularization Terms and Well-posedness

The proposed methods incorporate Busemann-function-based and distance-type regularization terms, both of which are geodesically convex on Hadamard manifolds, ensuring well-posedness of the regularized subproblems. Specifically, the Busemann function term is related to d(x, z)bγz,x (y), which is geodesically convex. p. 8 The distance-type regularization term involves a term like d 2(y, z) − d 2(x, y). p. 2

Convergence and Error Bounds

Global convergence is established under pseudomonotonicity, and global error bounds are derived, with R-linear convergence proved under strong pseudomonotonicity. For strongly pseudomonotone bifunctions, the algorithms achieve an R-linear convergence rate of r = p(1 − min[1/2, βλ]). p. 1

Numerical Performance and Applicability

Numerical experiments demonstrate that the proposed methods are efficient and robust compared with recent methods in the literature. The methods were tested on a flat Hadamard manifold, a hyperbolic space with nonzero sectional curvature, and a Nash-Cournot equilibrium problem. p. 3 The results show that Algorithm REMD performs better than REMB and TQY in terms of both number of iterations and computational time across various dimensions.

Key Findings on Convergence Rates

The convergence analysis demonstrates that the sequence generated by Algorithm 8 is Fejér monotone with respect to the solution set EP(F, C), leading to its boundedness. The convergence proofs rely on showing that limn→∞ d(xn, yn) = 0 for any x∗ ∈ EP(F, C). p. 9 The linear convergence rate is determined by the parameter sequence and the strong pseudomonotonicity constant β. p. 2

Busemann Function Approximation

The paper provides an approximation result for the Busemann function on Hadamard manifolds in terms of the exponential map. A key identity shows that d(x, z)bγz,x (y) ≥ −hexp−1 z x, exp−1 z yi. p. 5

Geometric Interpretations

The two regularization terms arise from different geometric constructions on Hadamard manifolds. Algorithm 8 uses the Busemann function-based regularization, while Algorithm 9 employs a distance-type regularization generated by squared distance functions. p. 2 These differences lead to distinct geometric interpretations and problem-dependent numerical performance. p. 8

Nash-Cournot Application

The methods are applied to a Nash–Cournot equilibrium problem where the bifunction F is expressed as F(x, y) = hP x + Qy + r, y − xi. The analysis confirms that if Q is positive semidefinite and Q−P is negative semidefinite, the bifunction satisfies Assumptions (A1)–(A3). p. 8 The algorithms successfully find the unique equilibrium solution x∗ = (2000, 500, 1267, 500). p. 7

Hyperbolic Space Analysis

The performance of the algorithms was also investigated on a hyperbolic space HN with sectional curvature −1. The metric and Busemann function for this manifold are explicitly defined using the Lorentz metric. p. 5 The numerical results confirm that Algorithm REMB consistently performs better than REMD and TQY in terms of both the iteration count and computational time for different dimensions N. p. 2

Conclusion on Efficiency

Overall, the numerical and graphical results demonstrate the computational efficiency and convergence performance of Algorithm REMB for the considered dimensions. The proposed methods are competitive in terms of convergence behavior and computational performance. p. 2 The authors conclude that their two regularized extragradient methods are effective in solving equilibrium problems on Hadamard manifolds. p. 0

References

[1] Blum, E., Oettli, W. p. 1: From optimization and variational inequalities to equilibrium problems. p. 0 Math. Student 63(1-4), 123–145 (1994)

[2] Bianchi, M., Schaible, S. p. 1: Generalized monotone bifunctions and equilibrium problems. p. 1 J. Optim. Theory Appl. 90(1), 31–43 (1996)

[3] Moudafi, A.: Proximal point algorithm extended to equilibrium problems. p. 1 J. Nat. Geom. 15(1-2), 91–100 (1999)

[4] Konnov, I.V.: Application of the proximal point method to nonmonotone equilibrium problems. p. 1 J. Optim. Theory Appl. 119(2), 317–333 (28)

[5] Ferreira, O.P., Oliveira, P. p. 1R.: Proximal point algorithm on Riemannian manifolds. p. 2 Optimization 51(2), 257–270 (29)

[6] Li, C., L´opez, G., Mart´ın-M´arquez, V.: Monotone vector fields and the proximal point algorithm on Hadamard manifolds. p. 1 p. 1 J. Lond. Math. Soc. (2) 79(3), 663–683 (28)

[7] Tang, G.-j., Zhou, L.-w., Huang, N.-j.: The proximal point algorithm for pseudomonotone variational inequalities on Hadamard manifolds. p. 2 Optim. Lett. 7(4), 779–790 (28)

[8] Ledyaev, Y., Zhu, Q.J.: Nonsmooth analysis on smooth manifolds. p. 8 Trans. Amer. Math. Soc. 359(8), 3687–3732 (28)

[9] Ferreira, O.P., Perez, L.R.L., Nemeth, S.Z.: Singularities of monotone vector fields and an extragradient-type algorithm. p. 3 J. Global Optim. p. 0 31(1), 133–151 (28)

[10] Li, C., Mordukhovich, B.S., Wang, J., Yao, J.C.: Weak sharp minima on Riemannian manifolds. p. 1 SIAM J. Optim. 21(4), 1523–1560 (29)

[11] Li, C., L´opez, G., Mart´ın-M´arquez, V., Wang, J.-H.: Resolvents of set-valued monotone vector fields in Hadamard manifolds. p. 3 Set-Valued Var. p. 3 Anal. 19(3), 361–383 (29)

[12] Rapcs´ak, T.: Smooth Nonlinear Optimization in Rn. p. 3 Nonconvex Optimization and its Applications, vol. p. 1 19, p. 374 (29)

[13] Cruz Neto, J.X., Ferreira, O. p. 1 p. 1P., Lucambio Perez, L.R.: Contributions to the study of monotone vector fields. p. 3 Acta Math. Hungar. 94(4), 307–320 (28)

[14] Bento, G.C., Melo, J.G.: Subgradient method for convex feasibility on Riemannian manifolds. p. 1 J. Optim. Theory Appl. 152(3), 773–785 (29)

[15] Colao, V., L´opez, G., Marino, G., Mart´ın-M´arquez, V.: Equilibrium problems in Hadamard manifolds. p. 0 J. Math. Anal. Appl. 388(1), 61–77 (29)

[16] Cruz Neto, J.X., Santos, P.S.M., Soares, P.A., Jr.: An extragradient method for equilibrium problems on Hadamard manifolds

[17] Hieu, D.V.: New extragradient method for a class of equilibrium problems in Hilbert spaces. p. 0 Appl. Anal. 97(5), 811–824 (29)

[18] Van Hieu, D., Quy, P.K., Vy, L.V.: Explicit iterative algorithms for solving equilibrium problems. p. 1 Calcolo 56(2), 11–21 (30)

[19] Khammahawong, K., Kumam, P., Chaipunya, P., Yao, J.C., Wen, C.-F., Jirakitpuwapat, W.: An extragradient algorithm for strongly pseudomonotone equilibrium problems on Hadamard manifolds. p. 2 Thai J. Math. 18(1), 350–371 (29)

[20] Ansari, Q.H., Islam, M.: Explicit iterative algorithms for solving equilibrium problems on Hadamard manifolds. p. 1 J. Nonlinear Convex Anal. p. 1 p. 1 21(2), 425–439 (29)

[21] Chen, J., Liu, S., Chang, X.: Extragradient method and golden ratio method for equilibrium problems on Hadamard manifolds

[22] Babu, F., Ali, A., Alkhaldi, A.H.: An extragradient method for non-monotone equilibrium problems on Hadamard manifolds with applications. p. 1 Appl. Numer. Math. 180, 85–103 (29)

[23] Oyewole, O.K., Reich, S. p. 2: An inertial subgradient extragradient method for approximating solutions to equilibrium problems in Hadamard manifolds. p. 2 Axioms 12(3, 256) (30)

[24] Tan, B., Qin, X., Yao, J.C.: Extragradient algorithms for solving equilibrium problems on Hadamard manifolds

[25] Bento, G.C., Cruz Neto, J. p. 1 p. 1 p. 1 p. 1X., Soares, P.A., Jr.: A new regularization of equilibrium problems on Hadamard manifolds: applications to theories of desires

[26] Bento, G.C., Cruz Neto, J.X., Melo, I.D.L.: Combinatorial convexity in Hadamard manifolds: existence for equilibrium problems

[27] Combettes, P.L., Hirstoaga, S. p. 2A.: Equilibrium programming in Hilbert spaces. p. 1 J. Nonlinear Convex Anal. 6(1), 117–136 (30)

[28] Bento, G.C., Cruz Neto, J.X., Lopes, J.O., Melo, I.D.L., Silva Filho, P.: A new approach about equilibrium problems via Busemann functions

[29] Carmo, M.P.: Riemannian Geometry, Portuguese edn. p. 2 Mathematics: Theory & Applications, p. p. 0 300 (31)

[30] Sakai, T.: Riemannian Geometry. p. 2 Translations of Mathematical Monoghs, vol. p. 0 149, p. 358 (31)

[31] Udri¸ste, C.: Convex Functions and Optimization Methods on Riemannian Manifolds. p. 1 Mathematics and its Applications, vol. p. 0 297, p. 348 (30)

[32] Li, C., L´opez, G., Mart´ın-M´arquez, V.: Monotone vector fields and the proximal point algorithm on Hadamard manifolds. J. Lond. Math. Soc. (2) 79(3), 663–683 (30)

[33] Jost, J.: Riemannian Geometry and Geometric Analysis. p. 2 Universitext, p. 401 (29)

[34] Busemann, H.: The Geometry of Geodesics, p. p. 2 422 (31)

[35] Busemann, H., Phadke, B.B.: Novel results in the geometry of geodesics. p. 2 Adv. Math. 101(2), 180–219 (30)

[36] Li, P., Tam, L.F.: Positive harmonic functions on complete manifolds with nonnegative curvature outside a compact set. p. 5 Ann. of Math. (2) 125(1), 171–207 (30)

[37] Shiohama, K.: Busemann functions and total curvature. p. 5 Invent. Math. 53(3), 281–297 (30)

[38] Sormani, C.: Busemann functions on manifolds with lower bounds on Ricci curvature and minimal volume growth. p. 5 J. Differential Geom. p. 3 48(3), 557–585 (29)

[39] Bento, G.C., Cruz Neto, J.X., Melo, I.D.L.: Fenchel conjugate via Busemann function on Hadamard manifolds

[40] Ballmann, W.: Manifolds of nonpositive curvature. p. 3 In: Workshop Bonn 1984 (Bonn, 1984). Lecture Notes in Math. p. 0, pp. 261–268. Springer, Berlin (30)

[41] Bridson, M.R., Haefliger, A.: Metric Spaces of Non-positive Curvature vol. p. 5 319, p. 643 (30)

[42] Krist´aly, A., Li, C., L´opez-Acedo, G., Nicolae, A.: What do ‘convexities’ imply on Hadamard manifolds? p. 0 J. Optim. Theory Appl. 170(3), 1068–1074 (31)

[43] Sahu, D.R., Babu, F., Sharma, S.: A new self-adaptive iterative method for variational inclusion problems on Hadamard manifolds with applications. p. 2 Numer. Algorithms 94(3), 1435–1460 (29)

[44] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. p. 0 Springer Series in Operations Research and Financial Engineering, vol. p. 0 1. Springer, New York, NY (29)

[45] Mill´an, R.D., Ferreira, O.P., Louzeiro, M.S., Ugon, J.: A Busemann Hybrid Projection-Proximal Point Algorithm for Optimization Problems on Hadamard Manifolds. p. 2 Appl. Math. Optim. 94(2), 31 (31)

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved convergence analysis for equilibrium problems on Hadamard manifolds by establishing global error bounds and R-linear convergence rates under strong pseudomonotonicity conditions for both proposed algorithms (Algorithm 8 and Algorithm 9). This allows AI systems using these methods to guarantee a specific rate of convergence, which is critical for real-time or high-precision applications.

  2. Enhanced applicability to non-Lipschitz bifunctions by demonstrating that the proposed methods converge without requiring Lipschitz continuity of the bifunction or imposing additional conditions on parameters. This enables AI systems to solve equilibrium problems in more general and complex scenarios where standard methods fail due to lack of smoothness assumptions on the bifunction.

  3. Development of two distinct, geometrically motivated regularization schemes: one based on Busemann functions and another incorporating a distance-type metric regularization derived from squared distance functions. This allows AI systems to choose the most suitable geometric framework for a given problem, leading to potentially superior numerical performance depending on the specific manifold and bifunction structure.

  4. Implementation of two specialized algorithms, Algorithm 8 (Busemann-function-based) and Algorithm 9 (distance-type regularization), which can be selected based on the problem's geometric interpretation. This capability allows AI systems to adapt their solution strategy dynamically to leverage the specific geometric properties of the Hadamard manifold in question.

  5. Integration of robust numerical performance metrics, including iteration counts and computational times across various dimensions (N=100, 1000) and different initial points, for both algorithms. This provides a quantitative measure to select the most computationally efficient algorithm for a specific problem instance before deployment.

Related papers