ADMM for Nonsmooth Composite Optimization under Orthogonality Constraints

We consider a class of structured, nonconvex, nonsmooth optimization problems under orthogonality constraints, where the objectives combine a smooth function, a nonsmooth concave function, and a nonsmooth weakly convex function. This class of problems finds diverse applications in statistical learning and data science. Existing ADMMs for addressing these problems often fail to exploit the specific structure of orthogonality constraints, struggle with nonsmooth functions and nonconvex constraint sets, or result in suboptimal oracle complexity. We propose OADMM, an Alternating Direction Method of Multipliers (ADMM) designed to solve this class of problems using efficient proximal linearized strategies. Two specific variants of OADMM are explored: one based on Euclidean Projection (OADMM-EP) and the other on Riemannian retraction (OADMM-RR). We integrate a Nesterov extrapolation strategy into OADMM-EP and a monotone Barzilai-Borwein strategy into OADMM-RR to potentially accelerate primal convergence. Additionally, we adopt an over-relaxation strategy in both OADMM-EP and OADMM-RR for rapid dual convergence. Under mild assumptions, we prove that OADMM converges to the critical point of the problem with a provable convergence rate of O (1/^3). We also establish the convergence rate of OADMM under the Kurdyka-Lojasiewicz (KL) inequality. Numerical experiments are conducted to demonstrate the advantages of the proposed method.