Two-thirds is sharp for affine scaling

Two-thirds is sharp for affine scaling

0.00 Avg rating0 Votes
Article ID: iaor1995329
Country: Netherlands
Volume: 13
Issue: 4
Start Page Number: 197
End Page Number: 201
Publication Date: May 1993
Journal: Operations Research Letters
Authors: ,
Abstract:

Tsuchiya and Muramatsu recently proved that the affine-scaling algorithm for linear programming generates convergent sequences of primal and dual variables whose limits are optimal for the corresponding primal and dual problems as long as the step size is no more than two-thirds of the distance to the nearest face of the polytope. An important feature of this result is that it does not require any nondegeneracy assumptions. In this paper the authors show that Tsuchiya and Muramatsu’s result is sharp by providing a simple linear programming problem for which the sequence of dual variables fails to converge for every step size greater than two-thirds.

Reviews

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