The Efficiency of Ballstep Subgradient Level Methods for Convex Optimization

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.