A Quadratic Programming Algorithm with $O(n^3)$ Time Complexity

This is the code repository for https://arxiv.org/pdf/2507.04515

Our manuscript has four main contributions:

(1) demonstrates how to transform a general strictly convex QP, a Lasso problem, and a support vector machine (or regression) into a Box-QP, highlighting the broad applicability of the approach.

(2) develops a unified and simple proof framework for feasible IPM algorithms with exact Newton step and approximated Newton step, respectively, resulting in $O(n^{3.5})$ and $O(n^3)$ time complexity.

(3) proves that the proposed $O(n^3)$-time-complexity algorithm has an exact and data-independent number of iterations

and the data-independent total number of rank-1 updates bounded by

where $\alpha,\beta,\eta,\delta$ are data-independent constants, thereby being able to offer an execution time certificate for real-time optimization-based applications;

(4) shows that the proposed $O(n^3)$-time-complexity algorithm is simple to implement and matrix-free in the iterative procedures.

Numerical Validations

(1) Validation of number of iterations and rank-1 updates

(2) Numerical comparison of Algorithms 1 ($O(n^{3.5)}$), Algorithm 2 ($O(n^{3)}$, Ipopt, and OSQP)