# How do you turn an abstract set constraint into equality constraints?

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!

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.
• 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 2 '20 at 2: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 2 '20 at 2: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 2 '20 at 4:13
• Each $z_i\in X_i$, so $x=z_i$ implies that $x\in \cap_i X_i$ without assuming it. – RobPratt Dec 2 '20 at 4: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 2 '20 at 5:08