Year: 1993
Author: Bing-Sheng He
Journal of Computational Mathematics, Vol. 11 (1993), Iss. 4 : pp. 350–364
Abstract
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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/1993-JCM-9334
Journal of Computational Mathematics, Vol. 11 (1993), Iss. 4 : pp. 350–364
Published online: 1993-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 15