EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4398. Regularized Interior Point Methods for Convex Programming

Invited abstract in session MA-2: EDDA, stream EURO Doctoral Dissertation Award.

Monday, 8:30-10:00
Room: Glassalen (building: 101)

Authors (first author is the speaker)

1. Spyridon Pougkakiotis
School of Mathematics, University of Edinburgh

Abstract

Large-scale convex optimization is integral to several application domains, given its amenability to efficient solution methods and its versatile modeling capabilities. Interior Point Methods (IPMs) represent a widely adopted class of optimization techniques for solving convex problems due to their ability to yield accurate solutions with a polynomial complexity guarantee. However, challenges such as numerical inaccuracy and ill-posedness of the underlying optimization problem can impede their performance.

To address these challenges, researchers have explored regularized versions of IPMs, which exhibit improved robustness in practical scenarios. Despite the practical success of regularized IPMs, a comprehensive theoretical understanding has been lacking until recently.

In this talk, we present an infeasible IPM combined with the Proximal Method of Multipliers (PMM). The resulting algorithm (IP-PMM) is interpreted as a primal-dual regularized IPM, suitable for solving convex programming problems. We apply few iterations of the interior point method to each sub-problem of the proximal method of multipliers. Once a satisfactory solution of the PMM sub-problem is found, we update the PMM parameters, form a new IPM neighbourhood, and repeat this process.

Crucially, we demonstrate the polynomial complexity of the algorithm for a broad class of convex problems under standard assumptions, marking a significant advancement as the first polynomial complexity result for a primal-dual regularized IPM. By inheriting the polynomial complexity of IPMs and the numerical stability of PMMs, IP-PMM offers a promising solution.

To enhance the applicability of our approach, we discuss general-purpose preconditioning strategies for efficiently solving the associated linear systems within IP-PMM. Subsequently, we present numerical results spanning a diverse range of convex programming problems, showcasing the benefits of regularization in IPMs and affirming the reliability and efficiency of the proposed IP-PMM algorithm.

Keywords

Status: accepted

Back to the list of papers