Affine scaling

Lore & Background

Affine scaling was first published by I. I. Dikin at the Energy Systems Institute of the Russian Academy of Sciences (then the Siberian Energy Institute, USSR Academy of Sciences) in the 1967 Doklady Akademii Nauk SSSR. Dikin followed this with a proof of its convergence in 1974, but his work went largely unnoticed until the 1984 discovery of Karmarkar's algorithm, the first practical polynomial time algorithm for linear programming. The importance and complexity of Karmarkar's method prompted mathematicians to search for a simpler version. Several groups then independently came up with a variant of Karmarkar's algorithm, replacing the projective transformations Karmarkar used with affine ones. After a few years, it was realized that these 'new' affine scaling algorithms were reinventions of Dikin's decades-old results.

Reader's Guide

Affine scaling works in two phases: the first finds a feasible point, and the second performs optimization while staying strictly inside the feasible region. Both phases solve linear programs in equality form using an iterative method that computes projected gradient descent steps in a re-scaled version of the problem. The algorithm's convergence depends on the step size β; for β ≤ 2/3, Vanderbei's variant has been proven to converge, while for β > 0.995 an example problem converges to a suboptimal value. Other variants show chaotic behavior even on small problems when β > 2/3. The algorithm's history of multiple discovery highlights how Dikin's original 1967 work was overlooked until the 1980s, when it was independently reinvented by E. R. Barnes at IBM, a team led by R. J. Vanderbei at AT&T, and others. Karmarkar himself also came up with affine scaling in this timeframe, mistakenly believing it converged as quickly as his own algorithm.

Did You Know?

• Affine scaling was first published by Soviet mathematician I. I. Dikin in 1967.
• The algorithm was independently reinvented in the mid-1980s by several groups, including E. R. Barnes at IBM and a team led by R. J. Vanderbei at AT&T.
• For step sizes β > 0.995, an example problem is known that converges to a suboptimal value.
• Karmarkar mistakenly believed affine scaling converged as quickly as his own algorithm.