Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0634.90064
Calamai, Paul H.; Moré, Jorge J.
Projected gradient methods for linearly constrained problems. (English)
[J] Math. Program. 39, 93-116 (1987). ISSN 0025-5610; ISSN 1436-4646/e

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 2000:: *90C30 Nonlinear programming
90C20 Quadratic programming
65K05 Mathematical programming (numerical methods)
90C52 Methods of reduced gradient type
49M37 Methods of nonlinear programming type

Keywords: bound constrained problems; convergence theory; gradient projection method; linearly constrained problems; large scale problems

Cited in: Zbl 1130.90415 Zbl 0963.90058

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]