Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints

Abstract

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.

Cited by in corpus (9)

• Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function
• Optimal Orbital Selection for Full Configuration Interaction (OptOrbFCI): Pursuing the Basis Set Limit under a Budget
• A Communication-Efficient and Privacy-Aware Distributed Algorithm for Sparse PCA
• A force-based gradient descent method for $\text{ab initio}$ atomic structure relaxation
• Solving Optimization Problems over the Stiefel Manifold by Smooth Exact Penalty Function
• Triangularized Orthogonalization-free Method for Solving Extreme Eigenvalue Problems
• Multipliers Correction Methods for Optimization Problems over the Stiefel Manifold
• Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs
• Convergent and orthogonality preserving schemes for approximating the Kohn-Sham orbitals