The Efficiency of Ballstep Subgradient Level Methods for Convex Optimization
- 1 February 1999
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 24 (1) , 237-254
- https://doi.org/10.1287/moor.24.1.237
Abstract
We study subgradient methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. We establish convergence and efficiency estimates for simple ballstep level controls without requiring that the feasible set be compact. Our framework may handle accelerations based on “cheap” projections, surrogate constraints, and conjugate subgradient techniques.Keywords
This publication has 29 references indexed in Scilit:
- Estimating the Held-Karp lower bound for the geometric TSPEuropean Journal of Operational Research, 1997
- Finding normal solutions in piecewise linear programmingApplied Mathematics & Optimization, 1995
- A descent proximal level bundle method for convex nondifferentiable optimizationOperations Research Letters, 1995
- Block-iterative surrogate projection methods for convex feasibility problemsLinear Algebra and its Applications, 1995
- Projection onto an acute cone and convex feasibility problemPublished by Springer Nature ,1994
- An improved subgradient method for constrained nondifferentiable optimizationOperations Research Letters, 1993
- A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxationEuropean Journal of Operational Research, 1982
- On the choice of step size in subgradient optimizationEuropean Journal of Operational Research, 1981
- On improving relaxation methods by modified gradient techniquesPublished by Springer Nature ,1975
- The Relaxation Method for Linear InequalitiesCanadian Journal of Mathematics, 1954