A surface of analytic centers and primal–dual infeasible-interior-point algorithms for linear-programming

A surface of analytic centers and primal–dual infeasible-interior-point algorithms for linear-programming

0.00 Avg rating0 Votes
Article ID: iaor20032990
Country: United States
Volume: 20
Issue: 1
Start Page Number: 135
End Page Number: 162
Publication Date: Feb 1995
Journal: Mathematics of Operations Research
Authors: , ,
Abstract:

We define a surface of analytic centers determined by a primal–dual pair of linear programming problems and an infeasible interior point. Then we study the boundary of the surface by analyzing limiting behavior of paths on the surface and sequences in a neighborhood of the surface. We introduce generic primal–dual infeasible-interior-point algorithms in which the search direction is the Newton direction for a system defining a point on the surface. We show that feasible-interior-point algorithms for artificial self-dual problems and for an artificial primal–dual pair of linear programming problems can be considered as special cases of these infeasible-interior-point algorithms or simple variants of them. In this sense, there are O(√(nL))-iteration primal–dual infeasible-interior-point algorithms for linear programming.

Reviews

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