On the Identification Property of a Projected Gradient Method
Authors:
- P. L. De AngelisPAP. L. De Angelis
- G. ToraldoGTG. Toraldo
- 1 October 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Numerical Analysis
- Vol. 30 (5) , 1483-1497
Abstract
The authors study the convergence properties of a projected gradient algorithm for the general problem \[\min \{ f(x):x \in \Omega \} ,\] where $f:R^n \to R$ is a mapping continuously differentiable on a closed convex set $\Omega \subseteq R^n $. The algorithm, which requires only one projection per iteration, is a special version of the method of projection of the gradient by Demyanov and Rubinov [Approximate Methods in Optimization Problems, Elsevier, New York, 1970] where the step choice is made according to a scheme similar to the one used by Calamai and Moré [Math. Programming, 39 (1987), pp. 93–116]. The authors are mainly interested in analysing the identification property of the algorithm for the case where the set $\Omega $ is a polyhedron, that is, the ability to identify in a finite number of steps the face in which the final solution lies. The convergence results that are shown are very similar to those shown in [6] for the standard projected gradient method.
Keywords
This publication has 18 references indexed in Scilit:
- Global Convergence of a Class of Trust Region Algorithms for Optimization Using Inexact Projections on Convex ConstraintsSIAM Journal on Optimization, 1993
- Convergence properties of trust region methods for linear and convex constraintsMathematical Programming, 1990
- On the Identification of Active ConstraintsSIAM Journal on Numerical Analysis, 1988
- Global Convergence of a Class of Trust Region Algorithms for Optimization with Simple BoundsSIAM Journal on Numerical Analysis, 1988
- Testing a class of methods for solving minimization problems with simple bounds on the variablesMathematics of Computation, 1988
- Quasi-Newton Updates with BoundsSIAM Journal on Numerical Analysis, 1987
- Projected gradient methods for linearly constrained problemsMathematical Programming, 1987
- An O(n) algorithm for quadratic knapsack problemsOperations Research Letters, 1984
- Projected Newton Methods for Optimization Problems with Simple ConstraintsSIAM Journal on Control and Optimization, 1982
- Global and Asymptotic Convergence Rate Estimates for a Class of Projected Gradient ProcessesSIAM Journal on Control and Optimization, 1981