Optimization Online


Quasi-Newton approaches to Interior Point Methods for quadratic problems

Jacek Gondzio(J.Gondzio***at***ed.ac.uk)
Francisco N. C. Sobral(fncsobral***at***uem.br)

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.

Keywords: Broyden Method, Quasi-Newton, Interior Point Methods, Matrix-free, Quadratic Programming Problems

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation: Technical Report ERGO 18-015, School of Mathematics, June 25, 2018

Download: [PDF]

Entry Submitted: 06/26/2018
Entry Accepted: 06/26/2018
Entry Last Modified: 06/26/2018

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