QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
From MaRDI portal
Publication:2088967
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)-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.
Recommendations
- QPPAL: A Two-phase Proximal Augmented Lagrangian Method for High-dimensional Convex Quadratic Programming Problems
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- Towards an efficient augmented Lagrangian method for convex quadratic programming
- An augmented Lagrangian iteration method for convex quadratic SDP
- Proximal quasi-Newton methods for nondifferentiable convex optimization
- Generalized quadratic augmented Lagrangian methods with nonmonotone penalty parameters
- An LPCC approach to nonconvex quadratic programs
- scientific article; zbMATH DE number 3848110
- A novel optimization method for nonconvex quadratically constrained quadratic programs
- An efficient method for non-convex QCQP problems
Cites work
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
- A new algorithm for solving convex parametric quadratic programs based on graphical derivatives of solution mappings
- A note on performance profiles for benchmarking software
- A reformulation-convexification approach for solving nonconvex quadratic programming problems
- A repository of convex quadratic programming problems
- Algorithm 837
- Algorithm 849
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Benchmarking optimization software with performance profiles.
- Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
- Computing the Minimum Fill-In is NP-Complete
- Convexification procedures and decomposition methods for nonconvex optimization problems
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- Direct Methods for Sparse Linear Systems
- Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization
- Global convergence of splitting methods for nonconvex composite optimization
- Globally solving nonconvex quadratic programming problems via completely positive programming
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Implicit Functions and Solution Mappings
- Inexact Variants of the Proximal Point Algorithm without Monotonicity
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Methods for convex and general quadratic programming
- Modifying a Sparse Cholesky Factorization
- Multiple-rank modifications of a sparse Cholesky factorization
- Newton-KKT interior-point methods for indefinite quadratic programming
- Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence
- Nonlinear programming
- Numerical solution of saddle point problems
- Object-oriented software for quadratic programming
- On affine scaling algorithms for nonconvex quadratic programming
- On classes of copositive matrices
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
- OSQP: an operator splitting solver for quadratic programs
- Practical augmented Lagrangian methods for constrained optimization
- Proximal Methods for Cohypomonotone Operators
- qpOASES: a parametric active-set algorithm for~quadratic programming
- Row Modifications of a Sparse Cholesky Factorization
- Symmetric Quasidefinite Matrices
- The BPMPD interior point solver for convex quadratic problems
- The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates
- Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method
- Variational Analysis
Cited in
(10)- LADEL
- Theoretical characteristics and numerical methods for a class of special piecewise quadratic optimization
- FBstab: a proximally stabilized semismooth algorithm for convex quadratic programming
- PAL-Hom method for QP and an application to LP
- Global convergence analysis of the power proximal point and augmented Lagrangian method
- A practical and optimal first-order method for large-scale convex quadratic programming
- A penalty barrier framework for nonconvex constrained optimization
- An efficient active-set method with applications to sparse approximations and risk minimization
- An exact penalty function optimization method and its application in stress constrained topology optimization and scenario based reliability design problems
- The augmented Lagrangian methods: overview and recent advances
Describes a project that uses
Uses Software
This page was built for publication: QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2088967)
