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:
- Linear Systems: Can be solved using "direct" methods (Cholesky, LU) with a fixed, data-independent cost of $O(n^3)$.
- 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:
- 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.
- 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.
- 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