Grassmannian optimization is NP-hard
Published in SIAM Journal on Optimization, 2025
Recommended citation: Zehua Lai, Lek-Heng Lim, and Ke Ye. "Grassmannian optimization is NP-hard." SIAM Journal on Optimization, Volume 35, Issue 3, (2025) https://epubs.siam.org/doi/10.1137/24M1672596
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.