Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel primal-dual interior-point method for quadratic programming that implicitly enforces complementarity through a retraction map relating dual variables and slacks to an auxiliary variable. By using the softplus function as the retraction map, the resulting KKT system is guaranteed to be spectrally bounded, mitigating ill-conditioning issues common in traditional primal-dual methods. This spectral boundedness enables the use of factorization-free solvers and low-precision arithmetic, leading to improved scalability and precision for large-scale quadratic programs.
Quadratic programs can now be solved at scale and high precision thanks to a novel interior-point method that avoids ill-conditioning by implicitly enforcing complementarity.
This paper introduces a new method for solving quadratic programs using primal-dual interior-point methods. Instead of handling complementarity as an explicit equation in the Karush-Kuhn-Tucker (KKT) conditions, we ensure that complementarity is implicitly satisfied by construction. This is achieved by introducing an auxiliary variable and relating it to the duals and slacks via a retraction map. Specifically, we prove that the softplus function has favorable numerical properties compared to the commonly used exponential map. The resulting KKT system is guaranteed to be spectrally bounded, thereby eliminating the most pressing limitation of primal-dual methods: ill-conditioning near the solution. These attributes facilitate the solution of the underlying linear system, either by removing the need to compute factorizations at every iteration, enabling factorization-free approaches like indirect solvers, or allowing the solver to achieve high accuracy in low-precision arithmetic. Consequently, this novel perspective opens new opportunities for interior-point methods, especially for solving large-scale problems to high precision.