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

Liang Wu, Richard D. Braatz

This paper presents a significant theoretical and practical advancement in numerical optimization, specifically for Quadratic Programming (QP). By bridging the complexity gap between solving linear systems and solving QPs, the authors provide a pathway for "execution time certificates" in high-stakes, real-time engineering applications.

TL;DR

The authors propose a new feasible Interior-Point Method (IPM) for box-constrained Quadratic Programs that achieves a total time complexity of $O(n^3)$. This matches the complexity of standard "direct" methods for linear systems (like Cholesky factorization), finally providing a deterministic time certificate for real-time applications like robotics and Model Predictive Control (MPC).

What Problem Does This Paper Address?

In fields like robotics, aerospace, and autonomous driving, controllers often solve a Quadratic Program (QP) every few milliseconds. For these systems to be safe, engineers need an execution time certificate: a guarantee that the solver will always finish within the allowed sampling time.

Historically, there has been a gap:

  1. Linear Systems: Can be solved using "direct" methods (Cholesky, LU) with a fixed, data-independent cost of $O(n^3)$.
  2. Quadratic Programs: Usually solved via iterative Interior-Point Methods (IPMs). Standard IPMs have a complexity of $O(n^{3.5})$ because they require $O(\sqrt{n})$ iterations, and each iteration involves solving a linear system ($O(n^3)$).

Furthermore, most IPMs require a "strictly feasible" starting point, which is often as hard to find as solving the QP itself. This paper aims to make QP solving as predictable and "direct" as solving a simple system of linear equations.

Methods

The authors achieve the $O(n^3)$ complexity through three key strategic moves:

  1. Universal Box-QP Transformation: They demonstrate that strictly convex QPs, Lasso problems, and Support Vector Machines (SVMs) can all be transformed into Box-Constrained QPs (Box-QPs). The specific structure of a Box-QP allows for a "cost-free" initialization—meaning you can find a strictly feasible starting point instantly.
  2. Approximated Newton Steps: In a standard IPM, you calculate an exact Newton step by inverting a matrix (or performing Cholesky factorization) every single iteration. Instead, the authors use an approximated Newton step.
  3. Rank-1 Update Strategy: Rather than recomputing the matrix inverse from scratch, they use the Sherman-Morrison formula to perform multiple rank-1 updates. They prove that while the algorithm still takes $O(\sqrt{n})$ iterations, the total number of rank-1 updates across all iterations is bounded by $O(n)$. Since each rank-1 update costs $O(n^2)$, the total cumulative cost is $O(n \times n^2) = O(n^3)$.

Datasets

The algorithm was evaluated using:

  • Randomly Generated Box-QPs: Used to validate the theoretical bounds on iteration counts and rank-1 updates for dimensions up to $n=1000$.
  • AFTI-F16 Aircraft Dynamics: A benchmark MPC problem involving initial infeasibility and hard constraints.
  • Three-Tank System: Used to demonstrate a Robust Kalman Filter (RKF) application, which is formulated as an online Lasso problem.

Key Insights and Ideas

  • Similarity is Efficiency: The "aha moment" is the realization that because IPMs converge smoothly, the matrices solved in consecutive iterations are very similar. You don't need a perfect Newton step every time; an approximation is sufficient to maintain the $O(\sqrt{n})$ convergence rate as long as you update the approximation whenever the error exceeds a specific threshold.
  • Data-Independence: By deriving an explicit equation for the maximum number of iterations and updates based only on the problem dimension ($n$) and desired accuracy ($\epsilon$), the solver becomes "direct-like." You can calculate the worst-case runtime before you even start the first iteration.
  • Matrix-Free Iterations: Once the initial matrix is inverted (which can often be done offline in MPC if the Hessian is constant), the iterative process only requires matrix-vector multiplications and rank-1 updates, making it highly suitable for embedded hardware.

Key Results

  • Theoretical Bound: The paper provides the first implementable feasible IPM with a proven $O(n^3)$ time complexity.
  • Speedup: In numerical tests, the $O(n^3)$ algorithm (Algorithm 2) achieved a 3-4x speedup over the $O(n^{3.5})$ version (Algorithm 1) for problems where $n \ge 100$.
  • Real-Time Validation: For the F16 aircraft MPC problem ($n=40$), the algorithm provided a certificate of 1,672 iterations and 11,060 rank-1 updates. On the test platform, this translated to a 0.011s solve time, well within the 0.05s sampling limit.

Limitations and Future Work

  • Strict Convexity: The current framework relies on the Hessian matrix being positive definite (strictly convex). While many problems fit this, extending it to semi-definite or non-convex cases remains a challenge.
  • Initial Inversion: The $O(n^3)$ complexity includes a one-time matrix inversion at the start. In scenarios where the problem data changes completely every step (time-varying Hessians), this initial cost is still $O(n^3)$, though the authors note it can be precomputed in many control applications.
  • The $O(\log n)$ Conjecture: The authors mention the long-standing conjecture that IPMs might actually be $O(\log n)$ iterations in practice. If proven, their rank-1 update approach could potentially push the complexity even lower than $O(n^3)$.

Summary updated

Abstract

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.
BibTeX
@misc{wu2025quadratic,
  author = {Liang Wu and Richard D. Braatz},
  title = {{A Quadratic Programming Algorithm with $O(n^3)$ Time Complexity}},
  year = {2025},
  eprint = {2507.04515},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.04515},
}
Figure