A framework of constraint preserving update schemes for optimization on Stiefel manifold

Bo Jiang, Yu-Hong DaiMath. Program 2015 · OpenReview

TL;DR

This paper introduces a novel framework for solving optimization problems on the Stiefel manifold, which are common in fields like quantum chemistry and signal processing. The authors propose a new, efficient update scheme that unifies existing methods and demonstrate its effectiveness with a Barzilai-Borwein-like algorithm that achieves global convergence.

What Problem Does This Paper Address?

Many real-world problems involve optimizing a function subject to the constraint that a matrix $X$ must be "orthonormal," meaning $X^T X = I_p$. This constraint defines the Stiefel manifold, a curved space that makes standard optimization techniques challenging. Existing methods for solving these problems often rely on complex "retraction" or "projection" steps to maintain the orthogonality constraint, which can be computationally expensive or lack theoretical guarantees. The paper aims to develop a more unified, efficient, and theoretically sound approach to optimization on the Stiefel manifold.

Methods

The core of the paper is a new framework for generating update steps that preserve the Stiefel manifold constraint. This framework decomposes a feasible point $X$ into its "range space" and "null space," allowing for a more flexible construction of update schemes. From this framework, the authors derive a new update scheme with lower computational complexity than many existing methods.

They then combine this new update scheme with a Barzilai-Borwein-like (BB-like) stepsize selection strategy. To ensure global convergence, they employ an adaptive nonmonotone line search. This leads to the proposed "Adaptive Feasible Barzilai-Borwein-like" (AFBB) method. The paper also extends this framework to handle generalized orthogonality constraints.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and testing on established benchmark problems.

Key Insights and Ideas

  • Unified Framework: The decomposition approach provides a unifying perspective on various existing update schemes (geodesic, gradient projection, polar decomposition, QR factorization), demonstrating that they can be seen as special cases of a more general framework.
  • Low-Complexity Update: The newly discovered update scheme offers a significant reduction in computational cost, especially for certain problem dimensions.
  • Global Convergence Guarantee: The AFBB method, by combining the new update scheme with an adaptive nonmonotone line search, achieves a proven global convergence guarantee, which is a significant theoretical contribution for this class of problems.
  • Practical Efficiency: The AFBB method demonstrates strong performance in numerical experiments, often outperforming existing state-of-the-art algorithms in terms of speed and solution quality.

Key Results

The paper presents numerical results on several challenging problems:

  • Nearest Low-Rank Correlation Matrix Problem: AFBB significantly outperforms three other state-of-the-art algorithms (SemiNewton, PenCorr, OptM) in terms of speed and solution quality. In some cases, it is considerably faster and finds better solutions.
  • Kohn-Sham Total Energy Minimization: AFBB is highly competitive with the widely used Self-Consistent Field (SCF) iteration, often achieving better results with less CPU time, especially for large molecules.
  • Generalized Orthogonality Constraints: The framework is extended to handle more general constraints, showing promise for broader applicability.

Limitations and Future Work

  • Global Optimality: While the paper proves global convergence (meaning the algorithm will eventually find a local minimum), it does not guarantee finding the global minimum for non-convex problems. The authors note that finding the global minimizer with high probability remains an open problem.
  • Subspace Techniques: The authors suggest that exploring subspace techniques could be a promising avenue for developing methods that are more likely to find the global optimum.
  • General Constraints: Extending the AFBB method to handle more general constraints beyond the Stiefel manifold (e.g., lower and upper bound constraints) is an area for future research.
  • Parameter Tuning: While the adaptive line search helps, the performance of AFBB can still be influenced by parameter choices, and further investigation into optimal parameter selection or adaptive strategies for these parameters is suggested.

Summary updated

Abstract

This paper considers optimization problems on the Stiefel manifold $$X^{\mathsf{T}}X=I_p$$ X T X = I p , where $$X\in \mathbb {R}^{n \times p}$$ X ∈ R n × p is the variable and $$I_p$$ I p is the $$p$$ p -by- $$p$$ p identity matrix. A framework of constraint preserving update schemes is proposed by decomposing each feasible point into the range space of $$X$$ X and the null space of $$X^{\mathsf{T}}$$ X T . While this general framework can unify many existing schemes, a new update scheme with low complexity cost is also discovered. Then we study a feasible Barzilai–Borwein-like method under the new update scheme. The global convergence of the method is established with an adaptive nonmonotone line search. The numerical tests on the nearest low-rank correlation matrix problem, the Kohn–Sham total energy minimization and a specific problem from statistics demonstrate the efficiency of the new method. In particular, the new method performs remarkably well for the nearest low-rank correlation matrix problem in terms of speed and solution quality and is considerably competitive with the widely used SCF iteration for the Kohn–Sham total energy minimization.
BibTeX
@inproceedings{jiang2015framework,
  author = {Bo Jiang and Yu-Hong Dai},
  title = {{A framework of constraint preserving update schemes for optimization on Stiefel manifold}},
  booktitle = {Math. Program},
  year = {2015},
  url = {https://openreview.net/forum?id=IKv9dQU143},
}
Figure