🔢 mathematics

The Generalized Fermat-Torricelli-Weber Problem

This paper introduces a new generalized Fermat–Torricelli–Weber problem and a corresponding subgradient algorithm within a unified Hilbert space framework that connects it to mixed split feasibility problems, establishing convergence results and demonstrating practical applications in image deblurring.

Original authors: SUBRATA RANA, Binayak S. Choudhury

Published 2026-07-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: SUBRATA RANA, 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 you are a master planner trying to solve a series of complex location puzzles. You need to find the "perfect spot" that balances several competing demands at once. This paper introduces a new, more powerful way to solve these puzzles, especially when the rules are a bit fuzzy or "bumpy" (mathematically speaking, non-smooth).

Here is a breakdown of the paper's ideas using simple analogies:

1. The Classic Puzzle: Finding the Best Meeting Spot

The story starts with an old idea called the Fermat-Torricelli-Weber problem.

The Analogy: Imagine you have three friends living in different houses. You want to build a new coffee shop such that the total walking distance for all three friends to get there is as short as possible.
The Twist: In this paper, the authors don't just look for a spot in a flat city (2D). They look for a spot in a vast, multi-dimensional "universe" (called a Hilbert space). Furthermore, instead of just finding a spot for three friends, they are dealing with a massive network of constraints:
- Some friends live in specific neighborhoods (convex sets).
- Some rules require the coffee shop to be a certain distance from a specific landmark.
- Some rules require the shop to be in a specific zone.

The goal is to find the one spot that minimizes the "friction" or total distance to all these different requirements.

2. The Problem with "Bumpy" Hills

In math, finding the lowest point on a smooth hill is easy. But in the real world, the "hill" (the objective function) is often bumpy or jagged.

The Analogy: Imagine trying to roll a ball down a mountain. If the mountain is smooth, you just follow the slope. But if the mountain is covered in jagged rocks and cliffs, you can't just follow a single smooth line down. You have to feel around the rocks to find the steepest path down.
The Paper's Solution: The authors created a new Subgradient Algorithm. Think of this as a smart robot that doesn't need a smooth slope. When it hits a "rock" (a non-smooth point), it is allowed to pick any valid direction that points somewhat downhill. It doesn't need the perfect direction; it just needs a valid direction to keep moving toward the solution. This flexibility makes the algorithm much more robust.

3. Connecting Different Worlds (The Unified Framework)

The authors realized that their new "coffee shop" puzzle is actually the same as two other famous puzzles in the optimization world:

The Split Feasibility Problem (SFP): Imagine you are in a room (Set A) and you need to find a spot where, if you look through a window (a mathematical operator), you see a specific pattern in the next room (Set B).
The Split Equality Problem (SEP): Imagine two different teams working in different rooms. They need to find a solution where their outputs, when processed, end up being exactly equal.

The Big Claim: The paper claims to be the first to show that all these different puzzles (the coffee shop, the window view, and the team equality) are actually just different versions of the same underlying structure. They built a "universal translator" (a unified framework) that can solve all of them using the same set of rules.

4. How the Algorithm Works

The paper proposes two main ways to solve these puzzles:

The Basic Walker (Algorithm 3.1): This is a step-by-step process. You take a step, check if you are getting closer, and adjust. The paper proves that if you take small enough steps over a long time, you will eventually reach the solution.
The Guided Walker (Algorithm 4.1): This version adds a "guide" (a contraction mapping). Imagine a GPS that not only tells you which way is down but also gently pulls you toward a specific target point to ensure you don't get stuck in a loop. The paper proves this version converges faster and more reliably.

5. Testing the Theory: From Math to Images

To prove their math works, the authors ran computer simulations.

The Test: They created random "puzzles" with different numbers of constraints and dimensions to see if their algorithms could find the solution.
The Real-World Application: They applied their method to Image Deblurring.
- The Analogy: Imagine taking a photo of a moving car, but the camera shook, making the photo blurry. The "blur" is like the noise in the math problem. The original, sharp photo is the "solution" hidden inside the blur.
- The Result: Their algorithm successfully took a blurry image and reconstructed a sharp one. They measured the quality using a score called SNR (Signal-to-Noise Ratio). Their method produced sharper images (higher SNR) compared to other standard methods.

Summary

In short, this paper says:

We invented a new, flexible way to solve complex location puzzles in high-dimensional spaces.
We proved that this method works mathematically (it will eventually find the answer).
We showed that this method is actually the "parent" of several other famous math problems, unifying them under one roof.
We tested it on computers and showed it can fix blurry photos, proving it works in the real world.

The authors emphasize that their method is unique because it allows the computer to be "flexible" when hitting rough spots in the math, making it a powerful tool for optimization.

Technical Summary: The Generalized Fermat-Torricelli-Weber Problem

