1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks Ankur, I have updated the original post with a couple of examples. Dual decomposition methods are gaining quick popularity in the statistical machine learning literature, and I wonder if there is anything about their structure that makes them a better fit for dual decomposition. I think I have also read S. Boyd making a general statement about dual decomposition methods resulting in more efficient decompositions in practice than primal ones. Perhaps a large number of popular problems exhibit a structure that is more friendly for dual decomposition? $\endgroup$ – Amelio Vazquez-Reina May 3 '12 at 23:46
  • $\begingroup$ I think you need to be more specific about the overarching class of structures/optimization problems you are referring to. I don't think something as definitive as "a large number of popular problems exhibit a structure that is more friendly for dual decomposition?" can be said without clarity on the kind of problems you have in mind. $\endgroup$ – Ankur May 4 '12 at 0:04
  • $\begingroup$ Thanks @Ankur. MAP-MRF problems are relatively common in the bioinformatics, computer vision, and NLP literature. These problems are often formulated as quadratic pseudoboolean optimization problems, and there is a growing trend in the literature to solve these problems via dual decomposition. I have also seen authors pointing out a connection between belief propagation and other general message passing methods to dual decomposition. $\endgroup$ – Amelio Vazquez-Reina May 4 '12 at 13:52
  • $\begingroup$ I have tried answering your question by taking into account the examples you have cited. $\endgroup$ – Ankur May 5 '12 at 21:03
  • $\begingroup$ Thanks @Ankur, this is very helpful. In my update of the original post I expanded more on what type of problems I am referring to: MAP-MRF with binary and quadratic cost functions. In other words the cost function is more of the form argmin$[\sum a_{ij} x_i x_j + \sum b_k x_k]$ (as opposed to just argmin$[\sum f(x_k)]$ as you wrote). However you are right about the structure of the constraints $K$, they are almost always of the form $\sum_i f(x_i,x_j) = g(x_j)$ (i.e. defining what's known as the marginal polytope) $\endgroup$ – Amelio Vazquez-Reina May 6 '12 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.