OSQP: An Operator Splitting Solver for Quadratic Programs

Optimization techniques have evolved from early linear programming methods to sophisticated convex quadratic programming algorithms. Interior-point methods, introduced in the 1980s, provided polynomial-time solutions but faced scalability issues. Active-set algorithms, while intuitive, suffered from exponential worst-case complexity. Recent advances focus on first-order methods like ADMM, which are computationally cheap and suitable for large-scale problems but lack robustness in infeasibility detection and high-precision solutions. Despite progress, a gap remains in developing a solver that combines speed, robustness, and accuracy, especially for embedded and real-time applications.

Existing quadratic programming solvers often face trade-offs between speed and reliability. Interior-point methods, though accurate, are computationally intensive for large problems. Active-set methods are faster but less robust and harder to warm start. ADMM-based approaches are promising but struggle with infeasibility detection and high-precision solutions. These limitations hinder their deployment in real-time systems requiring both speed and certainty. The core challenge is to design an algorithm that maintains robustness, detects infeasibility, and achieves high accuracy efficiently, even in noisy or large-scale environments.

OSQP introduces a new operator splitting framework that employs a fixed-coefficient linear system, enabling a single factorization throughout iterations. This approach leverages the quasi-definite structure of the KKT matrix, ensuring stability and efficiency. The solver supports factorization caching and warm starts, reducing repeated computational costs. It also incorporates a solution polishing step based on active set identification, ensuring high-precision solutions. Crucially, it can reliably detect primal and dual infeasibility directly from the iterates, a feature absent in prior operator splitting methods. These innovations collectively enable OSQP to deliver fast, reliable, and accurate solutions for convex quadratic programs.

• �� Formulate the quadratic program with an auxiliary variable to convert inequality constraints into equalities plus set constraints.
• �� Use ADMM to split the problem into subproblems involving a quadratic minimization and a projection step.
• �� Derive a linear system (the KKT system) with a quasi-definite structure, which remains constant when penalty parameters are fixed.
• �� Perform a one-time LDLT factorization of the KKT matrix, caching the factors for subsequent iterations.
• �� In each iteration, solve the linear system efficiently using the cached factors, update primal and dual variables, and perform projection onto the feasible set.
• �� Incorporate solution polishing by identifying active constraints from the dual variables, then solve a reduced linear system for high-precision solutions.
• �� Implement infeasibility detection by monitoring residuals and iterates, providing certificates when the problem is infeasible.

The authors benchmarked OSQP on a library of 1400 problems spanning finance, control, and machine learning, comparing against interior-point solvers (e.g., MOSEK, Gurobi) and open-source alternatives (e.g., qpOASES). Metrics included computational time, solution accuracy, and robustness in noisy environments. Results showed OSQP consistently outperformed competitors, often by an order of magnitude. The impact of factorization caching and warm starts was quantified, demonstrating up to 100x speedups in parametric scenarios. Additional tests confirmed reliable infeasibility detection and high solution precision, validating the method’s practical robustness.

• �� OSQP achieved an average of 10x faster solutions than interior-point methods across diverse problem sets, with some instances reaching 100x speedup using caching and warm starts.
• �� The solver maintained high accuracy, with residuals below 1e-6, surpassing traditional first-order methods.
• �� Reliable infeasibility detection was demonstrated, with over 95% accuracy, providing valuable certificates for infeasible problems.
• �� The approach scaled well to large problems, with minimal degradation in performance, confirming its suitability for real-time applications.

OSQP is ideal for embedded control systems, such as model predictive control (MPC) in autonomous vehicles, where rapid decision-making is critical. It also benefits financial portfolio optimization, enabling real-time asset allocation adjustments. In machine learning, it accelerates large-scale support vector machine training and regularized regression problems. Its ability to handle noisy data and detect infeasibility makes it suitable for industrial automation, robotics, and adaptive systems, where robustness and speed are paramount.

While highly effective for convex QPs, OSQP’s performance diminishes on non-convex or highly nonlinear problems due to its design assumptions. The fixed linear system approach depends on static problem data; dynamic changes require re-factorization, reducing efficiency. In extremely noisy or unreliable data scenarios, the infeasibility detection may produce false positives or negatives, necessitating additional validation. Future work aims to address these issues by extending capabilities to non-convex problems and improving adaptive strategies.