Proximal Stabilized Interior Point Methods and Low-Frequency-Update Preconditioning Techniques

Stefano Cipolla, Jacek Gondzio

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In this work, in the context of Linear and convex Quadratic Programming, we consider Primal Dual Regularized Interior Point Methods (PDR-IPMs) in the framework of the Proximal Point Method. The resulting Proximal Stabilized IPM (PS-IPM) is strongly supported by theoretical results concerning convergence and the rate of convergence, and can handle degenerate problems. Moreover, in the second part of this work, we analyse the interactions between the regularization parameters and the computational footprint of the linear algebra routines used to solve the Newton linear systems. In particular, when these systems are solved using an iterative Krylov method, we are able to show—using a new rearrangement of the Schur complement which exploits regularization—that general purposes preconditioners remain attractive for a series of subsequent IPM iterations. Indeed, if on the one hand a series of theoretical results underpin the fact that the approach here presented allows a better re-use of such computed preconditioners, on the other, we show experimentally that such (re)computations are needed only in a fraction of the total IPM iterations. The resulting regularized second order methods, for which low-frequency-update of the preconditioners are allowed, pave the path for an alternative class of second order methods characterized by reduced computational effort.
Original languageEnglish
JournalJournal of Optimization Theory and Applications
Early online date5 Apr 2023
DOIs
Publication statusE-pub ahead of print - 5 Apr 2023

Fingerprint

Dive into the research topics of 'Proximal Stabilized Interior Point Methods and Low-Frequency-Update Preconditioning Techniques'. Together they form a unique fingerprint.

Cite this