GLOBAL COMPLEXITY BOUND OF A PROXIMAL ADMM FOR LINEARLY CONSTRAINED NONSEPARABLE NONCONVEX COMPOSITE PROGRAMMING.

This paper proposes and analyzes a dampened proximal alternating direction method of multipliers (DP.ADMM) for solving linearly constrained nonconvex optimization problems where the smooth part of the objective function is nonseparable. Each iteration of DP.ADMM consists of (i) a sequence of partial proximal augmented Lagrangian (AL) updates, (ii) an under-relaxed Lagrange multiplier update, and (iii) a novel test to check whether the penalty parameter of the AL function should be updated. Under a basic Slater point condition and some requirements on the dampening factor and under-relaxation parameter, it is shown that DP.ADMM obtains an approximate first-order stationary point of the constrained problem in O(ε^-3) iterations for a given numerical tolerance ε > O. One of the main novelties of the paper is that convergence of the method is obtained without requiring any rank assumptions on the constraint matrices. [ABSTRACT FROM AUTHOR]