1

http://stanford.edu/~boyd/papers/pdf/prox_algs.pdf

In the link above it is proposed that the nonsmooth separable resource allocation problem $$\min \sum f_i(x_i) \ \ \text{s.t.} \ \ \textbf{1}^Tx = b, x_i \geq 0$$

can be solved efficiently by the algorithm:

$$x^{k+1}_i := \text{prox}_{\lambda f_i}(x_i^k-z^k-u^k) \\ z^{k+1} := \text{proj}_X(x^{k+1}+u^k)\\ u_i^{k+1} := u_i^k+x_i^{k+1}-z^{k+1}$$

Here proj$_X$ is the Euclidian projection onto the feasible set. I'm having problems seeing what makes this method essentially different from taking a step in a negative subgradient direction and then projecting the point onto the feasible set.

What advantages does introducing a bunch of helper variables bring? And wouldn't it usually be more expensive to evaluate the prox operator rather than finding an arbitrary subgradient?

Benjamin Lindqvist
  • 3,112
  • 1
    Short answer: The algorithm listed above is an ADMM (google it). This is known to be simple to implement, easy to parallelize, can handle sums of multiple objective functions, can handle "variable splitting" (via the z variable), etc. For example, you can't really do stuff like (isotropic) TV minimization via projected subgradient (due to the composite TV penalty term). However, in general the convergence rate of ADMM is less well-understood as the subgradient projection (the latter is essentially the ISTA algorithm). If necessary, I can expand this into an answer. – dohmatob Jun 29 '15 at 23:58
  • If you have more to say, I'd be very interested in reading :) – Benjamin Lindqvist Jul 01 '15 at 07:29

0 Answers0