OSQP: an operator splitting solver for quadratic programs
From MaRDI portal
Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Quadratic programming (90C20) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Optimality conditions and duality in mathematical programming (90C46) Applications of mathematical programming (90C90)
Abstract: We present a general-purpose solver for convex quadratic programs based on the alternating direction method of multipliers, employing a novel operator splitting technique that requires the solution of a quasi-definite linear system with the same coefficient matrix at almost every iteration. Our algorithm is very robust, placing no requirements on the problem data such as positive definiteness of the objective function or linear independence of the constraint functions. It can be configured to be division-free once an initial matrix factorization is carried out, making it suitable for real-time applications in embedded systems. In addition, our technique is the first operator splitting method for quadratic programs able to reliably detect primal and dual infeasible problems from the algorithm iterates. The method also supports factorization caching and warm starting, making it particularly efficient when solving parametrized problems arising in finance, control, and machine learning. Our open-source C implementation OSQP has a small footprint, is library-free, and has been extensively tested on many problem instances from a wide variety of application areas. It is typically ten times faster than competing interior-point methods, and sometimes much more when factorization caching or warm start is used. OSQP has already shown a large impact with tens of thousands of users both in academia and in large corporations.
Recommendations
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- COSMO: a conic operator splitting method for convex conic problems
- qpOASES: a parametric active-set algorithm for~quadratic programming
- On a primal-dual Newton proximal method for convex quadratic programs
- Conic optimization via operator splitting and homogeneous self-dual embedding
Cites work
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1024452 (Why is no real title available?)
- scientific article; zbMATH DE number 1049350 (Why is no real title available?)
- scientific article; zbMATH DE number 194668 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 781821 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- A Symmetry Preserving Algorithm for Matrix Scaling
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A new polynomial-time algorithm for linear programming
- A note on performance profiles for benchmarking software
- A repository of convex quadratic programming problems
- Algorithm 837
- Algorithm 849
- Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities
- Benchmarking optimization software with performance profiles.
- CVXGEN: a code generator for embedded convex optimization
- CVXPY: a Python-embedded modeling language for convex optimization
- Concerning nonnegative matrices and doubly stochastic matrices
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Convex analysis and monotone operator theory in Hilbert spaces
- Direct Methods for Sparse Linear Systems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Efficient numerical methods for nonlinear MPC and moving horizon estimation
- Embedded Online Optimization for Model Predictive Control at Megahertz Rates
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- JuMP: a modeling language for mathematical optimization
- Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
- Linear Matrix Inequalities in System and Control Theory
- Mathematical methods of organizing and planning production. English translation by Robert W. Campbell and W. H. Marlow
- Metric selection in fast dual forward-backward splitting
- Mixed-integer nonlinear optimization
- Model predictive control: Theory and practice - a survey
- Numerical Experience with Lower Bounds for MIQP Branch-And-Bound
- Object-oriented software for quadratic programming
- On Projection Algorithms for Solving Convex Feasibility Problems
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- On the Implementation of a Primal-Dual Interior Point Method
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Operator-Splitting Methods for Monotone Affine Variational Inequalities, with a Parallel Application to Optimal Control
- Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems
- Parallel alternating direction multiplier decomposition of convex programs
- Parameter selection and preconditioning for a graph form solver
- Preconditioning techniques for large linear systems: A survey
- Predictive control for linear and hybrid systems
- Robust Estimation of a Location Parameter
- Robust Statistics
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Stochastic matrix-free equilibration
- Support-vector networks
- Symmetric Quasidefinite Matrices
- The Simplex Method for Quadratic Programming
- The University of Florida sparse matrix collection
- Tight Global Linear Convergence Rate Bounds for Operator Splitting Methods
- Variational Analysis
- qpOASES: a parametric active-set algorithm for~quadratic programming
Cited in
(70)- A distributed Bregman forward-backward algorithm for a class of Nash equilibrium problems
- COSMO: a conic operator splitting method for convex conic problems
- Penalized and constrained LAD estimation in fixed and high dimension
- Linear programming with nonparametric penalty programs and iterated thresholding
- Sparse convex optimization toolkit: a mixed-integer framework
- On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
- Pooling adjacent violators under interval constraints
- Online Mixed-Integer Optimization in Milliseconds
- Multi-period portfolio optimization using model predictive control with mean-variance and risk parity frameworks
- On the asymptotic behavior of the Douglas-Rachford and proximal-point algorithms for convex optimization
- Stabilising quasi-time-optimal nonlinear model predictive control with variable discretisation
- Solution refinement at regular points of conic problems
- Spatially varying coefficient models with sign preservation of the coefficient functions
- Continuous-time portfolio optimization for absolute return funds
- Efficient semidefinite programming with approximate ADMM
- An infeasible-start framework for convex quadratic optimization, with application to constraint-reduced interior-point and other methods
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization
- Passive nonlinear dendritic interactions as a computational resource in spiking neural networks
- Efficient differentiable quadratic programming layers: an ADMM approach
- Tax-aware portfolio construction via convex optimization
- Proportional-integral projected gradient method for conic optimization
- Data‐enabled predictive control for quadcopters
- \texttt{acados} -- a modular open-source framework for fast embedded optimal control
- Optimal representative sample weighting
- Conic optimization via operator splitting and homogeneous self-dual embedding
- OSQP
- Laplacian-optimized diffusion for semi-supervised learning
- osqp
- Semi-explicit model predictive control of quasi linear parameter varying systems
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- Portfolio construction as linearly constrained separable optimization
- Total positivity in multivariate extremes
- QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
- Tutorial on Amortized Optimization
- NMPC in active subspaces: dimensionality reduction with recursive feasibility guarantees
- Theoretical characteristics and numerical methods for a class of special piecewise quadratic optimization
- Numerical Approximation of Optimal Convex Shapes
- An active-set algorithm for norm constrained quadratic problems
- Radial duality. II: Applications and algorithms
- qpOASES: a parametric active-set algorithm for~quadratic programming
- Efficient min–max MPC: Achieving a large domain of attraction with short horizon
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- An index search method based inner-outer iterative algorithm for solving nonnegative least squares problems
- A dual Newton strategy for tree-sparse quadratic programs and its implementation in the open-source software treeQP
- FBstab: a proximally stabilized semismooth algorithm for convex quadratic programming
- IPRQP: a primal-dual interior-point relaxation algorithm for convex quadratic programming
- A proximal augmented method for semidefinite programming problems
- On a primal-dual Newton proximal method for convex quadratic programs
- Propensity score analysis with local balance
- HiQR: an efficient algorithm for high-dimensional quadratic regression with penalties
- Solving variational inequalities and cone complementarity problems in nonsmooth dynamics using the alternating direction method of multipliers
- Robust linear algebra
- Optimal Subsampling via Predictive Inference
- Polyak minorant method for convex optimization
- Remark on Algorithm 1012: computing projections with large datasets
- Sequential hierarchical least-squares programming for prioritized non-linear optimal control
- A new computationally simple approach for implementing neural networks with output hard constraints
- On piecewise cubic estimates of the value function in a target control problem for a nonlinear system
- The exact worst-case convergence rate of the alternating direction method of multipliers
- Fused Lasso nearly-isotonic signal approximation in general dimensions
- \(\mathcal{N}\)IPM-HLSP: an efficient interior-point method for hierarchical least-squares programs
- Dictionary-free Koopman model predictive control with nonlinear input transformation
- Structure-exploiting Newton-type method for optimal control of switched systems
- Inexact log-domain interior-point methods for quadratic programming
- Data-driven entropic spatially inhomogeneous evolutionary games
- Back-and-forth nudging moving horizon estimation for discrete-time linear systems
- Independence Weights for Causal Inference with Continuous Treatments
- Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
- Motion planning of multiple unmanned vehicles using sequential convex programming-based distributed model predictive control
Describes a project that uses
Uses Software
This page was built for publication: OSQP: an operator splitting solver for quadratic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q78613)
