QPALM swMATH ID: 35397 Software Authors: Ben Hermans, Andreas Themelis, Panagiotis Patrinos Description: QPALM: A Proximal Augmented Lagrangian Method for Nonconvex Quadratic Programs. 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 of a unique solution. The resulting steps are shown to be equivalent to inexact proximal point iterations on the extended-real-valued cost function. Furthermore, we prove global convergence of such iterations to a stationary point at an R-linear rate in the specific case of a (possibly nonconvex) QP. 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, 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. Homepage: https://arxiv.org/abs/2010.02653 Keywords: Optimization; arXiv_math.OC; nonconvex quadratic programming; QP solver; proximal augmented Lagrangian method; C code Related Software: OSQP; qpOASES; NETLIB LP Test Set; Mosek; CHOLMOD; Gurobi; FBstab; GALAHAD; LDL; CSparse; Matlab; ALGENCAN; Ipopt; HPIPM; CUTEst; BPMPD; AMD; OOQP; GitHub; NASOQ Cited in: 7 Publications Standard Articles 1 Publication describing the Software Year QPALM: A Proximal Augmented Lagrangian Method for Nonconvex Quadratic Programs Ben Hermans, Andreas Themelis, Panagiotis Patrinos 2020 all top 5 Cited by 23 Authors 1 Albin, Thivaharan 1 Banjac, Goran 1 De Marchi, Alberto 1 Diehl, Moritz Mathias 1 Frey, Jonathan 1 Frison, Gianluca 1 Hermans, Ben 1 Jian, Jinbao 1 Kolmanovsky, Ilya V. 1 Kouzoupis, Dimitris 1 Liao-McPherson, Dominic 1 Lygeros, John 1 Ma, Guodong 1 Novoselnik, Branimir 1 O’Donoghue, Brendan 1 Patrinos, Panagiotis 1 Qin, Yao 1 Quirynen, Rien 1 Themelis, Andreas 1 van Duijkeren, Niels 1 Verschueren, Robin 1 Yin, Jianghua 1 Zanelli, Andrea all top 5 Cited in 6 Serials 2 Mathematical Programming Computation 1 Automatica 1 Applied Numerical Mathematics 1 SIAM Journal on Optimization 1 Computational Optimization and Applications 1 Optimization Letters all top 5 Cited in 6 Fields 6 Operations research, mathematical programming (90-XX) 2 Numerical analysis (65-XX) 1 (04-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Computer science (68-XX) 1 Systems theory; control (93-XX) Citations by Year