×

Parallel successive overrelaxation methods for symmetric linear complementarity problems and linear programs. (English) Zbl 0595.90090

A parallel successive overrelaxation (SOR) method is proposed for the solution of the fundamental symmetric linear complementarity problem. Convergence is established under a relaxation factor which approaches the classical value of 2 for a loosely coupled problem. The parallel SOR approach is then applied to solve the symmetric linear complementarity problem associated with the least norm solution of a linear program.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mangasarian, O. L.,Solution of Symmetric Linear Complementarity Problems by Iterative Methods, Journal of Optimization Theory and Applications, Vol. 22, pp. 465-485, 1977. · Zbl 0341.65049
[2] Mangasarian, O. L.,Normal Solutions of Linear Programs, Mathematical Programming Study, Vol. 22, pp. 206-216, 1984. · Zbl 0588.90058
[3] Mangasarian, O. L.,Sparsity-Preserving SOR Algorithms for Separable Quadratic and Linear Programming, Computer and Operations Research, Vol. 11, pp. 105-112, 1984. · Zbl 0606.90102
[4] Mangasarian, O. L., andDe Leone, R.,A Parallel Successive Overrelaxation (SOR) Algorithm for Linear Programming, 12th International Symposium on Mathematical Programming, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1985.
[5] Ortega, J. W.,Numerical Analysis: A Second Course, Academic Press, New York, New York, 1972. · Zbl 0248.65001
[6] Subramanian, P. K.,Iterative Methods of Soluton for Complementarity Problems, University of Wisconsin-Madison, PhD Thesis, 1985.
[7] Mangasarian, O. L., andDe Leone, R.,Error Bounds for Strongly Convex Programs and (Super) Linearly Convergent Iterative Schemes for the Least 2-Norm Solution of Linear Programs, University of Wisconsin-Madison, Applied Mathematics and Optimization, 1987. · Zbl 0645.90062
[8] DeWitt, D., Finkel, R., andSolomon, M.,The Crystal Multicomputer: Design and Implementing Experience, IEEE Transactions on Software Engineering, 1987.
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.