 # Affine scaling

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$).