Optimization Online


A New Preconditioning Approach for an Interior Point-Proximal Method of Multipliers for Linear and Convex Quadratic Programming

Luca Bergamaschi(berga***at***dmsa.unipd.it)
Jacek Gondzio(J.Gondzio***at***ed.ac.uk)
Ángeles Martínez(amartinez***at***units.it)
John W. Pearson(J.Pearson***at***ed.ac.uk)
Spyridon Pougkakiotis(s.pougkakiotis***at***ed.ac.uk)

Abstract: In this paper, we address the efficient numerical solution of linear and quadratic programming problems, often of large scale. With this aim, we devise an infeasible interior point method, blended with the proximal method of multipliers, which in turn results in a primal-dual regularized interior point method. Application of this method gives rise to a sequence of increasingly ill-conditioned linear systems which cannot always be solved by factorization methods, due to memory and CPU time restrictions. We propose a novel preconditioning strategy which is based on a suitable sparsification of the normal equations matrix in the linear case, and also constitutes the foundation of a block-diagonal preconditioner to accelerate MINRES for linear systems arising from the solution of general quadratic programming problems. Numerical results for a range of test problems demonstrate the robustness of the proposed preconditioning strategy, together with its ability to solve linear systems of very large dimension.

Keywords: Primal-dual regularization, Proximal point algorithm, Interior point methods, Krylov methods, Preconditioners

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical Report ERGO-19-017.

Download: [PDF]

Entry Submitted: 12/20/2019
Entry Accepted: 12/20/2019
Entry Last Modified: 12/20/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society