Understanding the conditions for which ADMM can be applied

Question

While reading Boyd's paper on ADMM I encountered an issue.

Consider the following problem:

Problem. Minimize $f(u) + g(v)$ subject to $Au + Bv = c$, where $f$ and $g$ are closed, proper, convex and differentiable.

Denote by $\lambda$ the dual variable. On page 18 of the paper, it is stated that the necessary and sufficient optimality conditions for the above problem are: \begin{align} Au^* + Bv^* &= c\\ \nabla f(u^*) + A^T\lambda^* &= 0\\ \nabla g(v^*) + B^T\lambda^* &= 0. \end{align} (I changed the names of the variables, sorry for the inconvenience.)

Now consider the following special case:

Let $$u=(x,t)\in \mathcal{X}\times\mathcal{T}, \quad v=(y,z)\in \mathcal{Y}\times\mathcal{Z}, \quad f(u) = h(x) + at, \ a\neq 0$$ where $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{T}$ are closed and convex. and $$A = \begin{bmatrix} -1 & 0\\ -1& 0 \end{bmatrix}, B = \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix},c=0,\lambda = (\lambda_y,\lambda_z)$$

(i.e. the problem becomes Minimize $h(x) + at + g(y,z)$ subject to $y=x,z=x$).

The second optimality condition above becomes $$\begin{bmatrix} \nabla h(x^*)\\ a \end{bmatrix} + \begin{bmatrix} -1 & -1\\ 0 & 0 \end{bmatrix}\begin{bmatrix} \lambda_y^*\\ \lambda_z^* \end{bmatrix} = 0$$ Or equivalently $$\begin{bmatrix} \nabla h(x^*) - \lambda_y^* - \lambda_z^*\\ a \end{bmatrix} = 0,$$ which can not be achieved because $a\neq 0$!

What am I missing?

Thank you in advance for your discussions!

---

Update: The motivation of the above example comes from the following problem I encountered in practice:

Minimize $(a+c+d)^Tx_1 + b^Tx_2$ subject to $(x_1,x_2)\in \mathcal X$, where $\mathcal X$ is a closed convex set defined by $$\mathcal X = \left\{(x_1,x_2)\middle| \begin{matrix} (x_1,x_2) \text{ satisfy some condition } (1), \\ x_1 \text{ satisfies some condition } (2),\\ x_1 \text{ satisfies some condition } (3) \end{matrix}\right\}$$

Denote \begin{align} \mathcal X_1 &= \left\{(x_1,x_2)\mid (x_1,x_2) \text{ satisfy condition } (1)\right\}\\ \mathcal Y &= \left\{x_1 \mid x_1 \text{ satisfies condition } (2)\right\}\\ \mathcal Z &= \left\{x_1 \mid x_1 \text{ satisfies condition } (3)\right\} \end{align} Suppose that the original optimization problem is very hard, but the problems of minimizing any quadratic function over (only) one of the set $\mathcal X_1, \mathcal Y, \mathcal Z$ are easy (minimizing over the intersection of any two sets among them is hard as well).

We can thus decompose the problem using ADMM by reformulating it as:

Minimize $a^Tx_1 + b^Tx_2 + c^Ty +d^Tz$ subject to $y=x_1, z=x_1, (x_1,x_2) \in \mathcal X_1, y\in\mathcal Y, z\in\mathcal Z$.

Can we apply ADMM now, if $\mathcal X_1, \mathcal Y, \mathcal Z$ are closed and convex? What are the optimality conditions then?

Answer 1

If I understand the proposed optimization problem correctly, then the only constraint is the equality constraint $Au + Bv=c$ (and $\mathcal{X} = \mathcal{T} = \mathcal{Y} = \mathcal{Z} = \mathbb{R}$ or $\mathbb{C}$).

In this case I think there is no optimal point. To see this, note that by the nature of the matrix $A$, the inequality constraint doesn't care about the value of $t$, so one can choose $t$ to be whatever you want independent of all the other variables. On the other hand, the objective function takes the form, $$f(u) + g(v) = at + [\text{stuff not depending on t}].$$ Thus one can make the objective as large or small as desired by taking $t \rightarrow \pm \infty$.

On the other hand, if I interpreted what you wrote wrong and the sets $\mathcal{X}$, $\mathcal{T}$, etc., are intervals rather then the whole real line, then you could enforce these requirement by either (1) using additional Lagrange multipliers $\nu$ to enforce inequality constraints, or (2) building the constraint into the objective by adding a penalty term that is zero in the feasible set and +infinity outside. Either way, a more detailed analysis is required.

For more details on first order conditions for inequality constrained optimization problems, see section 5.5.3 on the KKT optimality conditions on page 243 in Boyd's book, https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf