Primal vs dual decomposition methods

Question

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).

Answer 1

I don't think one can make a blanket statement on whether primal decomposition methods or dual decomposition methods are more efficient. The efficiency is dictated by the structure of the problem; primal decomposition and dual decomposition are ways of exploiting this structure to develop efficient algorithms.

The key aspect in making a choice between these methods is the kind of parametrization the master brings about on the slaves. Fo e.g., sometimes it is convenient (in terms of theory or practice) to have the parametrization in the objective function of the slave problems instead of having it in the constraints. If the parametrization happens to appear in the constraints (and it has suitable structure), one can try to dualize the slave problem to get in the objective.

In the slides you have linked, the effort seems to be in exploiting the structure for parallelization of the solution of subproblems. For parallelization one would require subproblems that are independent of each other. If there is a natural separability in the constraints, dual variables can be used to parametrize the problem and thereby create such subproblems.

Edit: I repeat once again that structure is important in determining the choice of the method. I am still not completely clear on the structure afforded by the problems you have in mind. Based on the information given, this is my best attempt at answering your question.

From the examples you have added, the problems appear to be what can be called "nearly separable". In essence, these problems appear to be variants of the problem $\min \{\sum_{i=1}^n f_i(x_i) : (x_1,...,x_n) \in K\}$, where $K$ is a constraint that has a separable structure. For example, the constraint $(x_1,...,x_n) \in K$ may be $\sum_ix_i =b$, where $b$ is a vector of appropriate size. By separable structure I mean that the optimal values of variables $x_1,...,x_n$ can be chosen independently of each other. If one looks at the problem as a whole, the objective functions are decoupled in individual variables, but because of the coupling in $K$ these variables cannot be independently optimized. However because this coupling in $K$ is mild, one can still salvage separability. Dual decomposition lets you separate the variables when they are coupled in the constraints. If the variables were coupled in the objective, one may have to employ primal decomposition (as in Boyd's slides). One may of course try to reformulate problems to bring them in some or the other form that one is comfortable using.

To demonstrate separation by dual decomposition, define the Lagrangian $L(x,\lambda) =\sum_i f_i(x_i) + \lambda^T(\sum_i x_i)$. If $(x,\lambda)$ is a saddle point of $L$, then $x$ solves the original problem. A dual decomposition method would for each value of $\lambda$, minimize $L(x,\lambda)$ over $x$, altering $\lambda$ until a saddle point is found. The minimization in $x$ is easier, in particular separable and parallelizable.