A modified layered-step interior-point algorithm for linear programming

A modified layered-step interior-point algorithm for linear programming

0.00 Avg rating0 Votes
Article ID: iaor20001125
Country: Netherlands
Volume: 82
Issue: 3
Start Page Number: 339
End Page Number: 355
Publication Date: Aug 1998
Journal: Mathematical Programming
Authors: , ,
Keywords: programming: convex
Abstract:

The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient matrix A. The main drawback of the algorithm is the use of an unknown big constant χA in computing the search direction and to initiate the algorithm. We propose a modified layered-step interior-point algorithm which does not use the big constant in computing the search direction. The constant is required only for initialization when a well-centered feasible solution is not available, and it is not required if an upper bound on the norm of a primal–dual optimal solution is known in advance. The complexity of the simplified algorithm is the same as that of Vavasis and Ye.

Reviews

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