Coupled-decompositions: exploiting primal–dual interactions in convex optimization problems

© 2013, Morell et al.; licensee Springer. Abstract: Decomposition techniques implement the so-called “divide and conquer” in convex optimization problems, being primal and dual decompositions the two classical approaches. Although both solutions achieve the goal of splitting the original program into several smaller problems (called the subproblems), these techniques exhibit in general slow speed of convergence. This is a limiting factor in practice and in order to circumvent this drawback, we develop in this article the coupled-decompositions method. As a result, the number of iterations can be reduced by more than one order of magnitude. Furthermore, the new technique is self-adjustable, i.e., it does not depend on user-defined parameters, as opposite to what happens with classical strategies. Given that in signal processing applied to communications and networking we usually deal with a variety of problems that exhibit certain coupling structures, our method is useful to design decentralized as well as centralized optimization schemes with advantages over the existing techniques in the literature. In this article, we expose there different resource allocation problems where the proposed method is successfully applied.