  In this paper we present complexity certification results for a distributed
Augmented Lagrangian (AL) algorithm used to solve convex optimization problems
involving globally coupled linear constraints. Our method relies on the
Accelerated Distributed Augmented Lagrangian (ADAL) algorithm, which can handle
the coupled linear constraints in a distributed manner based on local estimates
of the AL. We show that the theoretical complexity of ADAL to reach an
$\epsilon$-optimal solution both in terms of suboptimality and infeasibility is
$O(\frac{1}{\epsilon})$ iterations. Moreover, we provide a valid upper bound
for the optimal dual multiplier which enables us to explicitly specify these
complexity bounds. We also show how to choose the stepsize parameter to
minimize the bounds on the convergence rates. Finally, we discuss a motivating
example, a model predictive control (MPC) problem, involving a finite number of
subsystems which interact with each other via a general network.
