A NOTE ON A POTENTIAL REDUCTION ALGORITHM FOR LP WITH SIMULTANEOUS PRIMAL DUAL UPDATING

Potential function reduction algorithms for linear programming and the linear complementarity problem use key projections p(x) and p(s) which are derived from the 'double' potential function, phi(x, s) = rho ln(x(T)s)-SIGMA(j = 1)n ln(x(j)s(j)), where x and s are primal and dual slacks vectors. For non-symmetric LP duality we show that the existence of sBAR, yBAR, xBAR satisfying sBAR = c - A(T)yBAR, AxBAR = b such that p(x) = (rho/x(T)s)XsBAR - e and p(s) = (rho/x(T)s)SxBAR - e yields simultaneous primal and dual projection-based updating during the process of reducing the potential function phi. The role of xBAR, sBAR in an O(square-root n L) simultaneous primal-dual update algorithm is discussed.