The numerical solution of equality constrained quadratic programming problems
Authors:
Nira Dyn and Warren E. Ferguson
Journal:
Math. Comp. 41 (1983), 165170
MSC:
Primary 90C20
MathSciNet review:
701631
Fulltext 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, GaussSeidel, and symmetric GaussSeidel 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
(80a:90120), http://dx.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 (83d:90217)
 [3]
R. W. Cottle, Application of a Block Successive OverRelaxation Method to a Class of Constrained Matrix Problems, Tech. Report SOL 8120, Stanford University, November 1981.
 [4]
N. Dyn & W. Ferguson, Numerical Construction of Smooth Surfaces from Aggregated Data, University of WisconsinMadison, 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
(83a:65014), http://dx.doi.org/10.1137/0513010
 [6]
Numerical methods for constrained optimization, Academic Press,
LondonNew York, 1974. Edited by P. E. Gill and W. Murray. MR 0395227
(52 #16025)
 [7]
G.
Hadley, Nonlinear and dynamic programming, AddisonWesley
Publishing Co., Inc., Reading, Mass.London, 1964. MR 0173543
(30 #3756)
 [8]
David
G. Luenberger, Hyperbolic pairs in the method of conjugate
gradients, SIAM J. Appl. Math. 17 (1969),
1263–1267. MR 0260153
(41 #4781)
 [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
(56 #17031)
 [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
(52 #4595)
 [11]
G.
W. Stewart, Introduction to matrix computations, Academic
Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New
YorkLondon, 1973. Computer Science and Applied Mathematics. MR 0458818
(56 #17018)
 [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 RichterDyn],
Grace Wahba and Wing Hung Wong and a rejoinder by the author. MR 548256
(82b:62147)
 [13]
Burton
Wendroff, Theoretical numerical analysis, Academic Press, New
YorkLondon, 1966. MR 0196896
(33 #5080)
 [14]
David
M. Young, Iterative solution of large linear systems, Academic
Press, New YorkLondon, 1971. MR 0305568
(46 #4698)
 [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. 347363. 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 OverRelaxation Method to a Class of Constrained Matrix Problems, Tech. Report SOL 8120, Stanford University, November 1981.
 [4]
 N. Dyn & W. Ferguson, Numerical Construction of Smooth Surfaces from Aggregated Data, University of WisconsinMadison, 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 WisconsinMadison, 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, AddisonWesley, 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. 12631267; "The conjugate residual method for constrained minimization problems," SIAM J. Numer. Anal., v. 7, 1970, pp. 390398. 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. 465485; SparsityPreserving SOR Algorithms for Separable Quadratic and Linear Programming, University of WisconsinMadison, 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. 617629. 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. 519530. 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:
http://dx.doi.org/10.1090/S0025571819830701631X
PII:
S 00255718(1983)0701631X
Keywords:
Constrained minimization,
quadratic programming,
iterative schemes,
indefinite systems of equations
Article copyright:
© Copyright 1983
American Mathematical Society
