Polynomial affine algorithms for linear programming (Q1814590)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Polynomial affine algorithms for linear programming
scientific article

    Statements

    Polynomial affine algorithms for linear programming (English)
    0 references
    0 references
    25 June 1992
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    steepest descent algorithm with scaling
    0 references
    logarithmic potential function
    0 references
    0 references
    0 references