🔢 mathematics

Proximal Point Algorithms in Hadamard Spaces and Generalized Fermat-Torricelli Problem

This paper develops a double sum inexact cyclic proximal point algorithm for Hadamard spaces, establishing its linear and superlinear convergence under metric subregularity, proving finite termination via weak sharp minima, and applying these results to solve a new generalized Fermat–Torricelli problem with explicit resolvent formulas and numerical validation.

Original authors: Kumaresh Kundu, Debashish Paul, Binayak S. Choudhury

Published 2026-10-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kumaresh Kundu, Debashish Paul, Binayak S. Choudhury

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where the ground beneath your feet is not flat, but curved, like the surface of a sphere or a saddle. In such a place, the shortest path between two points is not a straight line, but a curve that follows the contours of the land. This is the realm of non-Euclidean geometry, a field that has fascinated mathematicians for centuries because it describes the actual shape of our universe and many complex data structures used in modern technology. Within this curved landscape, there is a classic puzzle known as the Fermat-Torricelli problem. It asks a simple question: if you have several fixed points scattered across this terrain, where is the single spot that minimizes the total distance to all of them? Think of it as finding the perfect location for a new town that needs to be as close as possible to several existing villages. While this problem has been solved for flat surfaces for hundreds of years, finding the answer on a curved, complex surface has remained a difficult challenge for modern optimization theory.

A team of researchers from India and South Africa has now developed a powerful new method to solve this puzzle in these curved spaces. They created a step-by-step algorithm, a kind of mathematical compass, that guides a traveler toward the perfect spot. The researchers call their environment a "Hadamard space," which is a specific type of curved landscape where the rules of geometry are well-behaved and predictable, even though the ground is not flat. Their approach is unique because it combines three different types of difficult problems into one unified solution. Instead of tackling the location problem, the problem of finding a point that fits within several overlapping regions, and the problem of finding the closest point to a specific area separately, their method solves them all at once. This is achieved by using a "double sum" structure, which allows the algorithm to handle complex layers of constraints without getting lost.

The core of their discovery is a process called the proximal point algorithm. In simple terms, this is a technique where you take a current guess at the solution, look around to see which direction reduces the total distance, and then take a step in that direction. However, in these curved spaces, taking a step is not as simple as moving forward; it involves following a specific curve called a geodesic. The researchers improved this process by making it "inexact," meaning the algorithm does not need to calculate every single step with perfect precision to work. This is crucial for real-world applications where calculations can be noisy or incomplete. They proved that their method works reliably and, under certain conditions, converges to the solution very quickly. In fact, they showed that if the problem has a single, unique solution, the algorithm can find it in a finite number of steps, stopping exactly when the answer is reached rather than just getting closer and closer forever.

To ensure their method was robust, the team tested it against a specific mathematical condition called metric subregularity. This condition essentially checks how sharply the landscape slopes away from the solution. If the slope is steep enough, the algorithm is guaranteed to find the answer rapidly. They also explored a scenario involving "weak sharp minima," a concept that describes a solution set with a very distinct, sharp boundary. When this condition is met, their algorithm does not just approach the answer; it lands on it and stops. This is a significant improvement over older methods that might wander indefinitely near the solution without ever settling. The researchers validated their theory with numerical experiments, simulating the process on a specific curved space that behaves like a logarithmic scale. In one test, they started with a point far from the target and watched the algorithm converge to the correct location with extreme precision, reaching a level of accuracy where the error was smaller than one part in a quintillion.

The implications of this work extend far beyond abstract mathematics. The ability to solve optimization problems in curved spaces is vital for fields like network design, where data flows through complex, non-linear pathways, and in statistics, where data often exists in high-dimensional, curved shapes. By replacing the rigid tools of flat geometry with flexible tools that work on curved surfaces, the researchers have opened the door to more efficient ways of organizing information and solving logistical problems. Their work demonstrates that even in the most complex and curved environments, there are reliable, predictable paths to the best possible solution. The algorithm they built is not just a theoretical curiosity; it is a practical tool that can be applied to real-world scenarios where the geometry of the problem is as important as the data itself. Through rigorous proof and careful simulation, the team has shown that finding the perfect point in a curved world is not only possible but can be done with speed and certainty.

