A Riemannian Alternating Direction Method of Multipliers
- 1 November 2025
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 50 (4) , 3222-3242
Abstract
We consider a class of Riemannian optimization problems where the objective is the sum of a smooth function and a nonsmooth function considered in the ambient space. This class of problems finds important applications in machine learning and statistics, such as sparse principal component analysis, sparse spectral clustering, and orthogonal dictionary learning. We propose a Riemannian alternating direction method of multipliers (ADMM) to solve this class of problems. Our algorithm adopts easily computable steps in each iteration. The iteration complexity of the proposed algorithm for obtaining an ϵ-stationary point is analyzed under mild assumptions. Existing ADMMs for solving nonconvex problems either do not allow a nonconvex constraint set or do not allow a nonsmooth objective function. Our algorithm is the first ADMM-type algorithm that minimizes a nonsmooth objective over manifold—a particular nonconvex set. Numerical experiments are conducted to demonstrate the advantage of the proposed method. Funding: The research of S. Ma was supported in part by the Office of Naval Research [Grant N00014-24-1-2705]; the National Science Foundation [Grants DMS-2243650, CCF-2308597, CCF-2311275, and ECCS-2326591]; the University of California, Davis Center for Data Science and Artificial Intelligence Research Innovative Data Science Seed Funding Program; and Rice University start-up fund.Keywords
This publication has 45 references indexed in Scilit:
- A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifoldsMathematical Programming, 2022
- Riemannian proximal gradient methodsMathematical Programming, 2021
- Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysisMathematical Programming, 2019
- Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysisComputational Optimization and Applications, 2018
- Global Convergence of ADMM in Nonconvex Nonsmooth OptimizationJournal of Scientific Computing, 2018
- A Regularized Semi-Smooth Newton Method with Projection Steps for Composite Convex ProgramsJournal of Scientific Computing, 2017
- A Geometric Analysis of Phase RetrievalFoundations of Computational Mathematics, 2017
- ε-subgradient algorithms for locally lipschitz functions on Riemannian manifoldsAdvances in Computational Mathematics, 2015
- Robust Computation of Linear Models by Convex RelaxationFoundations of Computational Mathematics, 2014
- A Splitting Method for Orthogonality Constrained ProblemsJournal of Scientific Computing, 2013