A successive over-relaxation method for quadratic programming problems with interval constraints

Hildreth’s algorithm is a classical iterative method for solving strictly convex quadratic programming problems, which uses the rows of constraint matrix just one at a time. This algorithm is particularly suited to large and sparse problems, because it acts upon the given problem data directly and the coefficient matrix is never modified in the course of the iterations. The original Hildreth’s algorithm is mathematically equivalent to the Gauss-Seidel method applied to the dual of the given quadratic programming problem. In this paper, the authors propose an SOR modification of Hildreth’s algorithm for solving interval constrained quadratic programming problems. They prove global convergence of the algorithm and show that the rate of convergence is linear. Computational results are also presented to demonstrate the effectiveness of the algorithm.