Quasi-Newton approaches to Interior Point Methods for quadratic problems

Jacek Gondzio, F. N. C. Sobral

Research output: Contribution to journalArticlepeer-review

Abstract

Interior Point Methods (IPM) rely on the Newton method for solv-
ing systems of nonlinear equations. Solving the linear systems which arise from
this approach is the most computationally expensive task of an interior point
iteration. If, due to problem's inner structure, there are special techniques
for eciently solving linear systems, IPMs demonstrate a reduced computing
time and are able to solve large scale optimization problems. It is tempting to
try to replace the Newton method by quasi-Newton methods. Quasi-Newton
approaches to IPMs either are built to approximate the Lagrangian function
for nonlinear programming problems or provide an inexpensive preconditioner.
In this work we study the impact of using quasi-Newton methods applied di-
rectly to the nonlinear system of equations for general quadratic programming
problems. The cost of each iteration can be compared to the cost of computing
correctors in a usual interior point iteration. Numerical experiments show that
the new approach is able to reduce the overall number of matrix factorizations
and is suitable for a matrix-free implementation.
Original languageEnglish
Pages (from-to)93-120
JournalComputational optimization and applications
Volume74
Issue number1
Early online date2 May 2019
DOIs
Publication statusPublished - 30 Sep 2019

Fingerprint

Dive into the research topics of 'Quasi-Newton approaches to Interior Point Methods for quadratic problems'. Together they form a unique fingerprint.

Cite this