4

I am reading from Nonlinear Programming by Bertsekas, and in the section on ADMM, he says:

Consider the problem $$\text{min} \sum _{i=1} ^ m f_i(x)$$ $$\text{s.t. }x \in \cap _{i = 1}^m X_i,$$ where $f_i : \mathbb{R}^n \to \mathbb{R}$ are convex functions and $X_i$ are closed, convex sets with nonempty intersection. We can reformulate this as an equality constrained problem, by introducing additional artificial variables $z_i, i = 1,..., m$ and the equality constraints $x = z_i$: $$\text{min} \sum _{i=1} ^ m f_i(z_i)$$ $$\text{s.t.} \hspace{0.3 cm} x = z_i, \hspace{0.6cm} z_i \in X_i,\hspace{0.6cm} i = 1, ..., m$$

I don't quite understand this transformation. I see that we have $m$ different functions, and for each function $f_i$ its input must come from a (possibly) different set $X_i$. That makes sense. But what does $x$ mean in this second problem? My only idea is that $x$ doesn't really stand for anything; it is just there as a short way of saying $z_1 = z_2 = ... = z_m$. Is this correct?

Thank you very much!

Blue
  • 603
  • 1
  • 5
  • 8

1 Answers1

4

Yes, $x$ is the common value of the $z_i$s. This idea of introducing multiple copies of a variable is known as Lagrangian Decomposition. The $x=z_i$ equalities are linking constraints for what otherwise would decompose into $m$ disjoint subproblems.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • If you wouldn't mind answering a question: reading the problem literarily, it seems like $x$ is a constant with respect to the problem. Therefore the constraint set $C$ consists of a single point $C = { (x, x, ..., x) }$. Am I missing something here? It seems to me like the second problem should be \begin{align}\text{min} &\sum {i=1} ^ m f_i(z_i) \ \text{s.t. } \hspace{0.5cm} &z_i = z{i+1}, z_i \in X_i, \hspace{0.5cm} i = 1, 2, ..., m-1 \end{align} Am I correct? Thanks a lot! – Ovi Dec 02 '20 at 02:10
  • No, $x$ is a variable that is constrained to be in the intersection of all $X_i$. The formulation you provided is equivalent to the other two. – RobPratt Dec 02 '20 at 02:49
  • Ohh ok thank you so much for the clarification! In that case I think it would be slightly more correct to include $x \in \cap X_i$ as one of the constraints in the second problem. I guess you're supposed to deduce this from the first problem, but it's a little confusing, at least to me, as Bertsekas is usually pretty good about stating every single assumption. – Ovi Dec 02 '20 at 04:13
  • Each $z_i\in X_i$, so $x=z_i$ implies that $x\in \cap_i X_i$ without assuming it. – RobPratt Dec 02 '20 at 04:21
  • Yes that's true. The domain of variables is usually explicitly defined, but since the domain of $x$ was not explicitly defined here, I made the mistake of thinking it has to be a constant. Thank you very much again for your help! – Ovi Dec 02 '20 at 05:08