Two-thirds is sharp for affine scaling

Leslie A. Hall, Robert J. Vanderbei

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


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 we 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.

Original languageEnglish (US)
Pages (from-to)197-201
Number of pages5
JournalOperations Research Letters
Issue number4
StatePublished - May 1993

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


  • affine-scaling algorithms
  • fixed points
  • linear programming algorithms
  • linear programming theory


Dive into the research topics of 'Two-thirds is sharp for affine scaling'. Together they form a unique fingerprint.

Cite this