THE EFFICIENCY OF SUBGRADIENT PROJECTION METHODS FOR CONVEX-OPTIMIZATION .1. GENERAL LEVEL METHODS

We study subgradient methods for convex optimization that use projecti ons onto successive approximations of level sets of the objective corr esponding to estimates of the optimal value. We present several varian ts and show that they enjoy almost optimal efficiency estimates. In an other paper we discuss possible implementations of such methods. In pa rticular, their projection subproblems may he solved inexactly via rel axation methods, thus opening the way for parallel implementations. Th ey can also exploit accelerations of relaxation methods based on simul taneous projections, surrogate constraints, and conjugate and projecte d (conditional) subgradient techniques.