We propose a gradient-based method for quadratic programming problems with asingle linear constraint and bounds on the variables. Inspired by the GPCGalgorithm for bound-constrained convex quadratic programming [J.J. Mor'e andG. Toraldo, SIAM J. Optim. 1, 1991], our approach alternates between two phasesuntil convergence: an identification phase, which performs gradient projectioniterations until either a candidate active set is identified or no reasonableprogress is made, and an unconstrained minimization phase, which reduces theobjective function in a suitable space defined by the identification phase, byapplying either the conjugate gradient method or a recently proposed spectralgradient method. However, the algorithm differs from GPCG not only because itdeals with a more general class of problems, but mainly for the way it stopsthe minimization phase. This is based on a comparison between a measure ofoptimality in the reduced space and a measure of bindingness of the variablesthat are on the bounds, defined by extending the concept of proportioning,which was proposed by some authors for box-constrained problems. If theobjective function is bounded, the algorithm converges to a stationary pointthanks to a suitable application of the gradient projection method in theidentification phase. For strictly convex problems, the algorithm converges tothe optimal solution in a finite number of steps even in case of degeneracy.Extensive numerical experiments show the effectiveness of the proposedapproach.
展开▼
