A regularized limited memory subspace minimization conjugate gradient method for unconstrained optimization

Wumei Sun, Hongwei Liu, Zexian Liu

This paper presents a new approach to unconstrained optimization, specifically targeting the "loss of orthogonality" problem that plagues traditional conjugate gradient methods. By blending subspace minimization with regularized quasi-Newton techniques, the authors offer a robust alternative to industry-standard solvers.

TL;DR

The authors propose RL_SMCG, a hybrid optimization method that combines the low memory footprint of Conjugate Gradient (CG) methods with the stability of Regularized Quasi-Newton (RQN) iterations. It dynamically switches between these modes to maintain gradient orthogonality, outperforming state-of-the-art packages like CG_DESCENT on standard benchmark libraries.

What Problem Does This Paper Address?

In large-scale unconstrained optimization, Conjugate Gradient (CG) methods are favored because they don't require storing large Hessian matrices. However, they have a major weakness: loss of orthogonality. In practice, especially on ill-conditioned problems, successive gradients can become nearly parallel, causing the algorithm to stall or converge extremely slowly.

While existing tools like CG_DESCENT attempt to fix this using complex pre-conditioners, they often rely on strict theoretical assumptions that are hard to verify in the real world. The authors aim to create a simpler, more robust algorithm that restores orthogonality without sacrificing the efficiency of limited-memory techniques.

Methods

The core of the paper is the RL_SMCG (Regularized Limited Memory Subspace Minimization Conjugate Gradient) algorithm. It utilizes two distinct types of iterations:

  1. SMCG Iteration: This is the "standard" mode. The algorithm searches for a direction within a 2D subspace spanned by the current gradient and the previous step. If the objective function doesn't behave like a nice quadratic, the algorithm employs a cubic regularization model to find a more stable search direction.
  2. RQN Iteration: This is the "recovery" mode. The algorithm monitors the distance between the current gradient and the subspace of previous directions. If they are too close (indicating a loss of orthogonality), it switches to a modified Regularized L-BFGS method within a small subspace (typically memory size $m \le 11$). This "resets" the geometry of the search.

Additional Innovations: * Acceleration Criteria: A quadratic interpolation-based step is used to speed up convergence when certain conditions are met. * Generalized Nonmonotone Line Search: An extension of the Zhang-Hager line search that allows the objective function value to occasionally increase, helping the algorithm escape local "flat" regions or narrow valleys. * Improved Stepsize Selection: A new tactic for choosing the initial stepsize ($\alpha_k$) to reduce the number of function evaluations.

Datasets

The algorithm was evaluated using the CUTEr library (Constrained and Unconstrained Testing Environment, revisited), a standard benchmark for nonlinear optimization. The researchers tested their method on 145 distinct test problems from this library.

Key Insights and Ideas

  • Orthogonality as a Trigger: Rather than using a complex preconditioner at every step, RL_SMCG uses a distance metric to detect when orthogonality is failing and only then deploys the more computationally expensive RQN iteration.
  • Subspace Regularization: By performing BFGS updates and cubic minimization only within a small subspace, the algorithm gains the curvature-sensing benefits of second-order methods while maintaining the $O(n)$ memory complexity of first-order methods.
  • Stability via Cubic Models: The use of a cubic term in the subproblem (Case (i) of the SMCG iteration) provides a "trust-region-like" safety net when the standard quadratic approximation of the function is unreliable.

Key Results

The authors compared RL_SMCG against ASMCG_PR, CG_DESCENT (6.8), and CGOPT (2.0). Using Dolan-Moré performance profiles, they found:

  • Superior Efficiency: RL_SMCG outperformed CG_DESCENT on approximately 71.5% of the CUTEr test problems in terms of the number of gradient evaluations.
  • Speed: The method showed a significant improvement in CPU time and total iterations compared to ASMCG_PR.
  • Robustness: The hybrid approach proved more reliable at reaching the $10^{-6}$ optimality tolerance across a wider variety of problem types than the pure CG-based solvers.

Limitations and Future Work

  • Hyperparameter Sensitivity: The algorithm introduces several new constants ($\xi_1$ through $\xi_5$, $\sigma$ values, etc.). While the paper provides defaults, the performance on very specific classes of problems might require manual tuning.
  • Memory Limit: The RQN iteration is restricted to a very small subspace ($m \le 11$). While this keeps it fast, it’s unclear if larger subspaces would provide diminishing returns or significantly better stability for extremely high-dimensional problems.
  • Future Directions: The authors suggest that the regularization and subspace minimization techniques could be extended to constrained optimization or adapted for stochastic gradient descent in machine learning contexts.

Summary updated

Abstract

In this paper, based on the limited memory techniques and subspace minimization conjugate gradient (SMCG) methods, a regularized limited memory subspace minimization conjugate gradient method is proposed, which contains two types of iterations. In SMCG iteration, we obtain the search direction by minimizing the approximate quadratic model or approximate regularization model. In RQN iteration, combined with regularization technique and BFGS method, a modified regularized quasi-Newton method is used in the subspace to improve the orthogonality. Moreover, some simple acceleration criteria and an improved tactic for selecting the initial stepsize to enhance the efficiency of the algorithm are designed. Additionally, an generalized nonmonotone line search is utilized and the global convergence of our proposed algorithm is established under mild conditions. Finally, numerical results show that, the proposed algorithm has a significant improvement over ASMCG_PR and is superior to the particularly well-known limited memory conjugate gradient software packages CG_DESCENT (6.8) and CGOPT(2.0) for the CUTEr library.
BibTeX
@article{sun2023regularized,
  author = {Wumei Sun and Hongwei Liu and Zexian Liu},
  title = {{A regularized limited memory subspace minimization conjugate gradient method for unconstrained optimization}},
  journal = {Numer. Algorithms},
  year = {2023},
  doi = {10.1007/s11075-023-01559-0},
}

Loading related content...

Figure