A two-phase gradient method for quadratic programming problems with a single linear constraint and bounds on the variables
Preprint
Abstract
We propose a gradient-based method for quadratic programming problems with a single linear constraint and bounds on the variables. Inspired by the GPCG algorithm for bound-constrained convex quadratic programming [J.J. Mor\'e and G. Toraldo, SIAM J. Optim. 1, 1991], 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, by applying either the conjugate gradient method or a recently proposed spectral gradient method. However, the algorithm 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. This 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 proportioning, which was proposed by some authors for box-constrained problems. If the objective function is bounded, the algorithm converges to a stationary point thanks to a suitable application of the gradient projection method in the identification phase. For strictly convex problems, the algorithm converges to the optimal solution in a finite number of steps even in case of degeneracy. Extensive numerical experiments show the effectiveness of the proposed approach.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- On the regularizing behavior of the SDA and SDC gradient methods in the solution of linear ill-posed problemsJournal of Computational and Applied Mathematics, 2016
- Optimal $L_2$-norm empirical importance weights for the change of probability measureStatistics and Computing, 2016
- Minimizing quadratic functions with semidefinite Hessian subject to bound constraintsComputers & Mathematics with Applications, 2015
- An efficient gradient method using the Yuan steplengthComputational Optimization and Applications, 2014
- Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programmingNumerische Mathematik, 2005
- Benchmarking optimization software with performance profilesMathematical Programming, 2002
- Algorithms for bound constrained quadratic programming problemsNumerische Mathematik, 1989
- On the numerical solution of bound constrained optimization problemsRAIRO - Operations Research, 1989
- Projected gradient methods for linearly constrained problemsMathematical Programming, 1987
- Multipoint methods for separable nonlinear networks1984