2020/09/08 by Maryam Yashtini, Yashtini, Maryam · 1 citation
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #math.OC
paper · pdf · doi:10.48550/arxiv.2009.04014
arxiv created 2021/09/01 · arxiv updated 2021/09/02
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 KŁ 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 KŁ property asserts that there exists a continuous concave monotonically increasing function ψ such that around x^* it holds ψ'(f(x)-f(x^*))⋅\rm dist(0,∂ f(x))≥ 1 . When ψ(s)=s1-θ with θ∈[0,1] this is equivalent to |f(x)-f(x^*)|θ\rm dist(0,∂ 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.