Optimization Online


An inexact potential reduction method for linear programming

Lukas Schork(L.Schork***at***ed.ac.uk)
Jacek Gondzio(J.Gondzio***at***ed.ac.uk)

Abstract: A class of interior point methods using inexact directions is analysed. The linear system arising in interior point methods for linear programming is reformulated such that the solution is less sensitive to perturbations in the right-hand side. For the new system an implementable condition is formulated that controls the relative error in the solution. Based on this condition, a feasible and an infeasible potential reduction method are described which retain the convergence and complexity bounds known for exact directions.

Keywords: Interior point methods, inexact directions, error control

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

Citation: Technical Report ERGO-16-005, School of Mathematics, University of Edinburgh, Edinburgh EH9 3FD, Scotland, UK

Download: [Postscript][PDF]

Entry Submitted: 07/29/2016
Entry Accepted: 07/29/2016
Entry Last Modified: 07/29/2016

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