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:
| 90C30 | Nonlinear programming |
| 90C20 | Quadratic programming |
| 65K05 | Numerical mathematical programming methods |
| 90C52 | Methods of reduced gradient type |
| 49M37 | Numerical methods based on nonlinear programming |
Keywords:
bound constrained problems;convergence theory;gradient projection method;linearly constrained problems;large scale problemsCite
Full Text:DOI
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). ·Zbl 0662.65052 |
| [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. ·Zbl 0583.65042 |
| [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). ·Zbl 0474.65043 |
| [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). ·Zbl 0478.90071 |
| [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). ·Zbl 0503.90062 |
| [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. ·Zbl 0161.07002 ·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). ·Zbl 0281.47043 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
