1
$\begingroup$

Consider the optimization problem $$ \min_{ x_1, \ldots, x_N } \sum_{i=1}^{N} f_i( x_i ) \\ \text{s.t.: } \sum_{i=1}^{N} x_i \in X, \ x_i \in X_i \ \forall i \in \{1, \ldots, N\} $$

where $f_1, \ldots, f_N : \mathbb{R}^n \rightarrow \mathbb{R}$ are convex and continuous, $X, X_1, \ldots, X_N \subset \mathbb{R}^n$ are compact and convex.

I am looking for a decentralized scheme to solve the problem.

Comment. I tried with the standard augmented Lagrangian method and the ADMM method, with $x:= (x_1, \ldots, x_N) \in X_1 \times \cdots \times X_N$, an additional variable $y := \sum_{i=1}^{N} x_i \in X$, and augmented cost $f(x) + g(y) := \sum_{i=1}^{N} \{ f_i( x_i ) \} + I_{X}(y)$, where $I_X$ is the characteristic function of the set $X$. However, the primal update $x^{k+1}$ is not entirely decomposable, namely the updates $x_1^{k+1}, \ldots, x_N^{k+1}$ cannot be implemented in parallel.

$\endgroup$
  • $\begingroup$ I'd say the answer depends significantly on what the coupling constraint set $X$ is. What do you have in mind? Here is a PDF from Stephen Boyd's group talking about decomposition methods; perhaps the general principles found therein can help you formulate your own. $\endgroup$ – Michael Grant Nov 12 '14 at 18:59
  • $\begingroup$ Can you please elaborate a bit your comment? I mean: Why $X$ matters even if the constraint is already "decomposed" as $\sum_i x_i$? As for $X$, I would start from general bounded polytopes. $\endgroup$ – user693 Nov 12 '14 at 19:08
  • 1
    $\begingroup$ The point is, that the merits of a specific decomposition approach will depend rather critically on how the constraints for $X$ are represented. But I must confess I don't have a lot of experience building my own decomposition methods, which is why I am responding in comments and not an answer :-) $\endgroup$ – Michael Grant Nov 12 '14 at 21:54
  • $\begingroup$ Ok, thank you very much. I think the dual ascent method should work. $\endgroup$ – user693 Nov 13 '14 at 7:57

Your Answer

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

Browse other questions tagged or ask your own question.