Dynamic Non-diagonal Regularization in Interior Point Methods for Linear and Convex Quadratic Programming

Spyridon Pougkakiotis (Lead / Corresponding author), Jacek Gondzio

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)
12 Downloads (Pure)

Abstract

In this paper, we present a dynamic non-diagonal regularization for interior point methods. The non-diagonal aspect of this regularization is implicit, since all the off-diagonal elements of the regularization matrices are cancelled out by those elements present in the Newton system, which do not contribute important information in the computation of the Newton direction. Such a regularization has multiple goals. The obvious one is to improve the spectral properties of the Newton system solved at each iteration of the interior point method. On the other hand, the regularization matrices introduce sparsity to the aforementioned linear system, allowing for more efficient factorizations. We also propose a rule for tuning the regularization dynamically based on the properties of the problem, such that sufficiently large eigenvalues of the non-regularized system are perturbed insignificantly. This alleviates the need of finding specific regularization values through experimentation, which is the most common approach in the literature. We provide perturbation bounds for the eigenvalues of the non-regularized system matrix and then discuss the spectral properties of the regularized matrix. Finally, we demonstrate the efficiency of the method applied to solve standard small- and medium-scale linear and convex quadratic programming test problems.

Original languageEnglish
Pages (from-to)905-945
Number of pages41
JournalJournal of Optimization Theory and Applications
Volume181
Issue number3
Early online date26 Feb 2019
DOIs
Publication statusPublished - 1 Jun 2019

Keywords

  • Generalized proximal point methods
  • Interior point methods
  • Primal–dual regularization

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Dynamic Non-diagonal Regularization in Interior Point Methods for Linear and Convex Quadratic Programming'. Together they form a unique fingerprint.

Cite this