  In this paper, we suggest a new framework for analyzing primal subgradient
methods for nonsmooth convex optimization problems. We show that the classical
step-size rules, based on normalization of subgradient, or on the knowledge of
optimal value of the objective function, need corrections when they are applied
to optimization problems with constraints. Their proper modifications allow a
significant acceleration of these schemes when the objective function has
favorable properties (smoothness, strong convexity). We show how the new
methods can be used for solving optimization problems with functional
constraints with possibility to approximate the optimal Lagrange multipliers.
One of our primal-dual methods works also for unbounded feasible set.
