Multi-Block Nonconvex Nonsmooth Proximal ADMM: Convergence and Rates under Kurdyka-Lojasiewicz Property

In this paper, we consider a multi-block generalized alternating direction method of multiplier (GADMM) algorithm for minimizing a linearly constrained separable nonconvex and possibly nonsmooth optimization problem. The GADMM generalizes the classical ADMM by including proximal terms in each primal updates and an over-relaxation parameter in the dual update. We prove that any limit point of the sequence is a critical point. By introducing a modified augmented Lagrangian we show that the sequence generated by the GADMM is bounded and the norm of the difference of consecutive terms approaches to zero. Under the powerful KL properties we show that the GADMM sequence has a finite length and converges to a stationary point, and we drive its convergence rate. Given a proper lower-semicontinuous function f:mathbb Rn→mathbb R and a critical point x^*∈mathbb Rn, the KL property asserts that there exists a continuous concave monotonically increasing function psi such that around x^* it holds psi'(f(x)-f(x^*))·rm dist(0,partial f(x))≥ 1 . When psi(s)=s1-θ with θ∈[0,1] this is equivalent to |f(x)-f(x^*)|θrm dist(0,partial f(x))-1 to remain bounded around x^*. We show that if θ=0, the sequence generated by GADMM converges in a finite numbers of iterations. If θ∈(0,1/2], then the rate of convergence is cQk where c>0, Q∈(0,1), and k∈mathbb N is the iteration number. If θ∈(1/2,1] then the rate mathcal O(1/kr) where r=(1-θ)/(2θ-1) will be achieved.