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]**R. W. Cottle, G. H. Golub & R. S. Sacher, "On the solution of large, structured linear complementarity problems: The block tridiagonal case,"*Appl. Math. Optim.*, v. 4, 1978, pp. 347-363. MR**512218 (80a:90120)****[2]**R. W. Cottle & J. S. Pang, "On the convergence of a block successive overrelaxation method for a class of linear complementarity problems,"*Math. Prog. Studies*. (To appear.) MR**654696 (83d:90217)****[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]**N. Dyn & G. Wahba,*On the Estimation of Functions of Several Variables from Aggregated Data*, University of Wisconsin--Madison, Math. Res. Center, TSR #1974, July 1979;*SIAM J. Math. Anal.*(To appear.) MR**641546 (83a:65014)****[6]**P. E. Gill & W. Murray,*Numerical Methods for Constrained Optimization*, Academic Press, New York, 1974. MR**0395227 (52:16025)****[7]**G. Hadley,*Nonlinear and Dynamic Programming*, Addison-Wesley, Reading, Mass., 1964. MR**0173543 (30:3756)****[8]**D. G. Luenberger, "Hyperbolic pairs in the method of conjugate gradients,"*SIAM J. Appl. Math.*, v. 17, 1969, pp. 1263-1267; "The conjugate residual method for constrained minimization problems,"*SIAM J. Numer. Anal.*, v. 7, 1970, pp. 390-398. MR**0260153 (41:4781)****[9]**O. L. Mangasarian, "Solution of symmetric linear complementarity problems by iterative methods,"*J. Optim. Theory Appl.*, v. 22, 1977, pp. 465-485;*Sparsity-Preserving SOR Algorithms for Separable Quadratic and Linear Programming*, University of Wisconsin-Madison, Math. Res. Center, TSR #2260, August 1981. MR**0458831 (56:17031)****[10]**C. C. Paige & M. A. Saunders, "Solution of sparse indefinite systems of equations,"*SIAM J. Numer. Anal.*, v. 12, 1975, pp. 617-629. MR**0383715 (52:4595)****[11]**G. W. Stewart,*Introduction to Matrix Computations*, Academic Press, New York, 1973. MR**0458818 (56:17018)****[12]**W. Tobler, "Smooth pycnophylactic interpolation for geographical regions,"*J. Amer. Statist. Assoc.*, v. 74, 1979, pp. 519-530. MR**548256 (82b:62147)****[13]**B. Wendroff,*Theoretical Numerical Analysis*, Academic Press, New York, 1966. MR**0196896 (33:5080)****[14]**D. M. Young,*Iterative Solution of Large Linear Systems*, Academic Press, New York, 1971. MR**0305568 (46:4698)**

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