Nonconvex Generalization of ADMM for Nonlinear Equality Constrained Problems

Abstract

The growing demand on efficient and distributed optimization algorithms for large-scale data stimulates the popularity of Alternative Direction Methods of Multipliers (ADMM) in numerous areas, such as compressive sensing, matrix completion, and sparse feature learning. While linear equality constrained problems have been extensively explored to be solved by ADMM, there lacks a generic framework for ADMM to solve problems with nonlinear equality constraints, which are common in practical application (e.g., orthogonality constraints). To address this problem, in this paper, we proposed a new generic ADMM framework for handling nonlinear equality constraints, called neADMM. First, we propose the generalized problem formulation and systematically provide the sufficient condition for the convergence of neADMM. Second, we prove a sublinear convergence rate based on variational inequality framework and also provide an novel accelerated strategy on the update of the penalty parameter. In addition, several practical applications under the generic framework of neADMM are provided. Experimental results on several applications demonstrate the usefulness of our neADMM.