1d
comment Inequality with sum of numbers
@I.Stefan : please upvote and accept the answer. Thanks.
1d
answered Inequality with sum of numbers
Apr
29
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
@MichaelGrant: I have written a complete proof of the global convergence of ADMM for non-convex functions. In addition, I showed that the rate of convergence is at least $O(1/\sqrt{k})$. Please have a look: dropbox.com/s/8u0nh3mi33dsqxf/admm_nonconvex.pdf?dl=0 I'm looking forward to hearing your opinions :) Thank you very much!
Apr
27
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
@MichaelGrant : Tomorrow I'll read the paper again and try to carefully write down a complete proof of convergence for nonconvex functions (I'm replying you while on my bed using my phone :P). Thanks a lot for your discussion!
Apr
27
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
In the proof of (A2) for example, they wrote: "Since f is closed, proper, and convex it is subdifferentiable, and so is Lρ. The (necessary and sufficient) optimality condition is <conditions involving subgradients>." However, <conditions involving subgradients> hold whether f is convex or not (c.f. The p/s in my question).
Apr
26
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
The proof that the convexity assumption is not necessary: is right in the paper: just remove the convexity and the proofs of the inequalities (A1), (A2), (A3) still hold.
Apr
26
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
@MichaelGrant : Yes, ADMM converges to a KKT point. If the functions are convex then this KKT point is also globally optimal. Getting a KKT point is already not bad for nonconvex functions, isn't it?
Apr
26
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
@MichaelGrant : The proof uses optimality conditions based on subgradients, which also hold for nonconvex functions.
Apr
26
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
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).
Apr
26
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
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)...
Apr
26
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
@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.
Apr
26
comment On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
@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/…
Apr
26
accepted Subgradients of non-convex functions
Apr
26
answered Subgradients of non-convex functions
Apr
26
revised On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
related
Apr
26
asked On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
Apr
26
comment Subgradients of non-convex functions
@MichaelGrant: Thanks. Actually I was not trying to apply subgradient methods to nonconvex functions. The above question arose when I was reading the convergence analysis of ADMM in Boyd et al.'s paper. I have realized that the convexity assumption in that analysis is not necessary (but I may be wrong). Could you please have a look at this question: math.stackexchange.com/questions/1759829/…
Apr
26
asked On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
Apr
25
accepted Subgradients of non-convex functions
Apr
25
comment Subgradients of non-convex functions
Thanks a lot! :D
1 2 3 4 5