Global Complexity Bound of a Proximal ADMM for Linearly Constrained Nonseparable Nonconvex Composite Programming
提出一种阻尼近端交替方向乘子法(DP.ADMM)，用于求解目标函数光滑部分不可分的线性约束非凸优化问题，在无需约束矩阵秩假设的条件下，证明了算法在O(ε^{-3})次迭代内达到近似一阶稳定点。
.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 \({\cal O}(\varepsilon^{-3})\) iterations for a given numerical tolerance \(\varepsilon \gt 0\). 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.Keywordsproximal ADMMnonseparable nonconvex composite optimizationiteration complexityunder-relaxed updateaugmented Lagrangian functionMSC codes65K1090C2590C2690C3090C60