4
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.