Group for Research in Decision Analysis

A two-phase gradient algorithm for quadratic programming problems with a single linear constraint and bounds on the variables

Daniela di Serafino University of Campania "Luigi Vanvitelli", Italy

We propose a gradient-based algorithmic framework for Quadratic Programming problems with a Single Linear constraint and Bounds on the variables (SLBQPs). These problems arise in several applications, e.g. support vector machine training, portfolio selection, multicommodity network flow and logistics; furthermore, SLBQPs can be regarded as "building blocks" for solving some more general constrained nonlinear problems. Inspired by the GPCG algorithm for bound-constrained convex quadratic programming [J.J. Moré and G. Toraldo, SIAM J. Optim., 1, 1991], our approach alternates between two phases until convergence: an identification phase, which performs Gradient Projection (GP) steps 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, by applying either the Conjugate Gradient method or recently proposed spectral GP methods. If the objective function is bounded, convergence to a stationary point holds thanks to a suitable application of GP in the identification phase. For strictly convex problems, finite convergence to the solution can be proved even in case of degeneracy. Numerical experiments show the effectiveness of the proposed approach.

This is joint work with Gerardo Toraldo (University of Naples Federico II, Italy) and Marco Viola (Sapienza University of Rome, Italy)


Free entrance.
Welcome to everyone!