THE EFFICIENCY OF SUBGRADIENT PROJECTION METHODS FOR CONVEX-OPTIMIZATION .2. IMPLEMENTATIONS AND EXTENSIONS

In the first part of this paper we studied subgradient methods for con vex optimization that use projections onto successive approximations o f level sets of the objective corresponding to estimates of the optima l value. We presented several variants and showed that they enjoy almo st optimal efficiency estimates. In this part of the paper we discuss possible implementations of such methods. In particular, their project ion subproblems may be solved inexactly via relaxation methods, thus o pening the way for parallel implementations. We discuss accelerations of relaxation methods based on simultaneous projections, surrogate con straints, and conjugate and projected (conditional) subgradient techni ques.