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, S.
Institutions:	Erasmus University Rotterdam, Econometric Institute
Subject:	linear programming \| potential function \| interior point method

More details

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

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