# On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?

Please refer to Boyd et al.'s convergence analysis of ADMM (Chapter 3 and Appendix A).

My question is: Why do we need $f$ and $g$ to be convex?

I don't see the need of this assumption. If the convexity assumption is removed, the analysis is still valid.

Thanks.

• @ChristianClason: The convergence analysis of that paper is based on the inequalities (A.1), (A.2) and (A.3). These inequalities hold true without the convexity assumption on $f$ and $g$. Let's take the proof of (A.2) for example (as you have referred to it): the proof is based on the optimality condition involving subgradients, which still holds for nonconvex functions. Please see my previous question: scicomp.stackexchange.com/questions/23778/… – Khue Apr 26 '16 at 17:43
• As I wrote in my answer: For the subgradient to be empty, you need a global minimizer. But you can only guarantee that in (3.1) and (3.2) for convex functions. – Christian Clason Apr 26 '16 at 17:52
• It's quite common to prove "global convergence" of nonlinear optimization algorithms for bounded nonconvex minimization problems, where this means "convergence from any starting point to a local minimizer." This is not the same as "convergence to a global minimizer." However, Boyd's definition (see page 1 in the book) is that a point is "optimal" if it is globally optimal. In that sense, ADMM doesn't solve nonconvex optimization problems to obtain an optimal solution. – Brian Borchers Apr 26 '16 at 17:56
• To add to the point @BrianBorchers made: And even if you are satisfied with a local optimum, you still need to compute global solutions to the subproblems for this convergence analysis to go through. This is why practical nonconvex ADMM is so tricky. – Christian Clason Apr 26 '16 at 17:59
• @BrianBorchers: I agree that ADMM doesn't solve nonconvex optimization problems to global optimality. However, from the analysis, we already have the following result: ADMM converges to a KKT point ($f$ and $g$ are not necessarily convex), which is not bad at all, at least compared to stuffs like "converge of ADMM for nonconvex problems are still unknown" etc... that I read from some papers. – Khue Apr 26 '16 at 18:13

To consolidate my comments: The proof of inequality (A.2) rests on the fact that the solutions $x^{k+1}$ and $z^{k+1}$ of the substeps (3.2) and (3.3), respectively, are global minimizers, so you can compare them to the saddle points $x^*$ and $z^*$, respectively. (Here, Boyd uses the subdifferential characterization, but I'm sure you can also derive it using the optimality directly.) But this is only guaranteed if the subproblems are convex (where any minimizer is a global minimizer), which is the case if $f$ and $g$ are convex.
• I would be disappointed if (3.2) and (3.3) are the (only) reason (I was rather waiting for someone to show me that I have made a mistake and that the proof of such or such result requires the convexity). When writing (3.2) and (3.3) in ADMM, we implicitly assume that $x_{k+1}$ and $z_{k+1}$ can be evaluated. Do there exist nonconvex functions $f$ and $g$ for which (3.2) and (3.3) can be solved to global optimality, easily? Of course there do, and a lot. So why assume $f$ and $g$ are convex?...(next)... – Khue Apr 26 '16 at 18:31
If the convexity assumption is removed, then the following equation (line 9, page 108) no longer holds: $$\partial L_\rho(x^{k+1},z^k,y^k) = \partial f(x^{k+1}) + A^Ty^k + \rho A^T (Ax^{k+1} + Bz^k - c).$$ More accurately, this equation only holds if $\partial f(x^{k+1}) \neq \emptyset$ (which always holds if $f$ is convex). Similarly for $g$.