🔢 mathematics

Spectral conjugate gradient projection methods for large-scale monotone equations without Lipschitz continuity

This paper introduces two derivative-free spectral conjugate gradient projection methods for solving large-scale monotone equations under convex constraints, with the first method achieving global convergence without requiring Lipschitz continuity and both demonstrating effectiveness through extensive numerical experiments and real-world applications.

Original authors: Kabenge Hamiss, Mohammed Alshahrani, Mujahid N. Syed

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kabenge Hamiss, Mohammed Alshahrani, Mujahid N. Syed

Original paper licensed under CC BY 4.0 (http://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 trying to find a hidden treasure (the solution) in a vast, foggy landscape. The map you have is a set of rules (equations) that tell you how the terrain behaves. Your goal is to stand exactly where the rules say "zero" (the treasure spot).

The problem is that this landscape is huge (millions of dimensions, like a city with millions of streets) and the rules are weird (non-linear and monotone). You can't see the whole map at once, and you don't have a compass that points directly to the treasure (no derivatives). You can only take small steps, check the ground under your feet, and guess which way to go next.

This paper introduces two new, smarter ways to take those steps. Here is the breakdown using simple analogies:

1. The Old Way vs. The New Way

The Old Way (Newton's Method): Imagine trying to find the treasure by calculating the exact slope of every single hill and valley around you before taking a step. It's very precise, but it's so slow and requires so much memory that for a giant city-sized map, you'd run out of battery before you took your first step.

The Standard "Conjugate Gradient" Way: This is like a hiker who remembers the direction they just came from and uses that memory to guess the next best direction. It's fast and light, but sometimes the hiker gets stuck in a loop or takes a very inefficient path.

The New Methods (GMOPCGM and GCGPM): The authors created two new "hiking guides." They took the standard hiker's memory and added a smart, adaptive compass (called a "spectral parameter").

The Adaptive Compass: Instead of using a fixed rule for how big a step to take, this compass looks at the terrain right now. If the ground is steep, it adjusts the step size. If the ground is flat, it adjusts again. It's like a hiker who constantly checks the weather and the slope to decide, "Okay, today I'll take a giant leap," or "Today, I'll take a tiny shuffle."

2. The Two New Guides

The paper presents two specific versions of this smart hiker:

Guide 1 (GMOPCGM): This guide is built on a method called "Modified Optimal Perry." The authors tweaked it so the compass is even smarter.
- The Big Claim: This guide is so robust that it can find the treasure even if the map is jagged and unpredictable (mathematically, without "Lipschitz continuity"). Usually, you need a smooth, predictable map to guarantee you'll find the treasure. This guide says, "I don't care if the map is jagged; I'll still get there."
Guide 2 (GCGPM): This guide is built on the "Hager–Zhang" method. It uses a slightly different type of compass (based on "Dai–Liao" logic).
- The Big Claim: This guide is incredibly fast and efficient, but it assumes the map is at least somewhat smooth (Lipschitz continuous). Under this assumption, it is the fastest runner in the race.

3. The "Projection" Trick

Since the treasure might be hidden behind a wall (a "convex constraint"), the hikers can't just walk anywhere.

The Analogy: Imagine the treasure is inside a walled garden. If your step takes you outside the wall, you don't stop; you just bounce back to the nearest point on the wall.
Both new guides use this "bounce back" technique. They calculate a step, check if it hits the wall, and if it does, they project (bounce) the position back inside before taking the next step. This ensures they never leave the valid area.

4. The Race Results

The authors put these two new guides against the old guides and some other famous hikers in a massive race:

The Track: They tested them on 18 different types of terrain, ranging from small hills to mountains with 120,000 dimensions (imagine a maze with 120,000 corridors).
The Winners:
- GCGPM was the overall champion. It found the treasure in the fewest steps and the least amount of time in almost every scenario.
- GMOPCGM was a close second. It was slightly slower than GCGPM but proved it could handle the "jagged" maps that the others struggled with.
- Both new guides were significantly faster than their "parent" methods (the old guides they were based on).

5. Real-World Applications

The paper didn't just test them on fake math problems; they used them for two real-world tasks:

Compressed Sensing (Signal Recovery): Imagine trying to reconstruct a blurry, broken photo from very few pixels. The new guides were able to piece together the image (the signal) faster and more reliably than the old methods.
Logistic Regression (Machine Learning): This is used for sorting emails into "Spam" or "Not Spam." The new guides helped the computer learn the rules for sorting much faster, especially when dealing with huge amounts of data.

Summary

In short, this paper says: "We built two new, super-smart navigation tools for finding solutions in massive, complex problems. One is incredibly tough and works even on rough terrain; the other is the speed demon that wins on smooth terrain. Both are faster and more reliable than the tools we used to have, and they work great for things like fixing broken images and training AI."

Technical Summary: Spectral Conjugate Gradient Projection Methods for Large-Scale Monotone Equations

Problem Statement
The paper addresses the problem of finding a vector $x \in \Gamma$ such that $G(x) = 0$ , where $G: \mathbb{R}^n \to \mathbb{R}^n$ is a continuous monotone mapping and $\Gamma \subset \mathbb{R}^n$ is a nonempty, closed, and convex set. This formulation encompasses variational inequality problems, complementarity problems, chemical equilibrium computations, compressed sensing, and regularized logistic regression. While Newton-type methods offer rapid local convergence for differentiable $G$ , they are impractical for large-scale problems due to $O(n^2)$ storage requirements and the need to compute Jacobians. Conjugate gradient (CG) methods are preferred for large-scale settings as they require only function evaluations and $O(n)$ storage. However, extending CG methods to constrained settings typically relies on projection techniques, and existing methods often require Lipschitz continuity of $G$ or suffer from suboptimal convergence rates.

Methodology
The authors propose two derivative-free projection methods that integrate an adaptive spectral parameter $\lambda_k$ into established conjugate gradient frameworks. Both methods utilize the Solodov–Svaiter projection technique, which involves computing a descent direction, performing a line search to generate a trial point, constructing a separating hyperplane based on the monotonicity of $G$ , and projecting the current iterate onto this hyperplane.

GMOPCGM (Generalized Modified Optimal Perry Conjugate Gradient Method):
This method generalizes the Modified Optimal Perry Conjugate Gradient Method (MOPCGM) by Sabi'u et al. The search direction is derived from a modified optimal Perry matrix where the scaling parameter is replaced by an adaptive spectral parameter $\lambda_k$ . The parameter $\lambda_k$ is bounded within $[\alpha_{\min}, \alpha_{\max}]$ and is updated using Barzilai–Borwein-type spectral ratios based on the local curvature ( $s_{k-1}$ and $v_{k-1}$ ). The resulting search direction satisfies a sufficient descent condition independent of the line search.
GCGPM (Generalized Conjugate Gradient Projection Method):
This method generalizes the CGPM of Zheng et al., which is based on the Hager–Zhang parameter. The authors introduce a spectral Dai–Liao parameter $\lambda_k$ into the update formula. Similar to GMOPCGM, the spectral parameter adapts to the problem's local geometry. The search direction is constructed to ensure sufficient descent.

Key Contributions

Derivation of New Search Directions: The paper derives two new search directions that generalize existing MOPCGM and CGPM frameworks via a spectral parameter $\lambda_k$ .
Sufficient Descent Independence: It is proven that both proposed methods satisfy a sufficient descent condition ( $G_k^T p_k \leq -c \|G_k\|^2$ ) that holds independently of the line search strategy.
Global Convergence under Weaker Assumptions:
- For GMOPCGM, global convergence is established under Assumptions A1 (nonempty solution set) and A2 (monotonicity) alone. Crucially, this result does not require the Lipschitz continuity of $G$ .
- For GCGPM, global convergence is proven under the standard assumptions A1–A3, which include Lipschitz continuity.
Practical Effectiveness: The methods are tested on 18 benchmark problems with dimensions up to 120,000, as well as applications in compressed sensing and regularized logistic regression.

Numerical Results
The authors conducted extensive numerical experiments comparing GMOPCGM and GCGPM against three existing methods: MOPCGM, CGPM, and STTDFPM.

Benchmark Problems: Across 5,400 runs (18 problems, 6 dimensions, 10 initial points), GCGPM achieved the highest convergence rate (96.9%) and the lowest median iteration count (10) and function evaluations (52). GMOPCGM converged in 93.0% of instances with a median of 28 iterations, a significant improvement over its predecessor MOPCGM (160 iterations).
Compressed Sensing: In $\ell_1$ -regularized signal recovery tasks, both proposed methods converged on all 240 test instances. GCGPM and GMOPCGM required significantly fewer iterations and CPU time compared to MOPCGM, which failed on 20 instances. All methods achieved comparable mean square error (MSE) in signal recovery.
Regularized Logistic Regression: On real-world binary classification datasets, both proposed methods converged on all 60 instances. GMOPCGM reduced the median iteration count from 2,447 (MOPCGM) to 313, demonstrating the benefit of the spectral generalization for nonlinear monotone equations. GCGPM was the most efficient, requiring 184 median iterations.

Significance and Claims
The paper claims that the integration of adaptive spectral parameters into conjugate gradient projection frameworks offers a robust approach for solving large-scale monotone equations. The primary theoretical significance lies in the convergence proof for GMOPCGM, which removes the requirement for Lipschitz continuity—a common bottleneck in the analysis of derivative-free methods for monotone equations. Practically, the results demonstrate that the spectral generalization consistently improves performance over the base methods in terms of convergence speed and computational cost, making the proposed algorithms suitable for high-dimensional applications in signal processing and machine learning. The authors note that future work could extend the convergence analysis of GCGPM to the pseudomonotone setting and explore inertial acceleration techniques.