The numerical solution of equality constrained quadratic programming problems

Authors:
Nira Dyn and Warren E. Ferguson

Journal:
Math. Comp. **41** (1983), 165-170

MSC:
Primary 90C20

DOI:
https://doi.org/10.1090/S0025-5718-1983-0701631-X

MathSciNet review:
701631

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper proves that a large class of iterative schemes can be used to solve a certain constrained minimization problem. The constrained minimization problem considered involves the minimization of a quadratic functional subject to linear equality constraints. Among this class of convergent iterative schemes are generalizations of the relaxed Jacobi, Gauss-Seidel, and symmetric Gauss-Seidel schemes.

**[1]**Richard W. Cottle, Gene H. Golub, and Richard S. Sacher,*On the solution of large, structured linear complementarity problems: the block partitioned case*, Appl. Math. Optim.**4**(1977/78), no. 4, 347–364. MR**512218**, https://doi.org/10.1007/BF01442149**[2]**R. W. Cottle and J. S. Pang,*On the convergence of a block successive overrelaxation method for a class of linear complementarity problems*, Math. Programming Stud.**17**(1982), 126–138. Nondifferential and variational techniques in optimization (Lexington, Ky., 1980). MR**654696****[3]**R. W. Cottle,*Application of a Block Successive Over-Relaxation Method to a Class of Constrained Matrix Problems*, Tech. Report SOL 81-20, Stanford University, November 1981.**[4]**N. Dyn & W. Ferguson,*Numerical Construction of Smooth Surfaces from Aggregated Data*, University of Wisconsin--Madison, Math. Res. Center, TSR #2129, October 1980.**[5]**Nira Dyn and Grace Wahba,*On the estimation of functions of several variables from aggregated data*, SIAM J. Math. Anal.**13**(1982), no. 1, 134–152. MR**641546**, https://doi.org/10.1137/0513010**[6]***Numerical methods for constrained optimization*, Academic Press, London-New York, 1974. Edited by P. E. Gill and W. Murray. MR**0395227****[7]**G. Hadley,*Nonlinear and dynamic programming*, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1964. MR**0173543****[8]**David G. Luenberger,*Hyperbolic pairs in the method of conjugate gradients*, SIAM J. Appl. Math.**17**(1969), 1263–1267. MR**0260153**, https://doi.org/10.1137/0117118**[9]**O. L. Mangasarian,*Solution of symmetric linear complementarity problems by iterative methods*, J. Optimization Theory Appl.**22**(1977), no. 4, 465–485. MR**0458831**, https://doi.org/10.1007/BF01268170**[10]**C. C. Paige and M. A. Saunders,*Solutions of sparse indefinite systems of linear equations*, SIAM J. Numer. Anal.**12**(1975), no. 4, 617–629. MR**0383715**, https://doi.org/10.1137/0712047**[11]**G. W. Stewart,*Introduction to matrix computations*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Computer Science and Applied Mathematics. MR**0458818****[12]**Waldo R. Tobler,*Smooth pycnophylactic interpolation for geographical regions*, J. Amer. Statist. Assoc.**74**(1979), no. 367, 519–536. With a comment by Nira Dyn [Nira Richter-Dyn], Grace Wahba and Wing Hung Wong and a rejoinder by the author. MR**548256****[13]**Burton Wendroff,*Theoretical numerical analysis*, Academic Press, New York-London, 1966. MR**0196896****[14]**David M. Young,*Iterative solution of large linear systems*, Academic Press, New York-London, 1971. MR**0305568**

Retrieve articles in *Mathematics of Computation*
with MSC:
90C20

Retrieve articles in all journals with MSC: 90C20

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1983-0701631-X

Keywords:
Constrained minimization,
quadratic programming,
iterative schemes,
indefinite systems of equations

Article copyright:
© Copyright 1983
American Mathematical Society