Fast inexact decomposition algorithms for large-scale separable convex optimization

Abstract

In this paper, we propose a new inexact dual decomposition algorithm for solving separable convex optimization problems. This algorithm is a combination of three techniques: dual Lagrangian decomposition, smoothing and excessive gap. The algorithm has low computational complexity since it consists in only one primal step and two dual steps at each iteration and allows one to solve the subproblem of each component inexactly and in parallel. Moreover, the algorithmic parameters are updated automatically without any tuning strategy as it happens in augmented Lagrangian approaches. We analyse the convergence of the algorithm and estimate its analytical worst-case complexity for both the primal–dual suboptimality and the primal feasibility violation, where is a given accuracy. Extensive numerical tests confirm that our method is numerically more efficient than the classical decomposition methods from the literature.

Keywords:

• primal–dual algorithm
• smoothing technique
• excessive gap
• Lagrangian decomposition
• distributed and parallel algorithm
• separable convex optimization

AMS Subject Classifications:

• 90C06
• 90C25
• 90-08

Acknowledgements

We thank the editor and two anonymous reviewers for their comments and suggestions to improve the presentation of the paper. This paper was completed when the first author was with the Department of Electrical Engineering (ESAT) and Optimization in Engineering Center (OPTEC), KU Leuven, Belgium.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by CoE EF/05/006-Optimization in Engineering (OPTEC); EMBOCON; ERC-HIGHWIND; IOF-SCORES4CHEM; GOA/10/009 (MaNet); GOA /10/11 and several PhD/postdoc and fellow grants; CNCS-UEFISCDI; ANCS; Sectoral Operational Programme Human Resources Development 2007–2013 of the Romanian Ministry of Labor; Family and Social Protection through the Financial Agreement POSDRU/89/1.5/S/62557 and POSDRU/107/1.5/S/76909; Nafosted (101.01-2014-24) (Vietnam).