J. Gondzio and F. N. C. Sobral
Abstract
Interior Point Methods (IPM) rely on the Newton method for solving
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 efficiently solving linear systems, IPMs enjoy fast
convergence 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 directly 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.
Key words: Broyden Method, Quasi-Newton, Interior Point Methods, Matrix-free, Quadratic Programming Problems.