Extrapolated Proportional-Integral Projected Gradient Method for Conic Optimization

Yue Yu, Purnanand Elango, Behçet Açikmese, Ufuk TopcuIEEE Control. Syst. Lett 2023 · DOI

Introduction

Conic optimization—minimizing a quadratic function subject to cone constraints—is a cornerstone of modern robotics and Model Predictive Control (MPC). A persistent challenge in this domain is the efficient detection of primal and dual infeasibility. While traditional interior-point methods are robust in identifying unsolvable problems, their reliance on expensive matrix inversions limits their scalability for large-scale applications. Conversely, first-order methods are computationally light but often lack reliable infeasibility detection or suffer from slow convergence.

This paper presents the Extrapolated Proportional-Integral Projected Gradient (xPIPG) method. xPIPG is a first-order, matrix-free algorithm that maintains the memory efficiency of its predecessors while achieving significant speedups and providing mathematical guarantees for infeasibility detection.

Methodology: Acceleration via Extrapolation

The xPIPG method builds upon the Proportional-Integral Projected Gradient (PIPG) framework by introducing an extrapolation step into the algorithm's update logic. This step is controlled by a parameter $\rho$, which determines the degree of "look-ahead" during iterations.

The range of the extrapolation step. When $\rho \in [1, 2]$, the algorithm performs extrapolation to accelerate convergence.

By applying averaged operator theory, the authors demonstrate that the algorithm remains stable even when $\rho$ is pushed beyond the standard interpolation range. Specifically, when $\rho \in [1, 2]$, the method effectively extrapolates the update, leading to faster convergence without sacrificing the ability to produce a mathematical "certificate" of infeasibility if no solution exists.

Experimental Evaluation

The performance of xPIPG was evaluated using a benchmark optimal control problem involving a chain of oscillating masses connected by springs. This setup allowed for testing across various problem scales (from 16 to 128 masses) and both feasible and infeasible scenarios.

Performance and Convergence

Numerical experiments indicate that xPIPG consistently achieves a 2x speedup over the original PIPG method. The optimal performance was typically observed with $\rho$ values between 1.5 and 1.9.

In comparative studies, xPIPG outperformed established open-source solvers such as OSQP, SCS, and ECOS. Remarkably, its performance on large-scale problems was found to be competitive with MOSEK, a high-performance commercial solver, despite xPIPG's much simpler implementation.

Discussion and Future Work

The "matrix-free" nature of xPIPG makes it ideal for deployment on resource-constrained hardware, such as embedded controllers in drones or robotic systems. However, as a first-order method, its performance can be sensitive to problem conditioning. Future research directions include the integration of automated preconditioning techniques to handle ill-conditioned problems and the development of adaptive strategies for parameter selection.

Summary updated

BibTeX
@article{yu2023extrapolated,
  author = {Yue Yu and Purnanand Elango and Behçet Açikmese and Ufuk Topcu},
  title = {{Extrapolated Proportional-Integral Projected Gradient Method for Conic Optimization}},
  journal = {IEEE Control. Syst. Lett.},
  year = {2023},
  doi = {10.1109/lcsys.2022.3186647},
}
Figure