STOP – a toolbox for STiefel manifold OPtimization

STOP is a toolbox developed for solving the optimization problems with orthogonality constraints.

\[ \begin{equation*} \begin{aligned} \min\limits_{X \in \mathbb{R}^{n \times p}} \hspace{2mm} & f (X) \\ \mathrm{s.t.} \hspace{3.5mm} & X \in \mathcal{S}_{n, p} := \{X \in \mathbb{R}^{n \times p} \mid X^{\top} X = I_p\}. \end{aligned} \end{equation*} \]

Here, \(f(X): \mathbb{R}^{n \times p} \to \mathbb{R}\) is an objective function, and the feasible set \(\mathcal{S}_{n, p}\) is usually referred to as the Stiefel manifold.

There are two categories of solvers in STOP, including feasible methods and infeasible methods. Distinct from Riemannian optimization algorithms, STOP captures the special structures of Stiefel manifolds, and hence can achieve high efficiency. Unless otherwise specified, for a smooth function \(g(X)\), \(\nabla g(X)\) and \(\nabla^2 g(X)\) stand for the Euclidean gradient and Hessian in STOP, respectively.

The STOP toolbox can be downloaded from Gitee or this link.
More information can be found in the Users’ Guide.

The Python version of STOP (PySTOP) is available on Gitee and PyPI (Users’ Guide).

Feasible Methods

STOP provides a class of feasible methods, called multipliers correction methods.

Multipliers correction methods aim to minimize a smooth function \(f(X)\) over the Stiefel manifold, which combine a function value reduction step with a correction step. The former one searches along the standard Euclidean descent directions instead of the vectors in the tangent space of \(\mathcal{S}_{n, p}\), and the latter one further reduces the function value and guarantees a symmetric dual variable at the same time.

FOForth focuses on the following structured objective functions.

\(f (X) = h (X) + \mathrm{tr} (G^{\top} X)\).

\(G \in \mathbb{R}^{n \times p}\) is a constant matrix.
\(h (X)\) is invariant under the orthogonal transformation, i.e., \(h(XQ) = h(X)\) holds for any \(Q \in \mathcal{S}_{p,p}\).
\(\nabla h(X) = H(X) X\), where \(H:\mathbb{R}^{n \times p} \to \mathbb{S}^{n}\) and \(\mathbb{S}^{n}\) represents the set of \(n \times n\) symmetric matrices.

ProxOrth extends the framework of FOForth to generic smooth objectives.

Infeasible Methods

The orthonormalization process has low parallel scalability. With the increasing of \(p\), a bottleneck of feasible algorithms emerges, that is, lack of concurrency. To address this issue, STOP provides a class of infeasible methods to waive the orthonormalization process. Hence, parallelization becomes tractable in solving the optimization problems over the Stiefel manifold.

For smooth objectives.
- PCAL is based on the augmented Lagrangian method (ALM), but updates the multipliers by a closed-form expression.
- PenCF uses a first-order approach to solve an exact penalty model.
- PenCS uses a second-order approach to solve an exact penalty model.

For nonsmooth objectives.
- PenCPG minimizes a smooth function plus an \(\ell_{2,1}\)-norm regularizer over the Stiefel manifold. It uses a proximal gradient approach to solve an exact penalty model.
- SLPG alternately takes tangential steps and normal steps to improve the optimality and feasibility respectively, which is penalty-free.

References

If you use these codes in an academic paper, please cite the following papers.

B. Gao, X. Liu, X. Chen, and Y. Yuan, A New First-order Algorithmic Framework for Optimization Problems with Orthogonality Constraints, SIAM Journal on Optimization, 28-1(2018), 302–332.
L. Wang, B. Gao, and X. Liu, Multipliers Correction Methods for Optimization Problems over the Stiefel Manifold, CSIAM Transactions on Applied Mathematics, 2-3(2021), 508-531.
B. Gao, X. Liu, and Y. Yuan, Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints, SIAM Journal on Scientific Computing, 41-3(2019), A1949–A1983.
N. Xiao, X. Liu, and Y. Yuan, A Class of Smooth Exact Penalty Function Methods for Optimization Problems with Orthogonality Constraints, Optimization Methods and Software.
N. Xiao, X. Liu, and Y. Yuan, Exact Penalty Function for \(\ell_{2,1}\) Norm Minimization over the Stiefel Manifold, SIAM Journal on Optimization.
N. Xiao, X. Liu, and Y. Yuan, A Penalty-free Infeasible Approach for a Class of Nonsmooth Optimization Problems over the Stiefel Manifold, arXiv:2103.03514.

Authors

STOP is developed by the following authors listed in alphabetical order in the State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences.

To Contact Us

If you have any questions or find any bugs, please feel free to contact us by email (stmopt@foxmail.com).

In oreder to help you use STOP, we are happy to receive feedbacks, bug reports and requests for more features, and to discuss the toolbox as well as its documentation. We would also like to know how you use the toolbox.

License

STOP is a free software. You can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

STOP is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Please see the GNU Lesser General Public License for more details.