Error Bound and Reduced-Gradient Projection Algorithms for Convex Minimization over a Polyhedral Set
- 1 February 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 3 (1) , 43-59
- https://doi.org/10.1137/0803003
Abstract
Consider the problem of minimizing, over a polyhedral set, the composition of an afline mapping with a strongly convex differentiable function. The polyhedral set is expressed as the intersection of an affine set with a (simpler) polyhedral set and a new local error bound for this problem, based on projecting the reduced gradient associated with the affine set onto the simpler polyhedral set, is studied. A class of reduced-gradient projection algorithms for solving the case where the simpler polyhedral set is a box is proposed and this bound is used to show that algorithms in this class attain a linear rate of convergence. Included in this class are the gradient projection algorithm of Goldstein and Levitin and Poljak, and an algorithm of Bertsekas. A new algorithm in this class, reminiscent of active set algorithms, is also proposed. Some of the results presented here extend to problems where the objective function is extended real valued and to variational inequality problems.Keywords
This publication has 24 references indexed in Scilit:
- Variable metric gradient projection processes in convex feasible sets defined by nonlinear inequalitiesApplied Mathematics & Optimization, 1988
- On the convergence of projected gradient processes to singular critical pointsJournal of Optimization Theory and Applications, 1987
- Two-Metric Projection Methods for Constrained OptimizationSIAM Journal on Control and Optimization, 1984
- Projected Newton methods and optimization of multicommodity flowsIEEE Transactions on Automatic Control, 1983
- Projected Newton Methods for Optimization Problems with Simple ConstraintsSIAM Journal on Control and Optimization, 1982
- Projection methods for variational inequalities with application to the traffic assignment problemPublished by Springer Nature ,1982
- Global and Asymptotic Convergence Rate Estimates for a Class of Projected Gradient ProcessesSIAM Journal on Control and Optimization, 1981
- On the Goldstein-Levitin-Polyak gradient projection methodIEEE Transactions on Automatic Control, 1976
- Convex programming in Hilbert spaceBulletin of the American Mathematical Society, 1964
- On approximate solutions of systems of linear inequalitiesJournal of Research of the National Bureau of Standards, 1952