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

摘要

Solving linear systems and quadratic programming (QP) problems are both ubiquitous tasks in the engineering and computing fields. Direct methods for solving systems, such as Cholesky, LU, and QR factorizations, exhibit data-independent time complexity of $O(n^3)$. This raises a natural question: could there exist algorithms for solving QPs that also achieve \textit{data-independent} time complexity of $O(n^3)$? This raises a natural question: could there exist algorithms for solving QPs that also achieve data-independent time complexity of $O(n^3)$? This is critical for offering an execution time certificate for real-time optimization-based applications such as model predictive control. This article first demonstrates that solving real-time strictly convex QPs, Lasso problems, and support vector machine problems can be turned into solving box-constrained QPs (Box-QPs), which support a cost-free initialization strategy for feasible interior-point methods (IPMs). Next, focusing on solving Box-QPs, this article replaces the exact Newton step with an approximated Newton step (substituting the matrix-inversion operation with multiple rank-1 updates) within feasible IPMs. For the first time, this article proposes an implementable feasible IPM algorithm with $O(n^3)$ time complexity, by proving the number of iterations is exact $O(\sqrt{n})$ and the number of rank-1 updates is bounded by $O(n)$. Numerical validations/applications and codes are provided.