TY - JOUR T1 - Further Developments in an Iterative Projection and Contraction Method for Linear Programming AU - He , Bing-Sheng JO - Journal of Computational Mathematics VL - 4 SP - 350 EP - 364 PY - 1993 DA - 1993/11 SN - 11 DO - http://doi.org/ UR - https://global-sci.org/intro/article_detail/jcm/9334.html KW - AB -

A linear programming problem can be translated into an equivalent general linear complementarity problem, which can be solved by an iterative projection and contraction (PC) method [6]. The PC method requires only two matrix-vector multiplications at each iteration and the efficiency in practice usually depends on the sparsity of the constraint-matrix. The prime PC algorithm in [6] is globally convergent; however, no statement can be made about the rate of convergence. Although a variant of the PC algorithm with constant step-size for linear programming [7] has a linear speed of convergence, it converges much slower in practice than the prime method [6]. In this paper, we develop a new step-size rule for the PC algorithm for linear programming such that the resulting algorithm is globally linearly convergent. We present some numerical experiments to indicate that it also works better in practice than the prime algorithm.