Polynomial affine algorithms for linear programming (Q1814590)

The aim of this paper is to show that polynomial bounds in linear programming algorithms can be obtained without the projective transformation, which is an essential part of Karmarkar's algorithm. The problem: \(\min\bar c' x\) subject to \(x\in S=\{y\in{\mathbf R}^ n: Ay=b,\;y\geq 0\}\) is considered under the usual assumptions: the optimal cost value is zero, \(S\) is compact and a starting feasible solution \(x^ 0\in S\) is known. A simple steepest descent algorithm with scaling is applied to a logarithmic potential function. The scaling and the linesearch may be exact or approximate, in the latter case fixed steplengths are used. It is proved that the number of arithmetical computations necessary to obtain an optimum is \(O(n^ 4 L)\) if \(q\geq n+\sqrt n\), and \(O(n^ 5 L)\) if \(q=n\), for exact scaling. The approximate scaling lowers these bounds to \(O(n^{3.5} L)\) and \(O(n^ 4 L)\), respectively. The paper is certainly successful in convincing the reader that polynomial bounds can be obtained in relatively simple algorithms. It reads well, the style is clear and straightforward. The proofs are given in full detail so that the several misprints can be easily recognized. Only the notation used in the proof of Lemma 3.2 is a little misleading: according to Algorithm 1.1, \(y^*\) need not be a strictly optimal result of the linesearch.