A Two-Phase Gradient Method for Quadratic Programming Problems with a Single Linear Constraint and Bounds on the Variables
Authors:
- Daniela di SerafinoDSDaniela di Serafino
- Gerardo ToraldoGTGerardo Toraldo
- Marco ViolaMVMarco Viola
- Jesse BarlowJBJesse Barlow
- 1 January 2018
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 28 (4) , 2809-2838
Abstract
We propose a gradient-based method for quadratic programming problems with a single linear constraint and bounds on the variables. 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, 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 an...Keywords
All Related Versions
Funding Information
- Gruppo Nazionale per l'Analisi Matematica, la Probabilità e le loro Applicazioni
This publication has 32 references indexed in Scilit:
- An Affine-Scaling Interior-Point Method for Continuous Knapsack Constraints with Application to Support Vector MachinesSIAM Journal on Optimization, 2011
- A scaled gradient projection method for constrained image deblurringInverse Problems, 2008
- New adaptive stepsize selections in gradient methodsJournal of Industrial and Management Optimization, 2008
- A New Active Set Algorithm for Box Constrained OptimizationSIAM Journal on Optimization, 2006
- Benchmarking optimization software with performance profilesMathematical Programming, 2002
- Nonmonotone Spectral Projected Gradient Methods on Convex SetsSIAM Journal on Optimization, 2000
- On the Maximization of a Concave Quadratic Function with Box ConstraintsSIAM Journal on Optimization, 1994
- On the Identification Property of a Projected Gradient MethodSIAM Journal on Numerical Analysis, 1993
- Algorithms for bound constrained quadratic programming problemsNumerische Mathematik, 1989
- Quasi-Newton Updates with BoundsSIAM Journal on Numerical Analysis, 1987