Optimization Online


Matrix-Free Interior Point Method

Jacek Gondzio(J.Gondzio***at***ed.ac.uk)

Abstract: In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods and imposes restrictions on the way the preconditioner is computed. A two-step approach is used to design a preconditioner. First, the Newton equation system is regularized to guarantee better numerical properties and then it is preconditioned. The preconditioner is {\it implicit}, that is, its computation requires only matrix-vector multiplications with the original problem data. The method is therefore well-suited to problems in which matrices are not explicitly available and/or are too large to be stored in computer memory. Numerical properties of the approach are studied including the analysis of the conditioning of the regularized system and that of the preconditioned regularized system. The method has been implemented and preliminary computational results for small problems limited to 1 million of variables and 10 million of nonzero elements demonstrate the feasibility of the approach.

Keywords: Linear Programming, Quadratic Programming, Matrix-Free, Interior Point Methods, Iterative Methods, Implicit Preconditioner.

Category 1: Nonlinear Optimization (Quadratic Programming )

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

Citation: Technical Report ERGO-2009-012 School of Mathematics and Maxwell Institute for Mathematical Sciences, The University of Edinburgh, October 5, 2009

Download: [Postscript][PDF]

Entry Submitted: 10/07/2009
Entry Accepted: 10/07/2009
Entry Last Modified: 10/07/2009

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 Programming Society