0

Consider the following convex problem.

$\min{\mathbf{x}_1,\cdots,\mathbf{x}_N\in\mathbb{R}^K}\sum_{n=1}^Na_n f(\mathbf{x}_n)\\ s.t.\quad \sum_{n=1}^N\mathbf{x}_n=\mathbf{c},\\ 0\le \mathbf{x}_n \le 1$

where $f(\mathbf{x}_n)$ is convex w.r.t. $\mathbf{x}_n$, $a_n\ge 0, \mathbf{c}\in \mathbb{R}^K$.

Does anyone have some clues to solve this problem? (Suppose that this problem can not be solved by the CVX tool.)

By the way, can this problem be solved by multi -block ADMM or BCD?

Dave
  • 576
  • 1
    I would suggest dynamic programming to solve this problem as it really fits that structure. Depending on the properties of the function $f(\cdot)$ you may be able to even find a closed form solution. –  Sep 24 '17 at 11:29
  • I do indeed think ADMM would work well here. In fact, what you're looking for here is consensus optimization. The constraint $\sum_n x_n = c$ is the so-called consistency or consensus constraint. Check out these slides (PDF) for instance. – Michael Grant Sep 24 '17 at 20:02
  • Can you explain more on that? I see that the consistency or consensus constraint is of the form $x_i − z = 0$ in that slides, while the constraint in my problem is $\sum_{n=1}^N\mathbf{x}_n=\mathbf{c}$. Should I introduce a new variable? – Dave Sep 25 '17 at 11:44

0 Answers0