On a wide region of centers and primal–dual interior point algorithms for linear programming

On a wide region of centers and primal–dual interior point algorithms for linear programming

0.00 Avg rating0 Votes
Article ID: iaor2004745
Country: United States
Volume: 22
Issue: 2
Start Page Number: 408
End Page Number: 431
Publication Date: May 1997
Journal: Mathematics of Operations Research
Authors: ,
Keywords: duality, interior point methods
Abstract:

In the adaptive step primal–dual interior point method for linear programming, polynomial algorithms are obtained by computing Newton directions towards targets on the central path, and restricting the iterates to a neighborhood of this central path. In this paper, the adaptive step methodology is extended, by considering targests in a certain central region, which contains the usual central path, and subsequently generating iterates in a neighborhood of this region. The size of the central region can vary from the central path to the whole feasible region by choosing a certain parameter. An O(√(nL)) iteration bound is obtained under mild conditions on the choice of the target points. In particular, we leave plenty of room for experimentation with search directions. The practical performance of the new primal–dual interior point method is measured on part of the Netlib test set for various sizes of the central region.

Reviews

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