Abstract
Minimizing both the worst-case and average execution times of optimization algorithms is equally critical in real-time optimization-based control applications such as model predictive control (MPC). Most MPC solvers have to trade off between certified worst-case and practical average execution times. For example, our previous work [1] proposed a full-Newton path-following interior-point method (IPM) with data-independent, simple-calculated, and exact $O(\sqrt{n})$ iteration complexity, but not as efficient as the heuristic Mehrotra predictor-corrector IPM algorithm (which sacrifices global convergence). This letter proposes a new predictor-corrector IPM algorithm that preserves the same certified $O(\sqrt{n})$ iteration complexity while achieving a $5\times$ speedup over [1]. Numerical experiments and codes that validate these results are provided.
Introduction
In Model Predictive Control (MPC), the optimization solver acts as the "brain" for autonomous systems. For these systems, speed is a safety-critical requirement. However, high average speed is insufficient; solvers must also provide a "certificate"—a mathematical guarantee on the maximum number of iterations—to ensure deadlines are never missed.
Currently, practitioners face a dilemma: use heuristic solvers like Mehrotra’s predictor-corrector, which are fast but lack worst-case guarantees, or use certified algorithms that are often too slow for high-speed applications. This paper introduces a new predictor-corrector interior-point method (IPM) for box-constrained quadratic programs (Box-QP) that bridges this gap, offering both a theoretical $O(\sqrt{n})$ iteration complexity and high practical efficiency.
Methodology
The proposed Feasible Adaptive-Step Predictor-Corrector IPM incorporates several technical innovations to achieve its performance:
- Predictor-Corrector Framework: The algorithm utilizes a predictor step to move aggressively toward the boundary of the feasible region, followed by a corrector step to maintain proximity to the "central path," ensuring both speed and numerical stability.
- Cost-Free Initialization: Finding a feasible starting point is often computationally expensive. By exploiting the structure of Box-QP (where variables are bounded between -1 and 1), the authors derived a closed-form formula for an initial point that requires zero additional computation.
- Adaptive Step-Sizes: While the algorithm dynamically adjusts step sizes for practical speed, the authors proved a lower bound on these steps. This ensures that the algorithm never exceeds the theoretical $O(\sqrt{n})$ iteration complexity.
- Efficient Linear Algebra: The KKT conditions are reduced to a symmetric $n \times n$ system, significantly lowering the per-iteration computational overhead.
Experimental Results
The algorithm was validated on two benchmarks: a suite of random Box-QPs with dimensions $n \in [100, 1000]$ and a high-dimensional nonlinear PDE-MPC case study involving the Korteweg-de Vries (KdV) equation.
Theoretical vs. Practical Performance
A key insight from the numerical experiments is the conservative nature of theoretical bounds. While the algorithm is proven to have $O(\sqrt{n})$ complexity, practical observations suggest a growth rate closer to $O(\log n)$ or $O(n^{0.25})$.
Efficiency in Real-Time Control
In the PDE-MPC scenario, the proposed algorithm demonstrated a significant performance leap over the previous state-of-the-art certified method [1]. It achieved a roughly 5x speedup in execution time and reduced the average number of iterations from 202 to approximately 29.
Conclusion
This work demonstrates that worst-case time certificates do not necessitate a sacrifice in practical performance. The proposed predictor-corrector IPM provides the predictability required for safety-critical MPC while maintaining the speed of heuristic methods. Future work will focus on further optimizing the linear algebra by reusing factorizations across the predictor and corrector steps, potentially closing the remaining gap with uncertified heuristic solvers.
Summary updated