Advanced Hybrid Conjugate Gradient Algorithms with Proven Convergence and Superior Efficiency

2.1 Classical conjugate gradient methods

Conjugate gradient methods were initially devised to efficiently address linear systems without the explicit formation of matrices [1]. Fletcher and Reeves [2] expanded their work to nonlinear optimization, leading to the development of methods such as Polak-Ribière-Polyak (PRP), along with variations PRP+, PRP-PR, and PRP-T, which are more responsive to the curvature of nonlinear objectives. Kou [4] advanced the discipline by providing an enhanced CG approach with optimal characteristics for general unconstrained optimization, emphasizing the potential of customizing conjugate gradient updates to the geometry of the problem. Compared to these classical schemes, our algorithms retain the CG framework but target non-convex robustness explicitly via adaptive β updates while keeping per-iteration cost comparable to standard CG.

2.2 Sufficient descent and convergence

Adequate descent conditions guarantee that the search direction results in significant objective reduction at each iteration. Gilbert and Nocedal [5], together with Dai and Yuan [6], formulated formal criteria that guarantee convergence for a wide range of nonlinear functions. The aforementioned conditions depend on characteristics such as bounded level sets and the Lipschitz continuity of the gradient. Our methods are designed to satisfy sufficient descent and global convergence under standard line-search assumptions, aligning with these criteria while enabling more aggressive search directions in non-convex regions.

2.3 DEI-related methods and extensions

Recent methodologies have enhanced β update rules by integrating restart conditions and regularization terms [7, 8]. The DEI algorithm developed by Akdag et al. [3] denotes a significant advancement, demonstrating sufficient descent and global convergence through the strategic implementation of the β_DEI parameter. Nonetheless, the conservative updates of DEI frequently lead to elevated NOI and NOF, causing the formulation of more aggressive yet stable hybrid strategies. Building directly on DEI, our approach adapts β using local curvature cues while preserving DEI’s descent and convergence guarantees, thereby reducing function/gradient calls in practice.

Recent research has advanced Dai–Yuan-type and spectral conjugate gradient methods with sufficient descent properties, directly addressing the challenges of non-convex optimization [9-11]. They also presented altered conjugate gradient approaches founded on the modified secant condition, enhancing convergence on challenging non-convex terrains [12], alongside rapid spectral conjugate gradient methods exhibiting efficacy in nonlinear optimization issues [13]. The experiments demonstrate that adaptive β formulas significantly improve convergence by better aligning search directions with the local geometry of intricate objective landscapes. To illustrate how precisely calibrated β updates may significantly increase convergence performance on intricate landscapes, Hu et al. [14] suggested enhanced CG methods that aim squarely at non-convex unconstrained optimization. Narushima et al. [15] proposed a three-term conjugate gradient method with a new sufficient descent condition, which established the foundational concepts for adaptive β strategies that continue influencing modern algorithm design. Relative to these DEI-adjacent and sufficient-descent lines, NEW1–NEW3 focus on a simple adaptive β mechanism that keeps the two-term CG structure (and complexity) while empirically lowering NOI/NOF on standard benchmarks.

2.4 Hybrid and metaheuristic advancements

Conjugate gradient algorithms have experienced considerable advancement since their introduction, leading to a diverse range of β update rules and restart strategies. The PRP method and its variants, such as PRP+, PRP-PR, and PRP-T, have been thoroughly investigated for their effective application to non-convex problems, although they typically necessitate meticulous tuning of the line search [5, 16]. Fletcher-Reeves (FR) remains a widely used method because of its simplicity and theoretical properties on convex functions, yet it can suffer on non-convex landscapes [2]. Several authors enhance pure CG by integrating it with quasi-Newton updates, adaptive restarts, or regularization to bolster robustness [8, 17]. Furthermore, some introduce inertial or extrapolation mechanisms to expedite convergence in applications like sparse recovery [18]. Cui [19] developed a modified PRP conjugate gradient method for unconstrained optimization and nonlinear equations, demonstrating that the incorporation of restart mechanisms into PRP formulas can enhance global convergence in large-scale problems. Further domain-specific CG variants encompass regression-oriented designs [20], Dai–Liao-type approaches customized for imaging and unconstrained tasks [21], and structured secant conditions for nonlinear least squares that enhance stability in large-scale contexts [22]. Hybrid strategies that integrate CG approaches with metaheuristic algorithms, including cuckoo and gray wolf optimizers, have been investigated to tackle the issues associated with local minima. These combinations improve performance in unconstrained nonlinear optimization problems [23, 24]. In contrast, NEW1–NEW3 remain purely CG—eschewing quasi-Newton/metaheuristic components—so that theoretical guarantees (sufficient descent, global convergence) are retained while achieving lower iteration and evaluation counts relative to DEI in our tests.

4.1 Algorithm (NEW1)

