Abstract
Almost all efficient algorithms for constrained optimization require the repeated computation of Lagrange-multiplier estimates. In this paper we consider the difficulties in providing accurate estimates and what tests can be made in order to check the validity of the estimates obtained. A variety of formulae for the estimation of Lagrange multipliers are derived and their respective merits discussed. Finally the role of Lagrange multipliers within optimization algorithms is discussed and in addition to other results, it is shown that some algorithms are particularly sensitive to errors in the estimates.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
P. Businger and G.H. Golub, “Linear least squares solutions by Householder transformations”,Numerische Mathematik 7 (1965) 269–276.
R. Fletcher, “An ideal penalty function for constrained optimization”, AERE Rept. CSS2 (1973).
P.E. Gill, G.H. Golub, W. Murray and M.A. Saunders, “Methods for modifying matrix factorization”,Mathematics of Computation 28 (1974) 505–535.
P.E. Gill and W. Murray, “Quasi-Newton methods for linearly constrained optimization”, NPL NAC Rept. No. 32 (1973).
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.
P.E. Gill and W. Murray, “Safeguarded steplength algorithms for optimization using descent methods”, NPL NAC Rept. No. 37 (1974).
P.E. Gill and W. Murray “Numerically stable methods for quadratic programming”, NPL NAC Rept. No. 78 (1977).
S.M. Goldfeld, R.E. Quandt and H.F. Trotter, “Maximization by quadratic hill climbing”,Econometrica 34 (1966) 541–551.
K. Levenberg, “A method for the solution of certain problems in least squares”,Quarterly of Applied Mathematics 2 (1944) 164–168.
D. Marquardt, “An algorithm for least squares estimation for non-linear parameters”,SIAM Journal on Applied Mathematics 11 (1963) 431–441.
R.W.H. Sargent, “Reduced-gradient and projection methods for non-linear programming”, in: P.E. Gill and W. Murray, eds.,Numerical methods for constrained minimization (Academic Press, London, 1974) pp. 149–174.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gill, P.E., Murray, W. The computation of Lagrange-multiplier estimates for constrained minimization. Mathematical Programming 17, 32–60 (1979). https://doi.org/10.1007/BF01588224
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588224