Viola, Marco, Di Serafino, Daniela, Toraldo, Gerardo and Barlow, Jesse (2018) A two-phase gradient method for quadratic programming problems with a single linear constraint and bounds on the variables. SIAM Journal on Optimization, 28 (4). pp. 2809-2838. ISSN 1095-7189
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´e 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 and a measure of bindingness of the variables that are on the bounds, defined by extending the concept of proportional iterate, 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 the case of degeneracy. Extensive numerical experiments show the effectiveness of the proposed approach
Metadata
| Item Type: | Article (Published) |
|---|---|
| Refereed: | Yes |
| Uncontrolled Keywords: | Quadratic programming, bound and single linear constraints, gradient projection, proportionality |
| Subjects: | Mathematics Mathematics > Mathematical analysis |
| DCU Faculties and Centres: | DCU Faculties and Schools > Faculty of Science and Health DCU Faculties and Schools > Faculty of Science and Health > School of Mathematical Sciences |
| Publisher: | Society for Industrial and Applied Mathematics |
| Official URL: | https://epubs.siam.org/doi/10.1137/17M1128538 |
| Copyright Information: | Authors |
| ID Code: | 31189 |
| Deposited On: | 11 Jul 2025 14:43 by Vidatum Academic . Last Modified 11 Jul 2025 14:43 |
Documents
Full text available as:
Preview |
PDF
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Creative Commons: Attribution 4.0 707kB |
Metrics
Altmetric Badge
Dimensions Badge
Downloads
Downloads
Downloads per month over past year
Archive Staff Only: edit this record