I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I understand, that dual decomposition methods often lead to more efficient algorithms.
After reading about decomposition methods on various sources (e.g. see these notes by Stephen Boyd), I don't get the intuition of why this would be the case.
Perhaps an important difference is that, as S. Boyd notes in his slides, in primal decomposition methods:
the master problem manipulates the primal (complicating) variables
while in the dual decomposition methods, this would not be the case. However, when S. Boyd describes the procedures for primal vs dual methods, the decomposition looks essentially the same:
repeat solve the subproblems (presumably on the slaves) update complicating variable (presumably on the master)
So my questions are:
- Is it true that dual decomposition methods tend to be more efficient in practice than primal methods? If so, why?
- Why does S. Boyd say that in primal decomposition methods, "the master problem manipulates the complicating variables" ? How is this different from the way these variables are handled in a dual decomposition?
Update: Additional background:
Statistical machine learning problems, such as MAP-MRF estimation, arise often in bioinformatics, computer vision and NLP, and are usually formulated as quadratic pseudoboolean problems (i.e. mathematical programming problems with binary and quadratic cost functions) (e.g. (3)).
There seems to be a growing trend in the literature to solve these problems via dual decomposition (as pointed out by the two articles I linked to above: (1), (2)). Moreover, some of these authors have pointed out that there are connections between an important class of inference algorithms, such as belief propagation and other general message passing methods, to dual decomposition (4).