POLYNOMIAL-TIME ALGORITHMS FOR LINEAR-PROGRAMMING BASED ONLY ON PRIMAL SCALING AND PROJECTED GRADIENTS OF A POTENTIAL FUNCTION

This paper presents extensions and further analytical properties of algorithms for linear programming based only on primal scaling and projected gradients of a potential function. The paper contains extensions and analysis of two polynomial-time algorithms for linear programming. We first present an extension of Gonzaga's O(nL) iteration algorithm, that computes dual variables and does not assume a known optimal objective function value. This algorithm uses only affine scaling, and is based on computing the projected gradient of the potential function [GRAPHICS] where x is the vector of primal variables and s is the vector of dual slack variables, and q = n + square-root n. The algorithm takes either a primal step or recomputes dual variables at each iteration. We next present an alternate form of Ye's O(square-root n L) iteration algorithm, that is an extension of the first algorithm of the paper, but uses the potential function [GRAPHICS] where q = n + square-root n. We use this alternate form of Ye's algorithm to show that Ye's algorithm is optimal with respect to the choice of the parameter q in the following sense. Suppose that q = n + n(t) where t greater-than-or-equal-to 0. Then the algorithm will solve the linear program in O(n(r)L) iterations, where r = max{t, 1-t}. Thus the value of t that minimizes the complexity bound is t = 1/2, yielding Ye's O(square-root n L) iteration bound.