Gradient-based methods with subspace acceleration for quadratic programming problems and applications

In this work we propose a gradient-based framework, called "Proportionality-based Subspace Accelerated framework for Quadratic Programming" (PSAQP), for quadratic programming problems. Inspired by the Gradient Projection Conjugate Gradient (GPCG) algorithm for bound-constrained convex quadratic programming [J. J. Moré and G. Toraldo, SIAM J. Optim., 1 (1991), pp. 93{113], our approach alternates between two phases until convergence: an identification phase, which performs gradient projection iterations until either a candidate active set is identified or no reasonable progress is made, and an unconstrained minimization phase, which reduces the objective function in a suitable space defined by the identification phase. The proposed framework differs from GPCG not only because it deals with a more general class of problems, but mainly for the way it stops the minimization phase. Indeed, thanks to a component-wise reformulation of the first-order KKT conditions, we introduce a way to estimate the Lagrange multipliers which is exploited to formulate an efficient criterion to switch between the two phases. The criterion is based on a comparison between a measure of optimality in the reduced space and a measure of bindingness of the variables that are on the bounds, defined by extending the concept of proportional iterate, which was proposed by some authors for box-constrained problems. If the objective function is bounded, every method fitting in the framework converges to a stationary point thanks to a suitable application of the gradient projection method in the identification phase. For strictly convex problems, finite convergence is proved even in the case of degeneracy. We develop a two-phase gradient method called "Proportionality-based 2-phase Gradient Projection" (P2GP), which can be considered as a specialization of PSAQP to the case of convex and nonconvex quadratic programming problems subject to bound constraints and possibly a single linear equality constraint. P2GP, which is able to exploit efficient spectral steplength for both the two phases, shows to perform better or comparably to state-of-the-art algorithms for the same class of problems, as shown by the comparison performed on randomly generated problems and problems arising in the training of support vector machines (SVM). Motivated by the good numerical performance of P2GP in the solution of bound constrained problems, we compared it with the MPRGP algorithm [Dostál and Schöberl, 2005] as solver for the inner problems arising in an Augmented Lagrangian framework for the solution of contact mechanics problems. The performed experiments suggest that P2GP is competitive with MPRGP and, thanks to the identification properties of the gradient projection, it can result favorable when the number of active constraints at the solution is high.