ODYN: An All-Shifted Non-Interior-Point Method for Quadratic Programming in Robotics and AI
This work addresses efficient and robust QP solving for robotics and AI applications, such as model-based control and deep learning, though it appears incremental as it builds on existing methods like proximal method of multipliers.
The authors tackled the problem of solving challenging dense and sparse quadratic programming (QP) problems in robotics and AI by introducing ODYN, a novel all-shifted primal-dual non-interior-point solver, which demonstrated state-of-the-art convergence performance on the Maros-Mészáros test set and superior warm-starting capabilities critical for sequential and real-time applications.
We introduce ODYN, a novel all-shifted primal-dual non-interior-point quadratic programming (QP) solver designed to efficiently handle challenging dense and sparse QPs. ODYN combines all-shifted nonlinear complementarity problem (NCP) functions with proximal method of multipliers to robustly address ill-conditioned and degenerate problems, without requiring linear independence of the constraints. It exhibits strong warm-start performance and is well suited to both general-purpose optimization, and robotics and AI applications, including model-based control, estimation, and kernel-based learning methods. We provide an open-source implementation and benchmark ODYN on the Maros-Mészáros test set, demonstrating state-of-the-art convergence performance in small-to-high-scale problems. The results highlight ODYN's superior warm-starting capabilities, which are critical in sequential and real-time settings common in robotics and AI. These advantages are further demonstrated by deploying ODYN as the backend of an SQP-based predictive control framework (OdynSQP), as the implicitly differentiable optimization layer for deep learning (ODYNLayer), and the optimizer of a contact-dynamics simulation (ODYNSim).