  We study the computational complexity certification of inexact gradient
augmented Lagrangian methods for solving convex optimization problems with
complicated constraints. We solve the augmented Lagrangian dual problem that
arises from the relaxation of complicating constraints with gradient and fast
gradient methods based on inexact first order information. Moreover, since the
exact solution of the augmented Lagrangian primal problem is hard to compute in
practice, we solve this problem up to some given inner accuracy. We derive
relations between the inner and the outer accuracy of the primal and dual
problems and we give a full convergence rate analysis for both gradient and
fast gradient algorithms. We provide estimates on the primal and dual
suboptimality and on primal feasibility violation of the generated approximate
primal and dual solutions. Our analysis relies on the Lipschitz property of the
dual function and on inexact dual gradients. We also discuss implementation
aspects of the proposed algorithms on constrained model predictive control
problems for embedded linear systems.
