Abstract
Range-space methods for convex quadratic programming improve in efficiency as the number of constraints active at the solution decreases. In this paper we describe a range-space method based upon updating a weighted Gram-Schmidt factorization of the constraints in the active set. The updating methods described are applicable to both primal and dual quadratic programming algorithms that use an active-set strategy.
Many quadratic programming problems include simple bounds on all the variables as well as general linear constraints. A feature of the proposed method is that it is able to exploit the structure of simple bound constraints. This allows the method to retain efficiency when the number ofgeneral constraints active at the solution is small. Furthermore, the efficiency of the method improves as the number of active bound constraints increases.
Similar content being viewed by others
References
R.H. Bartels, G.H. Golub and M.A. Saunders, “Numerical techniques in mathematical programming”, in: J.B. Rosen, Q.L. Mangasarian and K. Ritter, eds.,Nonlinear programming (Academic Press, London and New York, 1970) pp. 123–176.
J.R. Bunch and L.C. Kaufman, “A computational method for the indefinite quadratic programming problem”,Linear Algebra and its Applications 34 (1980) 341–370.
J.W. Daniel, W.B. Gragg, L.C. Kaufman and G.W. Stewart, “Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization”,Mathematics of Computation 30 (1976) 772–795.
A. Dax, “An active set algorithm for convex quadratic programming”, Technical Report, Hydrological Service (Jerusalem, Israel, 1981).
R. Fletcher, “A general quadratic programming algorithm”,Journal of the Institute of Mathematics and its Applications 7 (1971) 76–91.
P.E. Gill and W. Murray, “Numerically stable methods for quadratic programming”,Mathematical Programming 14 (1978) 349–372.
P.E. Gill, G.H. Golub, W. Murray and M.A. Saunders, “Methods for modifying matrix factorizations”,Mathematics of Computation 28 (1974) 505–535.
P.E. Gill, N.I.M. Gould, W. Murray, M.A. Saunders and M.H. Wright, “Range-space methods for convex quadratic programming”, Technical Report SOL 82-14, Department of Operations Research, Stanford University (Stanford, CA, 1982).
P.E. Gill, W. Murray and M.H. Wright,Practical optimization (Academic Press, London and New York, 1981).
D. Goldfarb, “Matrix factorizations in optimization of nonlinear functions subject to linear constraints”,Mathematical Programming 10 (1976) 1–31.
D. Goldfarb and A. Idnani, “A numerically stable dual method for solving strictly convex quadratic programs”,Mathematical Programming 27 (1983) 1–33.
W. Murray, “An algorithm for finding a local minimum of an indefinite quadratic program”, Report NAC 1, National Physical Laboratory (Teddington, England, 1971).
M.J.D. Powell, “An upper-triangular matrix method for quadratic programming”, in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear programming 4 (Academic Press, London and New York, 1981) pp. 1–24.
K. Schittkowski, “On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function”, Report SOL 82-4, Department of Operations Research, Stanford University (Stanford, CA, 1982).
Author information
Authors and Affiliations
Additional information
This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110. The work of Nicholas Gould was supported by the Science and Engineering Research Council of Great Britain.
Rights and permissions
About this article
Cite this article
Gill, P.E., Gould, N.I.M., Murray, W. et al. A weighted gram-schmidt method for convex quadratic programming. Mathematical Programming 30, 176–195 (1984). https://doi.org/10.1007/BF02591884
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591884