3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Your link to Boyd's paper on ADMM is actually a link to a paper by Eckstein and Bertsekas and should be fixed. $\endgroup$ – Brian Borchers Feb 7 '16 at 0:39
  • $\begingroup$ @BrianBorchers: oops sorry. I have fixed the link. Thanks. $\endgroup$ – Khue Feb 7 '16 at 0:41
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nick, $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{T}$ are not $\mathbb{R}$ or $\mathbb{C} $, but some closed convex sets. This information is important, that's why I wrote it in bold in the question. (And KKT conditions are applied only for open set, right?) I have updated the question, please have a look. $\endgroup$ – Khue Feb 7 '16 at 14:01
  • $\begingroup$ @Khue Yes the conditions on page 18 of the admm paper only apply when the solution lies within an open set within the domain, ruling out problems where the solution is on the boundary (which it sounds like your problem is). So, the optimal point satisfies a different more complicated set of conditions shown on page 244 of Boyds book, linked above. ADMM is not well-suited suited for inequality constraints, but I think (?) it can be used used by building the inequality constraints into the objective. (so then each iteration requires solving constrained problems) $\endgroup$ – Nick Alger Feb 7 '16 at 20:49
  • $\begingroup$ I think I have found an answer. More general optimality conditions are stated in Definition 16 (page 14) of this paper: optimization-online.org/DB_FILE/2015/06/4954.pdf. And yes convergence guarantee is preserved if we solved the constrained problems at each iteration (even if the constraint sets are closed). $\endgroup$ – Khue Feb 7 '16 at 22:51
  • $\begingroup$ @Khue Err, that is the same definition as before, but stated with different notation. If you look at the referenced problem (3) on page 3, you can see that it is defined for $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$, and there are no inequality constraints (only equality constraints) $\endgroup$ – Nick Alger Feb 7 '16 at 23:08
  • $\begingroup$ Yes, on $\mathbb{R}^n$ the two sets of conditions are the same. However, the latter can be applied to closed sets and I believe this does not affect the convergence properties. I'll try to prove it and get back. $\endgroup$ – Khue Feb 8 '16 at 1:25

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.