Login (DCU Staff Only)
Login (DCU Staff Only)

DORAS | DCU Research Repository

Explore open access research and scholarly works from DCU

Advanced Search

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

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:

[thumbnail of Viola_SIOPT2018.pdf]
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