Krylov Subspace Acceleration for First-Order Splitting Methods in Convex Quadratic Programming

We propose an acceleration scheme for first-order methods (FOMs) for convex quadratic programs (QPs) that is analogous to Anderson acceleration and the Generalized Minimal Residual algorithm for linear systems. We motivate our proposed method from the observation that FOMs applied to QPs typically consist of piecewise-affine operators. We describe our Krylov subspace acceleration scheme, contrasting it with existing Anderson acceleration schemes and showing that it largely avoids the latter's well-known ill-conditioning issues in regions of slow convergence. We demonstrate the performance of our scheme relative to Anderson acceleration using standard collections of problems from model predictive control and statistical learning applications. We show that our method is faster than Anderson acceleration across the board in terms of iteration count, and in many cases in computation time, particularly for optimal control and for problems solved to high accuracy.

• Publication year

  2025

• Venue

  Unknown venue

• Publication date

  2025-11-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2511.06323
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Clarabel: An interior-point solver for conic programs with quadratic objectives

  2024influential reference
• Verification of First-Order Methods for Parametric Quadratic Optimization

  2024cited by this paper
• A Practical and Optimal First-Order Method for Large-Scale Convex Quadratic Programming

  2023cited by this paper
• Safeguarded Anderson acceleration for parametric nonexpansive operators

  2022influential reference
• Degenerate Preconditioned Proximal Point Algorithms

  2021influential reference
• Acceleration Methods

  2021cited by this paper
• Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem

  2020cited by this paper
• Safeguarded Learned Convex Optimization

  2020cited by this paper
• COSMO: A Conic Operator Splitting Method for Convex Conic Problems

  2019cited by this paper
• Acceleration of Primal–Dual Methods by Preconditioning and Simple Subproblem Procedures

  2018influential reference
• Lectures on Convex Optimization

  2018cited by this paper
• Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations

  2018cited by this paper
• OSQP: an operator splitting solver for quadratic programs

  2017influential reference
• Multi-Period Trading via Convex Optimization

  2017cited by this paper
• Interior Point Methods

  2017cited by this paper
• An introduction to continuous optimization for imaging

  2016influential reference
• GMRES-Accelerated ADMM for Quadratic Objectives

  2016influential reference
• Towards proper assessment of QP algorithms for embedded model predictive control

  2015cited by this paper
• Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization

  2014cited by this paper
• Proximal Algorithms

  2013cited by this paper
• Local Linear Convergence of the Alternating Direction Method of Multipliers on Quadratic or Linear Programs

  2013cited by this paper
• Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems

  2013cited by this paper
• A Splitting Method for Optimal Control

  2013cited by this paper
• Numerical Linear Algebra

  2011cited by this paper
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers

  2011influential reference
• Convex Analysis and Monotone Operator Theory in Hilbert Spaces

  2011cited by this paper
• The university of Florida sparse matrix collection

  2011cited by this paper
• Anderson Acceleration for Fixed-Point Iterations

  2011influential reference
• Convex optimization

  2010cited by this paper
• Real-Time Convex Optimization in Signal Processing

  2010cited by this paper
• Roofline: an insightful visual performance model for multicore architectures

  2009cited by this paper
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

  2009cited by this paper
• Optimization of sparse matrix-vector multiplication on emerging multicore platforms

  2007cited by this paper
• Direct methods for sparse linear systems

  2006cited by this paper
• Theory of Inexact Krylov Subspace Methods and Applications to Scientific Computing

  2003cited by this paper
• Benchmarking optimization software with performance profiles

  2001cited by this paper
• Numerical Experience with Lower Bounds for MIQP Branch-And-Bound

  1998cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Support-Vector Networks

  1995cited by this paper
• GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems

  1986influential reference
• On robust estimation of the location parameter

  1980cited by this paper
• Monotone Operators and the Proximal Point Algorithm

  1976cited by this paper
• Iterative Procedures for Nonlinear Integral Equations

  1965cited by this paper

• No citing papers are available for this paper.