  A new decomposition optimization algorithm, called \textit{path-following
gradient-based decomposition}, is proposed to solve separable convex
optimization problems. Unlike path-following Newton methods considered in the
literature, this algorithm does not requires any smoothness assumption on the
objective function. This allows us to handle more general classes of problems
arising in many real applications than in the path-following Newton methods.
The new algorithm is a combination of three techniques, namely smoothing,
Lagrangian decomposition and path-following gradient framework. The algorithm
decomposes the original problem into smaller subproblems by using dual
decomposition and smoothing via self-concordant barriers, updates the dual
variables using a path-following gradient method and allows one to solve the
subproblem in parallel. Moreover, the algorithmic parameters are updated
automatically without any tuning strategy as in augmented Lagrangian
approaches. We prove the global convergence of the new algorithm and analyze
its local convergence rate. Then, we modify the proposed algorithm by applying
Nesterov's accelerating scheme to get a new variant which has a better local
convergence rate. Finally, we present preliminary numerical tests that confirm
the theory development.
