Grassmannian Optimization Is NP-Hard

.We show that unconstrained quadratic optimization over a Grassmannian \(\operatorname{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, and (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 \(\operatorname {V}(k,n)\) and the orthogonal group \(\operatorname {O}(n)\). As an addendum we demonstrate the NP-hardness of unconstrained quadratic optimization over the Cartan manifold, i.e., the positive definite cone \(\mathbb{S}^n_{\scriptscriptstyle++}\) regarded as a Riemannian manifold, another popular example in manifold optimization. We will also establish the nonexistence of \(\textrm{FPTAS}\) in all cases.KeywordsGrassmannianmanifold optimizationNP-hardStiefel manifoldpositive definite coneMSC codes03D1590C2690C2365K1068Q2590C60