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.

| improve this answer | |
$\endgroup$

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.