Polynomial affine algorithms for linear programming

The method of steepest descent with scaling (affine scaling) applied to the potential functionq logcx — _i=1ⁿ logx_i solves the linear programming problem in polynomial time forq n. Ifq = n, then the algorithm terminates in no more than O(n²L) iterations; if q n + withq = O(n) then it takes no more than O(nL) iterations. A modified algorithm using rank-1 updates for matrix inversions achieves respectively O(n⁴L) and O(n^3.5L) arithmetic computions.