Groupe d’études et de recherche en analyse des décisions

G-2021-03

RipQP: A multi-precision regularized predictor-corrector method for convex quadratic optimization

et

We describe a Julia implementation of Mehrotra's predictor-corrector method for convex quadratic optimization that is entirely open source and generic in that it is able to accommodate computations in multiple floating-point systems. As a result, our code, named RipQP (Orban and Leconte, 2020), can be initialized in a low-precision system such as Float16 as a form of warm start, and gradually transition through higher-precision systems until it reaches the accuracy tolerances prescribed by the user. On platforms with hardware for various floating-point systems, our strategy results in savings in terms of time, number of normalized iterations, and energy expended during the computations. RipQP employs primal and dual regularization as described by Friedlander and Orban (2012), solves symmetric and quasi-definite systems at each iteration, and is competitive with Gurobi, CPLEX and Xpress on standard collections of linear and quadratic optimization problems in double precision in terms of number of iterations and time.

, 34 pages