An interior point-proximal method of multipliers for linear positive semi-definite programming

Spyridon Pougkakiotis (Lead / Corresponding author), Jacek Gondzio

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)
49 Downloads (Pure)

Abstract

In this paper we generalize the Interior Point-Proximal Method of Multipliers (IP-PMM) presented in Pougkakiotis and Gondzio (Comput Optim Appl 78:307–351, 2021. https://doi.org/10.1007/s10589-020-00240-9) for the solution of linear positive Semi-Definite Programming (SDP) problems, allowing inexactness in the solution of the associated Newton systems. In particular, we combine an infeasible Interior Point Method (IPM) with the Proximal Method of Multipliers (PMM) and interpret the algorithm (IP-PMM) as a primal-dual regularized IPM, suitable for solving SDP problems. We apply some iterations of an IPM to each sub-problem of the PMM until a satisfactory solution is found. We then update the PMM parameters, form a new IPM neighbourhood, and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under mild assumptions, and without requiring exact computations for the Newton directions. We furthermore provide a necessary condition for lack of strong duality, which can be used as a basis for constructing detection mechanisms for identifying pathological cases within IP-PMM.

Original languageEnglish
Pages (from-to)97-129
Number of pages33
JournalJournal of Optimization Theory and Applications
Volume192
Issue number1
Early online date28 Oct 2021
DOIs
Publication statusPublished - Jan 2022

Keywords

  • Interior Point Method
  • Proximal method of multipliers
  • Proximal point method
  • Regularized Interior Point Methods
  • Semidefinite programming

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'An interior point-proximal method of multipliers for linear positive semi-definite programming'. Together they form a unique fingerprint.

Cite this