AFFINE SCALING

Affine scaling - A variant of Karmarkar's algorithm for the linear program in standard form: Min(cx:x >= 0, Ax = b), where A has full row rank.

Here are the basic steps (of the primal method ).
1. Given x > 0, let X = diag(x_j).
2. Estimate dual:y = [AX²A']^–1 A[X²]c' and d = c - y'A.
3. Move: x' = x - aX²d'/Max(d_j x_j), where a is a parameter in (0, 1).

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