Grassmannian optimization is NP-hard
Published in arXiv (accepted by SIOPT), 2025
Recommended citation: Zehua Lai, Lek-Heng Lim, and Ke Ye. "Grassmannian optimization is NP-hard." arXiv e-prints (2024): arXiv-2406.19377. https://arxiv.org/pdf/2406.19377
We show that unconstrained quadratic optimization over a Grassmannian is NP-hard. We then deduce the NP-hardness of unconstrained cubic optimization over the Stiefel manifold and the orthogonal group. As an addendum we demonstrate the NP-hardness of unconstrained quadratic optimization over the positive definite cone.