NEW1 clamps the update between stability and responsiveness by taking $\beta_k{ }^{N E W 1}= \max \left\{0, \min \left(\beta_k{ }^{D E I}, \beta_k{ }^{F R}\right)\right\}$ (with $\beta_k{ }^{D E I}$ from Akdag et al. [3] and $\beta_k{ }^{F R}$ from Fletcher-Reeves [2]). The DEI cap preserves sufficient descent under Wolfe/Armijo, while the FR cap limits aggressive growth; the outer max prevents direction reversal.

4.1.1 Algorithm 1: NEW1 (pseudocode)

Input: $x_0 \in \mathbb{R}^{\mathrm{n}}, \varepsilon \in(0,1)$, line-search parameters, $\mu \geq 0$ (strong Wolfe/Armijo [25, 26]).

Initialize: $g_0=\nabla f\left(x_0\right), d_0=-g_0, k \leftarrow 0$

Repeat:

• If $\left\|g_k\right\| \leq \varepsilon$ then stop
• Choose $\alpha_k$ by strong Wolfe/Armijo
• Set $\beta_k{ }^{N E W 1}$ as below $d_K=-g_K+\beta_k{ }^{N E W 1} \quad d_{k-1}$
• $x_{k+1}=x_k+\alpha_k d_k ; k \leftarrow k+1$

$\beta_k{ }^{N E W 1}=\max \left\{0, \min \left(\beta_k{ }^{D E I}, \beta_k{ }^{F R}\right)\right\}$                     (8)

$\beta_k{ }^{F R}=\frac{g_k{ }^T g_k}{g_{k-1}^T g_{k-1}}$                    (9)

$\beta_k^{D E I}=\frac{\left\|g_k\right\|^2-\frac{\left\|g_k\right\|}{\left\|d_{k-1}\right\|}\left|g_k{ }^T d_{k-1}\right|}{\left\|g_k\right\|^2+\mu\left\|g_k\right\|\left\|d_{k-1}\right\|}$                       (10)

$d_{k+1}=-\left(1+\beta_k^{N E W 1} \frac{g_k^T+1 d_k}{\left\|g_{k+1}\right\|^2}\right) g_{k+1}+\beta_k^{N E W 1} d_k$                      (11)

4.2 Algorithm (NEW2)

NEW2 blends three classical updates through a convex combination, interpolating between stability (FR [2]), curvature sensitivity (PR [16]), and added aggressiveness (BA [28]) for ill-conditioned/flat regions. The weights $\delta_k, \gamma_k \in[0,1]$ allow data-driven tuning (e.g., by alignment $\rho_k=\frac{\left|g_k{ }^T d_{k-1}\right|}{\left\|g_k\right\|\left\|d_{k-1}\right\|}$ ) while keeping the two-term CG structure.

4.2.1 Algorithm 2: NEW2 (pseudocode)

Same initialization/lines 1–2 as NEW1; then

1) Compute $\beta_k{ }^{\text {NEW } 2}$ below; set $d_K=-g_K+ \beta_k{ }^{\text {NEW } 2} \quad d_{k-1}$

2) $x_{k+1}=x_k+\alpha_k d_k ; k \leftarrow k+1$

$\begin{gathered}\beta_k^{N E W 2}=\delta_k \beta_k^{F R}+\gamma_k \beta_k^{P R}+\left(1-\delta_k-\gamma_k\right) \beta_k{ }^{B A}\left(\text { with } \delta_k \gamma_k \in[0,1]\right)\end{gathered}$                    (12)

$\beta_k^{B A}=-\frac{y_k^T y_k}{d_k^T g_{k-1}}, y_k=g_k-g_{k-1}$                  (13)

$\beta_k^{P R}=\frac{g_k^T y_k}{g_k^T-1 g_{k-1}}$                      (14)

4.3 Algorithm (NEW3)

When the PR component is unhelpful (e.g., weak y_k signal), NEW3 emphasizes an FR–BA interpolation [2, 28] for robustness on erratic curvature while retaining the same line-search safeguards.

4.3.1 Algorithm 3: NEW3 (pseudocode)

Same initialization/lines 1–2 as NEW1; then

1) If $y_{\mathrm{k}}=0$ and $0<\delta_{\mathrm{k}}<1$, set $\beta_{\mathrm{k}}{ }^{N E W 3}$ below; else use the corresponding NEW2 case

2) $d_K=-g_K+\beta_{\mathrm{k}}{ }^{N E W 3}\, d_{\mathrm{k}-1}, x_{\mathrm{k}+1}=x_{\mathrm{k}}+ \alpha_{\mathrm{k}} d_{\mathrm{k}}; k \leftarrow k+1$

$\begin{gathered}\beta_k^{N E W 3}=\delta_k \beta_k^{F R}+\left(1-\delta_k\right) \beta_k^{B A} \\ \left(\gamma_k=0,0<\delta_k<1\right)\left(\text { with } \delta_k \in[0,1]\right)\end{gathered}$                      (15)

4.4 Convergence of the proposed algorithms

We recall that all proofs assume strong Wolfe/Armijo at every iteration (Section 3), which yields the descent inequality and curvature control used in Lemmas 1–3. Constants are denoted $c 1,\, c 2,\, c 3\, \in(0,1)$.

