  In this paper we provide a detailed analysis of the iteration complexity of
dual first order methods for solving conic convex problems. When it is
difficult to project on the primal feasible set described by convex
constraints, we use the Lagrangian relaxation to handle the complicated
constraints and then, we apply dual first order algorithms for solving the
corresponding dual problem. We give convergence analysis for dual first order
algorithms (dual gradient and fast gradient algorithms): we provide sublinear
or linear estimates on the primal suboptimality and feasibility violation of
the generated approximate primal solutions. Our analysis relies on the
Lipschitz property of the gradient of the dual function or an error bound
property of the dual. Furthermore, the iteration complexity analysis is based
on two types of approximate primal solutions: the last primal iterate or an
average primal sequence.
