Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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.


References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

American Mathematical Society