Problem Formulation
This paper introduces a new Generalized Fermat-Torricelli-Weber (FTW) problem within the framework of real Hilbert spaces. The problem is formulated as a constrained minimization task:
$\min_{x \in D} \zeta(x)$
where $D$ is a non-empty, closed, and convex subset of a Hilbert space $H$ . The objective function $\zeta(x)$ is defined as:
$\zeta(x) = \left\| \sum_{i=1}^{L} B_i(A_i x) - \tilde{y} \right\|_K + \sum_{i=1}^{L} \sum_{j=1}^{m_i} t_{ij} \| A_i x - P_{C_{ij}}(A_i x) \|_{H_i}$
Here, $A_i: H \to H_i$ and $B_i: H_i \to K$ are bounded linear operators; $C_{ij}$ are non-empty, closed, convex subsets of $H_i$ ; $P_{C_{ij}}$ denotes the metric projection onto $C_{ij}$ ; $\tilde{y}$ is a fixed element in $K$ ; and $t_{ij}$ are positive real weights. The function $\zeta(x)$ is non-smooth and convex.

The authors demonstrate that this generalized framework encompasses several existing problems as special cases, including the classical Fermat-Weber location problem, the generalized Fermat-Torricelli problem, the Split Feasibility Problem with multiple output sets (SFP-MOS), and the Split Equality Problem (SEP).

Methodology
To solve the non-smooth optimization problem, the authors develop a subgradient algorithm (Algorithm 3.1). A distinguishing feature of this approach is the flexibility in selecting the subgradient; the algorithm allows for the choice of an arbitrary element from the subdifferential $\partial \zeta(x_n)$ at each iteration, rather than requiring a specific selection rule.

The iterative scheme is given by:
$x_{n+1} = P_D^H (x_n - \sigma_n g_n)$
where $g_n$ is an arbitrary element from the subdifferential of the objective function, and $\sigma_n$ is a sequence of positive step sizes.

The paper analyzes two distinct convergence regimes based on the step-size sequence $\{\sigma_n\}$ :

Standard Subgradient Regime: When $\lim_{n \to \infty} \sigma_n = 0$ and $\sum \sigma_n = \infty$ , the authors prove that the sequence of minimum values $M_n = \min_{1 \le k \le n} \zeta(x_k)$ converges to the optimal value. Furthermore, if $\sum \sigma_n^2 < \infty$ , the sequence $\{x_n\}$ contains a subsequence that converges weakly to a solution. In finite-dimensional spaces, this implies strong convergence.
Adaptive Step-Size Regime (for MSFP-MOS): When the optimal value is known to be zero (as in the Mixed Split Feasibility Problem with multiple output sets, MSFP-MOS), the authors propose an adaptive step-size rule:
$\sigma_n = \frac{\tau_n \zeta(x_n)}{\|g_n\|^2 + \beta_n}$
where $\tau_n \in [a, b] \subset (0, 2)$ and $\{\beta_n\}$ is a bounded positive sequence. Under these conditions, the sequence $\{x_n\}$ is proven to converge weakly to a solution of the MSFP-MOS.

Additionally, the paper introduces a viscosity approximation method (Algorithm 4.1) involving a strict contraction mapping $f$ . This variant is shown to yield strong convergence to the unique solution of a specific variational inequality associated with the problem.

Key Contributions

Unified Framework: The paper establishes a unified framework connecting the Generalized FTW problem with the Split Equality Problem (SEP) and the Split Feasibility Problem with multiple output sets (SFP-MOS). To the authors' knowledge, this is the first work to explicitly connect these problems within a single generalized structure.
Arbitrary Subgradient Selection: The proposed algorithm permits the selection of an arbitrary element from the subdifferential of the non-smooth objective function, offering greater flexibility compared to existing methods that may require specific subgradient choices.
Convergence Analysis: The authors establish both weak and strong convergence theorems for the proposed algorithms under various conditions on the step sizes and the underlying Hilbert space (finite vs. infinite dimensional).
Application to Image Deblurring: The theoretical framework is applied to the image deblurring problem, formulating it as a specific instance of the generalized FTW problem.

Results and Numerical Experiments
The theoretical results are validated through numerical experiments implemented in MATLAB R2025(a).

Synthetic Data: Experiments on synthetic convex sets and linear operators demonstrate the convergence behavior of the algorithms (labeled Algorithm X, Y, Z, 5.1, 5.2, 5.3, and 5.4). The results show that the adaptive step-size algorithms generally converge faster and with fewer iterations compared to fixed step-size approaches.
Image Deblurring: The framework is applied to restore blurred images (Cameraman and Tire datasets) degraded by a Gaussian kernel. The performance is measured using Signal-to-Noise Ratio (SNR). The numerical results indicate that the proposed algorithms successfully recover the images, with Algorithm 5.2 (the strong convergence variant) achieving slightly higher SNR values than Algorithm 5.1 in the tested scenarios.

Significance and Claims
The authors claim that this work extends and generalizes several existing approaches in the literature. The primary significance lies in the introduction of a new generalized problem model that unifies location theory (FTW) with split feasibility problems. By developing a subgradient algorithm that allows for arbitrary subgradient selection and proving its convergence properties, the paper provides a robust theoretical tool for solving non-smooth optimization problems in Hilbert spaces. The application to image deblurring serves to demonstrate the practical utility of the proposed framework in solving real-world inverse problems.