Technical Summary: Proximal Point Algorithms in Hadamard Spaces and Generalized Fermat-Torricelli Problem

1. Problem Statement and Context

The paper addresses the problem of locating a point that minimizes the sum of distances to given points or sets, a generalization of the classical Fermat-Torricelli problem. While this problem has a rich history in Euclidean spaces (Heron, Fermat, Torricelli, Steiner) and has been extended to Hilbert spaces and Riemannian manifolds, this work operates within the broader framework of Hadamard spaces (complete CAT(0) spaces).

The authors aim to unify three distinct convex minimization problems into a single framework:

The Weighted Fermat-Torricelli Problem.
The Convex Feasibility Problem.
The Best Approximation Problem.

The specific challenge lies in solving these problems in Hadamard spaces, which lack the global linear structure of Hilbert spaces. Consequently, standard tools like bounded linear operators must be replaced by continuous geodesic-preserving maps (affine maps in the metric sense). The paper investigates the convergence properties of inexact cyclic splitting proximal point algorithms (SPPA) for these problems, specifically focusing on:

$\Delta$ -convergence (weak convergence in the metric sense).
Strong convergence rates (linear and superlinear).
Finite termination under specific geometric conditions.

2. Methodology and Mathematical Framework

2.1 Geometric and Analytical Foundations

The study utilizes the geometry of Hadamard spaces, relying on:

Tangent Cones: Following Nikolaev's approach, the authors define tangent cones $T_x X$ to handle monotonicity without an exponential map, allowing the theory to apply to non-manifold spaces (e.g., $\mathbb{R}$ -trees, Hilbert balls).
Quasilinearization: Using the quasi-inner product $\langle \vec{ab}, \vec{cd} \rangle$ to generalize inner product properties.
Monotone Operators: Defined via the tangent bundle $TX$ and the condition $g_x(\eta, \mu_{x,y}) + g_y(\nu, \mu_{y,x}) \leq 0$ . The paper assumes the surjectivity condition for these operators, a necessary assumption in Hadamard spaces that is not automatically guaranteed as it is in Hilbert spaces.
Resolvents: The algorithm relies on the resolvent $J_r^A$ of a monotone operator $A$ , defined via Yosida-Moreau regularization.

2.2 Algorithmic Structure

The paper proposes and analyzes three levels of inexact cyclic splitting proximal point algorithms:

Basic Inexact PPA (Algorithm 1.1):
$\lambda_n d(y_n, x_n)\mu_{y_n, x_n} \in A(y_n), \quad d(x_{n+1}, y_n) \leq \epsilon_n$
This approximates a singularity of a single monotone operator $A$ .
Single-Sum Inexact Cyclic SPPA (Algorithm 1.2):
Designed for minimizing $f(x) = \sum_{i=1}^m f_i(x)$ . It cycles through resolvents:
$y_n = J_{r_n}^{f_m} \circ \dots \circ J_{r_n}^{f_1}(x_n), \quad d(x_{n+1}, y_n) \leq \epsilon_n$
Double-Sum Inexact Cyclic SPPA (Algorithm 1.3):
Designed for the generalized Fermat-Torricelli problem involving a double sum structure:
$f(x) = \sum_{i=1}^m \sum_{j=1}^{m_i} f_{i,j}(x)$
The iteration involves nested resolvent compositions:
$x_n^{(i,j)} = J_{r_n}^{f_{i,j}}(x_n^{(i,j-1)}), \quad y_n = x_n^{(m, m_m)}$
with $d(x_{n+1}, y_n) \leq \epsilon_n$ .

3. Key Contributions

The paper makes three primary contributions, bridging the gap between splitting algorithms and quantitative convergence theory in Hadamard spaces:

