article

Numerically stable methods for quadratic programming

Authors:

Philip E. Gill,

Walter MurrayAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 14, Issue 1

Pages 349 - 372

https://doi.org/10.1007/BF01588976

Published: 01 December 1978 Publication History

Abstract

Numerically stable algorithms for quadratic programming are discussed. A new algorithm is described for indefinite quadratic programming which utilizes methods for updating positivedefinite factorizations only. Consequently all the updating procedures required are common to algorithms for linearly-constrained optimization. The new algorithm can be used for the positive-definite case without loss of efficiency.

References

[1]

P. Businger and G.H. Golub, "Linear least squares solutions by Householder transformations", Numerische Mathematik 7 (1965) 269-276.

Digital Library

[2]

A.R. Conn, "Constrained optimization using a non-differentiable penalty function", SIAM Journal of the Numerical Analysis 10 (1973) 760-784.

[3]

A.R. Conn and J.W. Sinclair, "Quadratic programming via a non-differentiable penalty function", Department of Combinations and Optimization Research, University of Waterloo, Rep. CORR 75-15 (1975).

[4]

R. Fletcher, "The calculation of feasible points for linearly constrained optimization problems", UKAEA Research Group Rept., AERE R6354 (1970).

[5]

R. Fletcher and M.P. Jackson, "Minimization of a quadratic function of many variables subject only to lower and upper bounds", Journal of the Institute of Mathematics and its Applications 14 (1974) 159-174.

[6]

P.E. Gill, "Numerical methods for large-scale linearly-constrained optimization problems", Ph.D. thesis, Imperial College of Science and Technology, London University (1975).

[7]

P.E. Gill and W. Murray, "Quasi-Newton methods for linearly-constrained optimization", in: P.E. Gill and W. Murray, eds., Numerical methods for constrained optimization (Academic Press, London, 1974) pp. 67-92.

[8]

P.E. Gill and W. Murray, "Newton-type methods for linearly-constrained optimization", in: P.E. Gill and W. Murray, eds., Numerical methods for constrained optimization (Academic Press, London, 1974) pp. 29-66.

[9]

P.E. Gill and W. Murray, "Newton-type methods for unconstrained and linearly-constrained optimization", Mathematical Programming 7 (1974) 311-350.

Digital Library

[10]

P.E. Gill and W. Murray, "Minimization of a nonlinear function subject to bounds on the variables", NPL NAC Rep. No. 72 (1976).

[11]

P.E. Gill and W. Murray, "The computation of Lagrange-multiplier estimates for constrained minimization", NPL NAC Rep. No. 77 (1977).

[12]

P.E. Gill and W. Murray, "Linearly-constrained problems including linear and quadratic programming", in: D. Jacobs, ed., A survey of numerical analysis--1976, (Academic Press, London, 1977).

[13]

P.E. Gill, G.H. Golub, W. Murray and M.A. Saunders, "Methods for modifying matrix factorizations", Mathematics of Computation 28 (1974) 505-535.

[14]

C.L. Lawson and R.J. Hanson, Solving least-squares problems (Prentice Hall, Englewood Cliffs, N J, 1974).

[15]

W. Murray, "An algorithm for finding a local minimum of an indefinite quadratic program", NPL NAC Rep. No. 1 (1971).

[16]

J.H. Wilkinson, The algebraic eigenvalue problem (Oxford University Press, London, 1965).

Cited By

Rontsis NGoulart PNakatsukasa Y(2022)An active-set algorithm for norm constrained quadratic problemsMathematical Programming: Series A and B10.1007/s10107-021-01617-2193:1(447-483)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s10107-021-01617-2
Forsgren AGill PWong E(2016)Primal and dual active-set methods for convex quadratic programmingMathematical Programming: Series A and B10.1007/s10107-015-0966-2159:1-2(469-508)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10107-015-0966-2
Wang CYan X(2015)Parallel multisplitting methods with optimal weighting matrices for linear systemsApplied Mathematics and Computation10.1016/j.amc.2015.03.025259:C(523-532)Online publication date: 15-May-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.03.025
Show More Cited By

Numerically stable methods for quadratic programming

Recommendations

A numerically stable dual method for solving strictly convex quadratic programs

An efficient and numerically stable dual algorithm for positive definite quadratic programming is described which takes advantage of the fact that the unconstrained minimum of the objective function can be used as a starting point. Its implementation ...
A clique algorithm for standard quadratic programming

A standard Quadratic Programming problem (StQP) consists in minimizing a (nonconvex) quadratic form over the standard simplex. For solving a StQP we present an exact and a heuristic algorithm, that are based on new theoretical results for quadratic and ...
An algorithm for indefinite quadratic programming with convex constraints

We propose a branch-and-bound method for minimizing an indefinite quadratic function over a convex set. The bounding operation is based on a certain relaxation of the constraints. The branching is a simplex bisection.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 14, Issue 1

December 1978

380 pages

ISSN:0025-5610

Issue’s Table of Contents

Copyright © Copyright © 1978 The Mathematical Programming Society.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 December 1978

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rontsis NGoulart PNakatsukasa Y(2022)An active-set algorithm for norm constrained quadratic problemsMathematical Programming: Series A and B10.1007/s10107-021-01617-2193:1(447-483)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s10107-021-01617-2
Forsgren AGill PWong E(2016)Primal and dual active-set methods for convex quadratic programmingMathematical Programming: Series A and B10.1007/s10107-015-0966-2159:1-2(469-508)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10107-015-0966-2
Wang CYan X(2015)Parallel multisplitting methods with optimal weighting matrices for linear systemsApplied Mathematics and Computation10.1016/j.amc.2015.03.025259:C(523-532)Online publication date: 15-May-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.03.025
Achtziger WStolpe M(2008)Global optimization of truss topology with discrete bar areas--Part IComputational Optimization and Applications10.1007/s10589-007-9138-540:2(247-280)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1007/s10589-007-9138-5
Qi LYang Y(2001)A Globally and Superlinearly Convergent SQP Algorithm for Nonlinear Constrained OptimizationJournal of Global Optimization10.1023/A:101198313055921:2(157-184)Online publication date: 1-Oct-2001
https://dl.acm.org/doi/10.1023/A%3A1011983130559
He BStoer J(1992)Solution of projection problems over polytopesNumerische Mathematik10.1007/BF0138549861:1(73-90)Online publication date: 1-Dec-1992
https://dl.acm.org/doi/10.1007/BF01385498
Coleman THulbert L(1989)A direct active set algorithm for large sparse quadratic programs with simple boundsMathematical Programming: Series A and B10.5555/3112655.311287345:1-3(373-406)Online publication date: 1-Aug-1989
https://dl.acm.org/doi/10.5555/3112655.3112873
Gill PMurray WSaunders MWright M(1989)A practical anti-cycling procedure for linearly constrained optimizationMathematical Programming: Series A and B10.5555/3112655.311285545:1-3(437-474)Online publication date: 1-Aug-1989
https://dl.acm.org/doi/10.5555/3112655.3112855
Ruszczyński A(1986)A regularized decomposition method for minimizing a sum of polyhedral functionsMathematical Programming: Series A and B10.5555/3226657.322696535:3(309-333)Online publication date: 1-Jul-1986
https://dl.acm.org/doi/10.5555/3226657.3226965
Womersley RFletcher R(1986)An algorithm for composite nonsmooth optimization problemsJournal of Optimization Theory and Applications10.5555/3182698.318329148:3(493-523)Online publication date: 1-Mar-1986
https://dl.acm.org/doi/10.5555/3182698.3183291
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents