zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Projected gradient methods for linearly constrained problems. (English) Zbl 0634.90064
Summary: The aim of this paper is to study the convergence properties of the gradient projection method and to apply these results to algorithms for linearly constrained problems. The main convergence result is obtained by defining a projected gradient, and proving that the gradient projection method forces the sequence of projected gradients to zero. A consequence of this result is that if the gradient projection method converges to a nondegenerate point of a linearly constrained problem, then the active and binding constraints are identified in a finite number of iterations. As an application of our theory, we develop quadratic programming algorithms that iteratively explore a subspace defined by the active constraints. These algorithms are able to drop and add many constraints from the active set, and can either compute an accurate minimizer by a direct method, or an approximate minimizer by an iterative method of the conjugate gradient type. Thus, these algorithms are attractive for large scale problems. We show that it is possible to develop a finite terminating quadratic programming algorithm without non-degeneracy assumptions.

MSC:
90C30Nonlinear programming
90C20Quadratic programming
65K05Mathematical programming (numerical methods)
90C52Methods of reduced gradient type
49M37Methods of nonlinear programming type in calculus of variations
References:
[1]P. Bertsekas, ”On the Goldstein-Levitin-Polyak gradient projection method,”IEEE Transactions on Automatic Control 21 (1976) 174–184. · Zbl 0326.49025 · doi:10.1109/TAC.1976.1101194
[2]D.P. Bertsekas, ”Projected Newton methods for optimization problems with simple constraints,”SIAM Journal on Control and Optimization 20 (1982) 221–246. · Zbl 0507.49018 · doi:10.1137/0320018
[3]J.V. Burke and J.J. Moré, ”On the identification of active constraints,” Argonne National Laboratory, Mathematics and Computer Science Division Report ANL/MCS-TM-82, (Argonne, IL, 1986).
[4]R.S. Dembo and U. Tulowitzki, ”On the minimization of quadratic functions subject to box constraints,” Working Paper Series B#71, School of Organization and Management, Yale University, (New Haven, CT, 1983).
[5]R.S. Dembo and U. Tulowitzki, ”Local convergence analysis for successive inexact quadratic programming methods,” Working Paper Series B#78, School of Organization and Management, Yale University, (New Haven, CT, 1984).
[6]R.S. Dembo and U. Tulowitzki, ”Sequential truncated quadratic programming methods,”, in: P.T. Boggs, R.H. Byrd and R.B. Schnabel, eds.,Numerical Optimization 1984 (Society of Industrial and Applied Mathematics, Philadelphia, 1985) pp. 83–101.
[7]J.C. Dunn, ”Global and asymptotic convergence rate estimates for a class of projected gradient processes,”SIAM Journal on Control and Optimization 19 (1981), 368–400. · Zbl 0488.49015 · doi:10.1137/0319022
[8]J.C. Dunn, ”On the convergence of projected gradient processes to singular critical points,”Journal of Optimization Theory and Applications (1986) to appear.
[9]R. Fletcher,Practical Methods of Optimization Volume 2: Constrained Optimization (John Wiley & Sons, New York, 1981).
[10]E.M. Gafni and D.P. Bertsekas, ”Convergence of a gradient projection method,” Massachusetts Institute of Technology, Laboratory for Information and Decision Systems Report LIDS-P-1201 (Cambridge, Massachusetts, 1982).
[11]E.M. Gafni and D.P. Bertsekas, ”Two-metric projection methods for constrained optimization,”SIAM Journal on Control and Optimization 22 (1984) 936–964. · Zbl 0555.90086 · doi:10.1137/0322061
[12]P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, New York, 1981).
[13]A.A. Goldstein, ”Convex programming in Hilbert space,”Bulletin of the American Mathematical Society 70 (1964) 709–710. · Zbl 0142.17101 · doi:10.1090/S0002-9904-1964-11178-2
[14]E.S. Levitin and B.T. Polyak, ”Constrained minimization problems”,USSR Computational Mathematics and Mathematical Physics 6 (1966), 1–50. · doi:10.1016/0041-5553(66)90114-5
[15]G.P. McCormick and R.A. Tapia, ”The gradient projection method under mild differentiability conditions,”SIAM Journal on Control 10 (1972) 93–98. · Zbl 0237.49019 · doi:10.1137/0310009
[16]D.P. O’Leary, ”A generalized conjugate gradient algorithm for solving a class of quadratic programming problems,”Linear Algebra and its Applications 34 (1980) 371–399. · Zbl 0464.65039 · doi:10.1016/0024-3795(80)90173-1
[17]R.R. Phelps ”The gradient projection method using Curry’s steplength,”SIAM Journal on Control and Optimization 24 (1986) 692–699. · Zbl 0603.90117 · doi:10.1137/0324042
[18]B.T. Polyak, ”The conjugate gradient method in extremal problems,”USSR Computational Mathematics and Mathematical Physics 9 (1969) 94–112. · Zbl 0229.49023 · doi:10.1016/0041-5553(69)90035-4
[19]E.H. Zarantonello, ”Projections on convex sets in Hilbert space and spectral theory,” in: E.H. Zarantonello, ed.,Contributions to Nonlinear Functional Analysis (Academic Press, New York, 1971).