Double-Sum Inexact Cyclic Splitting PPA with Rate Theory:
The authors develop a double-sum version of the cyclic splitting algorithm tailored to the generalized Fermat-Torricelli problem. Unlike previous works that only established existence-type convergence (e.g., $\Delta$ -convergence), this paper establishes linear and superlinear convergence rates and finite termination results for these specific splitting schemes.
Metric Subregularity without Linear Structure:
The paper formulates metric subregularity directly using the distance in tangent cones ( $d_x(0_x, A(x))$ ), rather than relying on an exponential map to linearize the space. This definition applies to general Hadamard spaces (including those that are not manifolds), extending the rate theory of Kohlenbach et al. and others from Hilbert spaces and manifolds to the general CAT(0) setting.
Generalized Fermat-Torricelli via Geodesic-Preserving Maps:
The paper introduces a new formulation of the Fermat-Torricelli problem (Problem 6.1) involving geodesic-preserving (affine) mappings and distances to convex subsets. This extends previous linear/Hilbert formulations to the nonlinear Hadamard setting, unifying weighted distance minimization, feasibility, and best approximation.

4. Main Results

4.1 Convergence Analysis

$\Delta$ -Convergence: Under the assumption that the error sequence $\{\epsilon_n\}$ is summable, the sequences generated by the algorithms are shown to be quasi-Fejér monotone and $\Delta$ -converge to a solution in $A^{-1}(0)$ or the minimizer set $C$ .
Strong Convergence and Rates: By introducing metric subregularity (Definition 4.1), the authors prove that if the operator is metrically subregular, the algorithm converges linearly.
- Superlinear Convergence: The convergence becomes superlinear if the singularity set is a singleton and either the regularity modulus degenerates (i.e., the modulus is zero) or the proximal parameters $\lambda_n$ vanish ( $\lim \lambda_n = 0$ ).

4.2 Finite Termination

The paper introduces a weak sharp minima-type condition based on normal cones (Definition 5.1).

If the problem satisfies a global weak sharp minima-type condition with modulus $\alpha$ , and the operator $A(x)$ is a singleton for every $x$ in the solution set, the algorithm terminates in a finite number of steps.
This result is derived by showing that the weak sharpness condition implies metric subregularity, which forces the iterates to reach the solution set exactly once the error tolerance and step sizes satisfy specific bounds.

4.3 Application to Generalized Fermat-Torricelli

Existence: The paper proves that the objective function for the generalized problem is convex and lower semicontinuous. Under coercivity assumptions (conditions F1 and F2 in Theorem 6.1), a minimizer exists.
Subdifferential Properties: For the specific case of the weighted Fermat-Torricelli problem, the subdifferential is shown to be metrically subregular, validating the application of the convergence rate theorems.

5. Numerical Validation

The theoretical results are validated through numerical experiments in a specific Hadamard manifold ( $X = \mathbb{R}_{++}$ with a specific metric).

Example 7.1 (Superlinear Convergence): Solves a weighted Fermat-Torricelli problem. The results confirm linear convergence initially, transitioning to superlinear convergence as $\lambda_n \to 0$ , consistent with Theorem 6.3.
Example 7.2 (Finite Termination): Solves a best approximation problem. The sequence is shown to reach the solution set and terminate exactly after a finite number of iterations, validating Theorem 6.4 and the weak sharp minima condition.

6. Significance and Claims

The authors position this work as a unification of two previously distinct lines of research:

Splitting Algorithms: Previously, splitting schemes in Hadamard spaces (e.g., backward-backward schemes) focused on existence and weak convergence without addressing convergence rates or finite termination.
Quantitative Theory: Previous rate analyses (e.g., by Kohlenbach et al.) were largely confined to single-operator settings in Hilbert spaces or required manifold structures.

The paper claims:

It provides rate and finite termination theory for splitting algorithms (specifically double-sum cyclic schemes) in general Hadamard spaces, addressing a gap where these two lines of research "have not yet met."
It successfully extends the Fermat-Torricelli problem to a setting where linear operators are replaced by geodesic-preserving maps, maintaining the tractability of the problem through explicit resolvent formulas.
The methodology does not require the underlying space to be locally compact or a manifold, broadening the applicability of proximal point methods to spaces like $\mathbb{R}$ -trees and Hilbert balls.

The authors conclude that while the framework is established, a natural direction for future work is the extension to split feasibility problems involving multiple output sets in Hadamard spaces.