OSQP: an operator splitting solver for quadratic programs
From MaRDI portal
Publication:78613
DOI10.48550/ARXIV.1711.08013zbMATH Open1452.90236arXiv1711.08013OpenAlexW2769646558WikidataQ120716989 ScholiaQ120716989MaRDI QIDQ78613FDOQ78613
Authors: Bartolomeo Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad, Stephen Boyd, Bartolomeo Stellato, Goran Banjac, Paul J. Goulart, A. Bemporad, Stephen Boyd 
Publication date: 21 November 2017
Published in: Mathematical Programming Computation (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1711.08013
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
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)
Cites Work
- Algorithm 849
- Algorithm 837
- The University of Florida sparse matrix collection
- CVXGEN: a code generator for embedded convex optimization
- Object-oriented software for quadratic programming
- CVXPY: a Python-embedded modeling language for convex optimization
- JuMP: a modeling language for mathematical optimization
- Direct Methods for Sparse Linear Systems
- Parameter selection and preconditioning for a graph form solver
- The Simplex Method for Quadratic Programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Model predictive control: Theory and practice - a survey
- Parallel alternating direction multiplier decomposition of convex programs
- Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities
- Preconditioning techniques for large linear systems: A survey
- Support-vector networks
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Stochastic matrix-free equilibration
- Concerning nonnegative matrices and doubly stochastic matrices
- Mathematical methods of organizing and planning production. English translation by Robert W. Campbell and W. H. Marlow
- A Symmetry Preserving Algorithm for Matrix Scaling
- Predictive control for linear and hybrid systems
- Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems
- Embedded Online Optimization for Model Predictive Control at Megahertz Rates
- Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
- Conic optimization via operator splitting and homogeneous self-dual embedding
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Efficient numerical methods for nonlinear MPC and moving horizon estimation
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- On the Implementation of a Primal-Dual Interior Point Method
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear Matrix Inequalities in System and Control Theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Variational Analysis
- Numerical Experience with Lower Bounds for MIQP Branch-And-Bound
- Operator-Splitting Methods for Monotone Affine Variational Inequalities, with a Parallel Application to Optimal Control
- A repository of convex quadratic programming problems
- Tight Global Linear Convergence Rate Bounds for Operator Splitting Methods
- Title not available (Why is that?)
- On Projection Algorithms for Solving Convex Feasibility Problems
- Symmetric Quasidefinite Matrices
- qpOASES: a parametric active-set algorithm for~quadratic programming
- Title not available (Why is that?)
- A note on performance profiles for benchmarking software
- Mixed-integer nonlinear optimization
- Title not available (Why is that?)
- Robust Estimation of a Location Parameter
- Title not available (Why is that?)
- Title not available (Why is that?)
- Convex analysis and monotone operator theory in Hilbert spaces
- Robust Statistics
- Benchmarking optimization software with performance profiles.
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- A new polynomial-time algorithm for linear programming
- Metric selection in fast dual forward-backward splitting
Cited In (70)
- 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
- Back-and-forth nudging moving horizon estimation for discrete-time linear systems
- Independence Weights for Causal Inference with Continuous Treatments
- Fused Lasso nearly-isotonic signal approximation in general dimensions
- \(\mathcal{N}\)IPM-HLSP: an efficient interior-point method for hierarchical least-squares programs
- Structure-exploiting Newton-type method for optimal control of switched systems
- The exact worst-case convergence rate of the alternating direction method of multipliers
- Remark on Algorithm 1012: computing projections with large datasets
- On piecewise cubic estimates of the value function in a target control problem for a nonlinear system
- Data-driven entropic spatially inhomogeneous evolutionary games
- Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
- Propensity score analysis with local balance
- A new computationally simple approach for implementing neural networks with output hard constraints
- Inexact log-domain interior-point methods for quadratic programming
- Sequential hierarchical least-squares programming for prioritized non-linear optimal control
- Optimal Subsampling via Predictive Inference
- Polyak minorant method for convex optimization
- Dictionary-free Koopman model predictive control with nonlinear input transformation
- Motion planning of multiple unmanned vehicles using sequential convex programming-based distributed model predictive control
- Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization
- \texttt{acados} -- a modular open-source framework for fast embedded optimal control
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- FBstab: a proximally stabilized semismooth algorithm for convex quadratic programming
- Total positivity in multivariate extremes
- 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
- Stabilising quasi-time-optimal nonlinear model predictive control with variable discretisation
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- 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
- Efficient min–max MPC: Achieving a large domain of attraction with short horizon
- 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
- Efficient differentiable quadratic programming layers: an ADMM approach
- Tax-aware portfolio construction via convex optimization
- Online Mixed-Integer Optimization in Milliseconds
- Pooling adjacent violators under interval constraints
- Proportional-integral projected gradient method for conic optimization
- An active-set algorithm for norm constrained quadratic problems
- On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
- A proximal augmented method for semidefinite programming problems
- Solution refinement at regular points of conic problems
- OSQP
- osqp
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Portfolio construction as linearly constrained separable optimization
- Semi-explicit model predictive control of quasi linear parameter varying systems
- qpOASES: a parametric active-set algorithm for~quadratic programming
- An index search method based inner-outer iterative algorithm for solving nonnegative least squares problems
- Continuous-time portfolio optimization for absolute return funds
- Data‐enabled predictive control for quadcopters
- Passive nonlinear dendritic interactions as a computational resource in spiking neural networks
- Laplacian-optimized diffusion for semi-supervised learning
- COSMO: a conic operator splitting method for convex conic problems
- Efficient semidefinite programming with approximate ADMM
- Spatially varying coefficient models with sign preservation of the coefficient functions
- An infeasible-start framework for convex quadratic optimization, with application to constraint-reduced interior-point and other methods
- Optimal representative sample weighting
- QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
- Numerical Approximation of Optimal Convex Shapes
- On a primal-dual Newton proximal method for convex quadratic programs
- A dual Newton strategy for tree-sparse quadratic programs and its implementation in the open-source software treeQP
- A distributed Bregman forward-backward algorithm for a class of Nash equilibrium problems
- Radial duality. II: Applications and algorithms
- IPRQP: a primal-dual interior-point relaxation algorithm for convex quadratic programming
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)
