Seminario del 2019

Gradient projection (GP) methods have proved to be very efficient in the solution of optimization problems in which the projection onto the feasible set can be computed cheaply. In this seminar we, at first, review the theoretical results and algorithmic techniques developed for the case of bound constrained quadratic programming problems (BQPs). Then, 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 convex BQPs [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. If the objective function is bounded, every method fitting in the framework converges to a stationary point thanks to a suitable application of the GP method in the identification phase. For strictly convex problems, finite convergence is proved even in the case of degeneracy of the solution. Numerical experiments show that practical algorithms in this framework are competitive with reference algorithms for the solution of synthetic and real-life problems subject to bounds only or to bounds and a single linear constraint.

indietro