Improved complexity using higher-order correctors for primal–dual Dikin affine scaling

Improved complexity using higher-order correctors for primal–dual Dikin affine scaling

0.00 Avg rating—0 Votes
Article ID: iaor1998416
Country: Netherlands
Volume: 76
Issue: 1
Start Page Number: 117
End Page Number: 130
Publication Date: Jan 1997
Journal: Mathematical Programming
Authors: , , ,
Keywords: programming: linear
Abstract:

In this paper we show that the primal–dual Dikin affine scaling algorithm for linear programming of Jansen, Roos and Terlaky enhances an asymptotical O(√(n)L) complexity by using corrector steps. We also show that the result remains valid when the method is applied to positive semi-definite linear complementarity problems.

Reviews

Required fields are marked *. Your email address will not be published.