QPALM: a proximal augmented lagrangian method for nonconvex quadratic programs

Ben Hermans, Andreas Themelis, Panagiotis Patrinos

TL;DR

This paper introduces QPALM, a new algorithm for solving nonconvex quadratic programming (QP) problems. QPALM leverages a proximal augmented Lagrangian approach to efficiently find stationary points, even for challenging problems where other methods struggle. It demonstrates strong performance across various benchmarks, outperforming existing solvers in robustness and competitiveness.

What Problem Does This Paper Address?

Quadratic programming (QP) problems, where we minimize a quadratic objective function subject to linear constraints, are fundamental in many fields like machine learning, finance, and control systems. While solving convex QPs (where the quadratic term is positive semidefinite) is well-understood, nonconvex QPs pose a significant challenge. Nonconvexity means the objective function can have multiple local minima, making it difficult to guarantee finding the global optimum or even a reliable stationary point. Existing methods for convex QPs often fail or exhibit poor performance on nonconvex instances. This paper aims to bridge this gap by developing a robust and efficient solver for nonconvex QPs that can reliably find stationary points.

Methods

The core of QPALM is the proximal augmented Lagrangian method (P-ALM). This approach tackles the nonconvexity by transforming the original QP into a sequence of strongly convex subproblems. This is achieved by adding a "proximal" term to the objective function, which ensures that each subproblem has a unique, well-defined solution.

Key algorithmic components include:

  • Inexact Proximal Point Iterations: The P-ALM steps are shown to be equivalent to inexact proximal point iterations on the objective function. This theoretical link allows for a simpler convergence analysis, proving R-linear convergence to a stationary point.
  • Semismooth Newton Method: The strongly convex subproblems are solved using a semismooth Newton method. This method is efficient because it can leverage factorization update routines, avoiding costly refactorizations in most iterations.
  • Exact Linesearch: An exact linesearch is employed to determine the optimal step size, which involves finding the root of a simple, one-dimensional piecewise affine function.
  • Dedicated Linear Algebra Package (LADEL): QPALM utilizes a custom C package called LADEL for its linear algebra operations, including LDL factorization and updates, which are crucial for computational efficiency.

Datasets

The paper evaluates QPALM on several benchmark datasets:

  • Maros-Meszaros problems: A collection of convex QPs, used to test QPALM's performance on well-conditioned and ill-conditioned problems.
  • Cutest test set: A collection of nonconvex QPs, used to assess QPALM's robustness and ability to find stationary points for challenging problems.
  • Portfolio optimization problems: QPs arising from financial applications.
  • Model Predictive Control (MPC) problems: QPs derived from optimal control strategies.

Key Insights and Ideas

  • Proximal term as a "nonconvexity tamer": The addition of a proximal term to the augmented Lagrangian is the key innovation that transforms difficult nonconvex subproblems into manageable, strongly convex ones. This is a crucial insight for extending augmented Lagrangian methods to nonconvex settings.
  • Equivalence to inexact proximal point iterations: This theoretical connection simplifies the convergence analysis and provides a strong foundation for QPALM's global convergence guarantees.
  • Robustness through careful parameter tuning: The paper emphasizes the importance of parameter selection and update rules (especially for penalty parameters) in achieving QPALM's practical performance and robustness.
  • Efficiency via factorization updates: By using semismooth Newton with factorization updates, QPALM avoids repeated expensive factorizations, making it competitive even with first-order methods on certain problems.

Key Results

  • Robustness: QPALM successfully solves all Maros-Meszaros convex QP problems and finds stationary points for a high percentage (94.39%) of nonconvex QPs in the Cutest test set.
  • Competitiveness: QPALM demonstrates competitive performance against state-of-the-art convex QP solvers (Gurobi, OSQP, qpOASES) on various problem classes, including portfolio optimization and MPC.
  • Nonconvex QP performance: For nonconvex QPs, QPALM is shown to be more robust than IPOPT (a nonlinear optimization solver used for comparison), with a lower failure rate and comparable performance in finding solutions with similar objective values.
  • Warm-starting: QPALM benefits significantly from warm-starting, making it particularly suitable for applications like MPC where successive problems are similar.
  • Theoretical Guarantees: The algorithm is proven to converge globally at an R-linear rate to a stationary point for nonconvex QPs.

Limitations and Future Work

  • "Dead points": Like IPOPT, QPALM can find "dead points" – stationary points that do not satisfy second-order necessary conditions for optimality. The paper notes that both solvers find these on different problems, suggesting that obtaining a better stationary point might require more advanced techniques.
  • Warm-starting for interior-point methods: The paper notes that interior-point methods, in general, do not benefit from warm-starting as much as QPALM, making them less suitable for applications like MPC. Future work could explore how to improve warm-starting capabilities for interior-point methods.
  • Parameter tuning: While QPALM's parameters are carefully tuned, the paper suggests that further investigation into automatic parameter selection and warm-starting strategies could be beneficial.
  • Global optimization: This paper focuses on finding stationary points, not necessarily global optima. For problems where global optimality is critical, different approaches would be needed.

Summary updated

Abstract

We propose QPALM, a nonconvex quadratic programming (QP) solver based on the proximal augmented Lagrangian method. This method solves a sequence of inner subproblems which can be enforced to be strongly convex and which therefore admit a unique solution. The resulting steps are shown to be equivalent to inexact proximal point iterations on the extended-real-valued cost function, which allows for a fairly simple analysis where convergence to a stationary point at an $$R$$ R -linear rate is shown. The QPALM algorithm solves the subproblems iteratively using semismooth Newton directions and an exact linesearch. The former can be computed efficiently in most iterations by making use of suitable factorization update routines, while the latter requires the zero of a monotone, one-dimensional, piecewise affine function. QPALM is implemented in open-source C code, with tailored linear algebra routines for the factorization in a self-written package LADEL. The resulting implementation is shown to be extremely robust in numerical simulations, solving all of the Maros-Meszaros problems and finding a stationary point for most of the nonconvex QPs in the Cutest test set. Furthermore, it is shown to be competitive against state-of-the-art convex QP solvers in typical QPs arising from application domains such as portfolio optimization and model predictive control. As such, QPALM strikes a unique balance between solving both easy and hard problems efficiently.
BibTeX
@article{hermans2022qpalm,
  author = {Ben Hermans and Andreas Themelis and Panagiotis Patrinos},
  title = {{QPALM: a proximal augmented lagrangian method for nonconvex quadratic programs}},
  journal = {Math. Program. Comput.},
  year = {2022},
  doi = {10.1007/s12532-022-00218-0},
}

Loading related content...

Figure