Solving Quadratic Programs with Slack Variables via ADMM without Increasing the Problem Size
This work addresses a computational bottleneck for researchers and practitioners in optimization, offering an incremental improvement to existing ADMM methods for QPs.
The paper tackles the issue of solving infeasible quadratic programs (QPs) with slack variables using ADMM, which traditionally increases problem size and slows computation, by proposing a modified ADMM scheme that avoids adding slack variables while maintaining equivalence, resulting in demonstrated speedups in numerical experiments.
Proximal methods such as the Alternating Direction Method of Multipliers (ADMM) are effective at solving constrained quadratic programs (QPs). To tackle infeasible QPs, slack variables are often introduced to ensure feasibility, which changes the structure of the problem, increases its size, and slows down numerical resolution. In this letter, we propose a simple ADMM scheme to tackle QPs with slack variables without increasing the size of the original problem. The only modification is a slightly different projection in the z-update, while the rest of the algorithm remains standard. We prove that the method is equivalent to applying ADMM to the QP with additional slack variables, even though slack variables are not added. Numerical experiments show speedups of the approach.