1

Consider the following convex optimization problem: $$\text{minimize} ~ \sum_{i=1}^N f_i(x) ~ \text{ s.t. } ~ x \in X,$$ where $X$ is an $m$-dimensional convex set, and $f_i$'s are convex. We can rewrite this as: $$\text{minimize} ~ \sum_{i=1}^N f_i(x_i) ~ \text{ s.t. } ~ x_i \in X ~ \text{ and } ~ x_i = z ~\forall i.$$ This is called the global consensus problem (refer to Chapter 7 of Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers). The partial augmented Lagrangian for this problem is: $$L_\rho(x, z, y) = \sum_{i=1}^N\left( f_i(x_i) + y_i^T (x_i - z) + \rho/2 \Vert x_i - z \Vert_2^2 \right).$$ Let $(x^*, z^*, y^*)$ be the optimal solution. We know that $x_i^* = z^*$ for all $i$. Here are my questions:

  • Do we have $y_i^* = 0_m$?
  • If not, can we show that $\sum_i y_i^* = 0_m$? Also, what can we say about $\Vert y_i^* \Vert_2$ if $X = \{ x \in [0, 1]^m : \Vert x \Vert_1 \le 1\}$?
Royi
  • 8,711
smz
  • 283
  • It is not at all clear why you would expect the multipliers to sum to zero? Also, the $X$ at the end is not convex. – copper.hat Jan 20 '24 at 07:18
  • 1
    On page 50 of the book, it is shown that with ADMM updates, $\sum_i y_i^k = 0$. And we know that $y_i^k \to y_i^*$. I've changed the $X$. I think it's convex now. – smz Jan 20 '24 at 07:32

0 Answers0