# Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints

arXiv: https://arxiv.org/abs/1810.03930 · HTML: https://mlsanity.com/paper/1810.03930/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2018.

## Built on by (most cited first, 16 of 16)

- [Fast and accurate optimization on the orthogonal manifold without retraction](https://mlsanity.com/paper/2102.07432/) (2021)
- [Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2303.16510/) (2023)
- [Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs](https://mlsanity.com/paper/2109.08046/) (2021)
- [Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function](https://mlsanity.com/paper/2112.14949/) (2021)
- [Momentum Stiefel Optimizer, with Applications to Suitably-Orthogonal Attention, and Optimal Transport](https://mlsanity.com/paper/2205.14173/) (2022)
- [Optimization without Retraction on the Random Generalized Stiefel Manifold](https://mlsanity.com/paper/2405.01702/) (2024)
- [Riemannian coordinate descent algorithms on matrix manifolds](https://mlsanity.com/paper/2406.02225/) (2024)
- [Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method](https://mlsanity.com/paper/2505.12378/) (2025)
- [An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale](https://mlsanity.com/paper/2602.14656/) (2026)
- [A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints](https://mlsanity.com/paper/2208.13643/) (2022)
- [A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2304.03641/) (2023)
- [Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points](https://mlsanity.com/paper/2112.13269/) (2021)
- [Rotation Averaging: A Primal-Dual Method and Closed-Forms in Cycle Graphs](https://mlsanity.com/paper/2406.18564/) (2024)
- [Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraints](https://mlsanity.com/paper/2604.04130/) (2026)
- [STN: a new tensor network method to identify stimulus category from brain activity pattern](https://mlsanity.com/paper/2210.16993/) (2022)
- [A second-order method landing on the Stiefel manifold via Newtonunicodex2013Schulz iteration](https://mlsanity.com/paper/2605.02838/) (2026)

## Abstract (arXiv)

To construct a parallel approach for solving optimization problems with orthogonality constraints is usually regarded as an extremely difficult mission, due to the low scalability of the orthonormalization procedure. However, such demand is particularly huge in some application areas such as materials computation. In this paper, we propose a proximal linearized augmented Lagrangian algorithm (PLAM) for solving optimization problems with orthogonality constraints. Unlike the classical augmented Lagrangian methods, in our algorithm, the prime variables are updated by minimizing a proximal linearized approximation of the augmented Lagrangian function, meanwhile the dual variables are updated by a closed-form expression which holds at any first-order stationary point. The orthonormalization procedure is only invoked once at the last step of the above mentioned algorithm if high-precision feasibility is needed. Consequently, the main parts of the proposed algorithm can be parallelized naturally. We establish global subsequence convergence, worst-case complexity and local convergence rate for PLAM under some mild assumptions. To reduce the sensitivity of the penalty parameter, we put forward a modification of PLAM, which is called parallelizable column-wise block minimization of PLAM (PCAL). Numerical experiments in serial illustrate that the novel updating rule for the Lagrangian multipliers significantly accelerates the convergence of PLAM and makes it comparable with the existent feasible solvers for optimization problems with orthogonality constraints, and the performance of PCAL does not highly rely on the choice of the penalty parameter. Numerical experiments under parallel environment demonstrate that PCAL attains good performance and high scalability in solving discretized Kohn-Sham total energy minimization problems.