0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ @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/… $\endgroup$ – Khue Apr 26 '16 at 17:43
  • $\begingroup$ 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. $\endgroup$ – Christian Clason Apr 26 '16 at 17:52
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Apr 26 '16 at 17:56
  • $\begingroup$ 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. $\endgroup$ – Christian Clason Apr 26 '16 at 17:59
  • $\begingroup$ @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. $\endgroup$ – Khue Apr 26 '16 at 18:13
6
$\begingroup$

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.

That's not saying ADMM can't work for nonconvex problems -- indeed, this is currently a very hot topic in nonsmooth optimization and image processing -- but the fact that you can only work with local minimizers makes the analysis (and practice) significantly more involved.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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)... $\endgroup$ – Khue Apr 26 '16 at 18:31
  • $\begingroup$ How to solve (3.2) and (3.3) is up to the users (similar to the prox operator in proximal methods, we assume that the users can evaluate it, but "how" is up to them). $\endgroup$ – Khue Apr 26 '16 at 18:31
  • $\begingroup$ I think you are severely underestimating the difficulty of computing global minimizers of nonconvex problems of the size that is relevant in the context these notes were written in. For example, any derivative-based method is right out (since they can never distinguish global from local minimizers). Also, algorithms of the form "To solve [difficult problem 1], proceed as follows: Step 1. Solve [problem 2, which is just as difficult as problem 1]. Step 2. [...]" typically do not make you any friends. $\endgroup$ – Christian Clason Apr 26 '16 at 19:08
  • $\begingroup$ ... and this most certainly involves prox-operators. (Also, these are well-defined only for convex functions!) $\endgroup$ – Christian Clason Apr 26 '16 at 19:10
2
$\begingroup$

It took me quite some time to figure out.

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$.

|cite|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.