×

A simultaneous projections method for linear inequalities. (English) Zbl 0552.65051

In this very readable paper, the authors study an iterative method for solving systems of finitely many linear inequalities in finitely many variables. Recently suggested by Censor and Elfving, the algorithm is a variant of Cimmino’s method for solving linear systems. Each iterate is a convex combination of the orthogonal projections of its predecessor on the half-spaces defined by the linear inequalities. The authors show that for any starting point the method converges for both consistent and inconsistent systems (to a feasible point in the first case and to a weighted least squares type solution in the second). The method is well suited for implementation on computers capable of performing parallel computation.
Reviewer: R.W.Cottle

MSC:

65K05 Numerical mathematical programming methods
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Censor, Y., Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23, 444-466 (1981) · Zbl 0469.65037
[2] Censor, Y.; Elfving, T., New Methods for linear inequalities, Linear Algebra Appl., 42, 199-211 (1982) · Zbl 0479.65039
[3] Cimmino, G., Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, La Ricerca Scientifica. La Ricerca Scientifica, Roma. La Ricerca Scientifica. La Ricerca Scientifica, Roma, Anno IX, 1, 326-333 (1938), XVI, Ser. II · JFM 64.1244.02
[4] Cottle, R. W.; Pang, Y. S., On solving linear complementarity problems as linear programs, Math. Programming Stud., 7, 88-107 (1978) · Zbl 0381.90072
[5] Gastinel, N., Analyse Numérique Linéaire (1966), Hermann: Hermann Paris · Zbl 0151.21202
[6] Herman, G. T., Image Reconstruction from Projections: The Fundamentals of Computerized Tomography (1980), Academic: Academic New York · Zbl 0538.92005
[7] Mangasarian, O. L., Linear complementarity problems solvable by a single linear programm, Math. Programming, 10, 263-270 (1976) · Zbl 0355.90040
[8] Nashed, M. N., Continuous and semicontinuous analogues of iterative methods of Cimmino and Kaczmarz with applications to the inverse Radon transform, (Herman, G. T.; Natterer, F., Mathematical Aspects of Computerized Tomography. Mathematical Aspects of Computerized Tomography, Lecture Notes in Medical Informatics, 8 (1981), Springer: Springer Berlin), 160-178 · Zbl 0544.65090
[9] Rockafeller, R. T., Convex Analysis (1970), Cambridge U.P
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.