# Khue

 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 ." However, 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 functionsThanks a lot! :D