Stiefel optimization is NP-hard
Published in arXiv, 2025
Recommended citation: Zehua Lai, Lek-Heng Lim, and Tianyun Tang. "Stiefel optimization is NP-hard." arXiv e-prints (2025): arXiv-2507.02839. https://arxiv.org/pdf/2507.02839
We show that linear programming over Stiefel manifold is NP-hard. After the first draft is posted, we found that part of the results in this paper has already been shown in the paper “Linear Programming on the Stiefel Manifold “ by Mengmeng Song and Yong Xia. We are working on a revised version.