Grassmannian optimization is NP-hard

We show that unconstrained quadratic optimization over a Grassmannian Gr(k,n) is NP-hard. Our results cover all scenarios: (i) when k and n are both allowed to grow; (ii) when k is arbitrary but fixed; (iii) when k is fixed at its lowest possible value $1$. We then deduce the NP-hardness of unconstrained cubic optimization over the Stiefel manifold V(k,n) and the orthogonal group O(n). As an addendum we demonstrate the NP-hardness of unconstrained quadratic optimization over the Cartan manifold, i.e., the positive definite cone Sⁿ₊₊ regarded as a Riemannian manifold, another popular example in manifold optimization. We will also establish the nonexistence of FPTAS in all cases.