On the convergence properties of Hildreth’s quadratic programming algorithm. (English) Zbl 0712.90054

The linear convergence rate of Hildreth’s algorithm with an almost cyclic control for convex quadratic programming problems is proved. The proof is carried out for both its sequential and simultaneous version. Bounds on the convergence rate are derived. The results are compared with those obtained previously by J. Mandel [Math. Program. 30, 218-228 (1984; Zbl 0545.90068)].
Reviewer: K.Zimmermann


90C20 Quadratic programming
65K05 Numerical mathematical programming methods
90C25 Convex programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming


Zbl 0545.90068
Full Text: DOI


[1] S. Agmon, ”The relaxation method for linear inequalities,”Canadian Journal of Mathematics 6 (1954) 382–392. · Zbl 0055.35001
[2] Y. Censor, ”Row-action methods for huge and sparse systems and their applications,”SIAM Review 23 (1981) 444–466. · Zbl 0469.65037
[3] Y. Censor and G.T. Herman, ”Row generation methods for feasibility and optimization problems involving sparse matrices and their applications,” in: I.S. Duff and G.W. Stewart, eds.,Sparse Matrix Proceedings 1978 (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1979) pp. 197–219.
[4] J.L. Goffin, ”The relaxation method for solving systems of linear inequalities,”Mathematics of Operations Research 5 (1980) 388–414. · Zbl 0442.90051
[5] R. Gordon and G.T. Herman, ”Three-dimensional reconstruction from projections: A review of algorithms,”International Review of Cytology 38 (1974) 111–151.
[6] G.T. Herman and A. Lent, ”Iterative reconstruction algorithms,”Computers in Biology and Medicine 6 (1976) 273–294.
[7] G.T. Herman and A. Lent, ”A family of iterative quadratic optimization algorithms for pairs of inequalities with applications in diagnostic radiology,”Mathematical Programming Study 9 (1978) 15–29. · Zbl 0389.90078
[8] C. Hildreth, ”A quadratic programming procedure,”Naval Research Logistics Quarterly 4 (1957) 79–85. [Erratum,ibid., p. 361.]
[9] A.N. Iusem and A.R. De Pierro, ”A simultaneous iterative method for computing projections on polyhedra,”SIAM Journal on Control 25 (1986) 231–243. · Zbl 0621.90061
[10] S. Kaczmarz, ”Angenäherte Auflösung von Systemen linearer Gleichungen,”Bulletin International de l’Academie Polonaise de Sciences et Lettres A35 (1937) 355–357. · Zbl 0017.31703
[11] A. Lent and Y. Censor, ”Extensions of Hildreth’s row-action method for quadratic programming,”SIAM Journal on Control 18 (1980) 444–454. · Zbl 0444.49025
[12] J. Mandel, ”Convergence of the cyclical relaxation method for linear inequalities,”Mathematical Programming 30 (1984) 218–228. · Zbl 0545.90068
[13] O.L. Mangasarian, ”Solution of symmetric linear complementarity problems by iterative methods,”Journal of Optimization Theory and Applications 22 (1977) 465–485. · Zbl 0341.65049
[14] T.H. Motzkin and I.J. Schoenberg, ”The relaxation method for linear inequalities,”Canadian Journal of Mathematics 6 (1954) 393–404. · Zbl 0055.35002
[15] J.S. Pang, ”More results on the convergence of iterative methods for the symmetric linear complementarity problem,”Journal of Optimization Theory and Applications 49 (1986) 107–134. · Zbl 0568.90096
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.