4.5 Complexity analysis

Each iteration of the NEW algorithms requires computing the gradient $g_k$, a vector addition, and a few inner products to update $\beta_k$ and $g_k{ }^T d_k$. Thus, their per-iteration computational complexity remains $O(n)$, where $n$ is the problem dimension. The $\beta_k$ calculations in NEW1-NEW3 incur a minor constant overhead compared to DEI; this is negligible relative to gradient and line-search costs. Empirically, we observe reductions of up to $60 \%$ in total function evaluations (Periteration cost $O(n)$; linear memory; no Hessian storage/inversion).

5a.png

Note: Lower bars indicate faster convergence. NEW3 achieves the lowest median NOI for ill-conditioned and separable/mild sets, while NEW1–NEW2 are competitive on multi-modal functions

(a)

5b.png

Note: Lower bars indicate greater computational efficiency. NEW3 yields the lowest median NOF on ill-conditioned problems; NEW2 leads on multi-modal functions, and NEW1 performs best on separable/mild problems

(b)

Figure 5. (a). Category-wise median NOI over 32 benchmark functions grouped as ill-conditioned, multi-modal, and separable/mild; (b). Category-wise median NOF evaluations over the same groups

6a.png

Note: For each algorithm, the curve shows the fraction of problems solved within a factor  of the best number of iterations on each problem; curves that are higher and further to the left indicate better performance.

(a)

6b.png

Note: The fraction of problems solved within  times the best number of function evaluations is plotted for each algorithm; higher/leftward curves denote better performance.

(b)

Figure 6. (a). Dolan–Moré performance profile [29] for NOI over 32 benchmark functions; (b). Dolan–Moré performance profile [29] for NOF over 32 benchmark functions

Our findings are consistent with recent discoveries that complexity guarantees and structured secant enhancements in CG methods can further enhance convergence on challenging non-convex objectives [31]. We emphasize that our analysis adopts the same Dolan–Moré profiling framework commonly used in the literature (e.g., [12, 13, 31]), enabling like-for-like, quantitative comparisons: our reported $\tau$–profiles (Figure 6) provide the exact fractions at $\tau \in\{1.25,1.5,2.0\}$, facilitating direct benchmarking against published curves in those works. This suggests that hybrid strategies, such as those found in our NEW algorithms, are a critical area for future research.

Our algorithms demonstrate substantial enhancements in efficiency when contrasted with the DEI proposed by Akdag et al. [3]. The adaptive β and restarts reduce wasted steps caused by curvature-induced zig-zagging on functions with narrow curved valleys or tridiagonal structure (e.g., F7, F18), resulting in the largest gains. This demonstrates that our hybrid strategies effectively adjust to rapidly changing gradient information, circumventing the inefficiencies noted in DEI when employing a fixed β formula. Given the linear-memory footprint and O(n) per-iteration cost, the observed reductions in NOI/NOF indicate strong potential for deployment in large-scale settings where function/gradient evaluations dominate runtime.

6.1 Applications

The NEW algorithms exhibit potential that extends beyond synthetic benchmarks. Engineering design optimization frequently involves challenges such as aerodynamic shape design, structural topology, and electromagnetic devices, which typically result in large-scale, non-convex objectives that are effectively addressed by conjugate gradient methods. In machine learning, novel algorithms may function as effective optimizers for deep neural networks, especially when second-order methods are not feasible. They can also enhance scientific computing tasks, such as inverse problems in medical imaging, where computing gradients is costly and obtaining Hessians is impractical. As illustrated by the MRI parameter-estimation example (Section 4.5), NEW3’s restart and adaptive β can reduce evaluations substantially while retaining theoretical guarantees, a combination attractive for high-throughput pipelines.

6.2 Limitations and future work

Although the NEW algorithms demonstrate substantial efficiency improvements on a wide range of standard benchmarks, they are not without limitations. In highly flat regions or near saddle points, adaptive β strategies may not enhance convergence beyond that achieved by standard steepest descent methods. The algorithms presuppose smooth objectives characterized by Lipschitz-continuous gradients; further investigation is necessary for extensions to non-smooth or discontinuous problems. Future work will include non-monotone line search integration (to trade strict monotonicity for faster progress on rough landscapes), projection-based constrained variants, stochastic/mini-batch adaptations for large-scale learning, and parallel implementations with batched line searches to exploit modern GPUs/TPUs.

6.3 Comparison with prior work (quantitative positioning)

To position our results against the broader CG literature, we report profile-based statistics commonly used in references [12, 13, 31]. At $\tau=1.5$, NEW3’s fractions are 0.875 (NOI) and 0.938 (NOF), compared to DEI’s 0.531 and 0.063, respectively (Figure 6). These $\tau$-anchored numbers—together with the category-wise medians in Figure 5 and the function-level scatter in Figure 7—provide a quantitative basis for comparing to spectral/Dai–Yuan/three-term variants evaluated with the same profiling methodology in those works.

7.png

Figure 7. Per-function NOF evaluations for NEW3 versus DEI across 32 benchmarks