Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am looking at the following paper to implement dual decomposition for my algorithm:

On Pg.29 they suggest setting the step size for the sub-gradient method by taking the difference of the best primal solution and current dual solution and dividing by the L2-norm of the sub-gradient at current iteration.

My doubt is the following: Do I use sub-gradients for each slave problem and compute a different step-size for each slave problem? Or is there some way I can compute the sub-gradient for the combined dual problem?

share|cite|improve this question
up vote 2 down vote accepted

Step-sizes are the crucial and difficult point when using subgradient methods. Basically you need that the step-sizes tend to zero but not too fast. If one uses a-priori step-sizes (e.g. of the form $1/k$) then the method provably converges but in practice it will slow down such that you'll not observe convergence.

The dynamic rule they suggest in the paper (in equation (40)) look like so-called Polyak step-sizes with estimation of the true optimal values (obtained by values of the dual problem). One can prove convergence with these step-sizes under special conditions. I do not know a good reference off the top of my head but many books on (nonsmooth) convex optimization should treat this.

share|cite|improve this answer
Thanks, but my doubt was slightly different. Since my dual problem is decomposed into multiple slave problems, there exists a sub-gradient for each slave problem. Now while computing the Polyak step-sizes, what should be the term in denominator? If it is sub-gradient for each slave problem, then the step-size would be different for each slave even for the same iteration of the subgradient method. Does this make sense? – stressed_geek Jul 17 '12 at 10:06
What do you mean my "decomposed into multiple slace problems"? Probably you can form a subgradient of the "total" dual problem from the subgradients of the "slave probelms"? – Dirk Jul 17 '12 at 11:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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