An interior point method, based on rank-one updates, for linear programming

We propose a polynomial time primal-dual potential reduction algorithm for linear programming. Unlike any other interior point method, the new algorithm is based on a rank-one updating scheme for sequentially computing the projection matrices. For a standard linear programming problem, the number of operations required is [TeX: ${\\cal O}(mn)$] per main iteration and the overall computational complexity is [TeX: ${\\cal O}(mn^{2.5}L)$].

MoreLess

Year of publication:	1995-01-01
Authors:	Sturm, J.F. ; Zhang, Zhang, S.
Institutions:	Faculteit der Economische Wetenschappen, Erasmus Universiteit Rotterdam
Subject:	interior point method \| linear programming \| potential function

More details

Series:	Econometric Institute Research Papers. - ISSN 1566-7294.
Type of publication:	Book / Working Paper
Notes:	The text is part of a series RePEc:ems:eureir Number EI 9546-/A
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010731679