Affine scaling

From Glossary

Jump to: navigation, search

A variant of Karmarkar's algorithm for the linear program in standard form: LaTeX:  \min \{c^T x : x \ge 0, \; Ax = b \}, where LaTeX: A has full row rank.

Here are the basic steps (of the primal method).

  1. Given LaTeX: x > 0, let LaTeX:  X = \mbox{diag}(x).
  2. Estimate dual: LaTeX:  y = [AX^2A^T]^{-1} AX^2c and LaTeX: d = c - A^T y.
  3. Move: LaTeX: x = x - aX^2d / \|Xd\|_{\infty}, where LaTeX: a is a parameter in LaTeX: (0, 1).

Multiplication of LaTeX: A and LaTeX: c by LaTeX: X is a scaling operation, using current levels as scale values -i.e. LaTeX: AX multiplies column LaTeX: j of LaTeX: A by LaTeX: x_j, and LaTeX: Xc multiplies LaTeX: c_j by LaTeX: x_j. Note that the reduced cost LaTeX: d is in the null space of LaTeX: A -i.e. LaTeX: Ad = 0, so LaTeX: d is a feasible direction. This affine scaling direction is used in its own right in interior methods. It minimizes the duality gap subject to LaTeX: Ax = b and LaTeX: x in an ellipsoid (replacing LaTeX: x \ge 0).

Personal tools