Projection-type methods for large convex quadratic programs: theory and computational experience

A well-known approach to the solution of large and sparse linearly constrained quadratic programming (QP) problems is given by the classical projection and splitting methods. These methods have a similar iterative scheme consisting in to solve a sequence of QP subproblems with the constraints of the original problem and an easily solvable Hessian matrix. A theorem of convergence, resuming the main results about the projection and splitting methods, is given for this general scheme. In order to achieve a higher numerical performance than that obtained by projection and splitting methods, we introduce two variants of an iterative scheme that use a variable projection parameter at each step. These two variable projection-type methods differ in the strategy used to assure a sufficient decrease in the objective function f(x). We prove, under very general hypotheses, the convergence of these scheme and we propose two practical, nonexpensive and efficient updating rules for updating the projection parameter.An extensive numerical experimentation shows that the variable projection-type methods have an efficient behaviour.These results are produced by a set of programs available at the URL: http://www.unife.it/AnNum97/index.html. About the solution of the inner subproblems of the projection-type methods, we observe that, when the structure of the constraints does not suggest a particular solver for the QP inner subproblems, we can formulate each inner subproblem as a mixed linear complementarity problem (LCP) that can be solved by the classical projected SOR method of Cryer. When the number of constraints (and, consequently, the size of the inner LCPs) is large, appropriate parallel splitting methods for LCPs can be used for the solution on multiprocessor systems. Finally we describe two applications, arising in the framework of data analysis, that involve QP problems suited to be solved by projection-type methods.