Stiefel optimization is NP-hard

We show that linearly constrained linear optimization over a Stiefel or Grassmann manifold is NP-hard in general. We show that the same is true for unconstrained quadratic optimization over a Stiefel manifold. We will show that unless $\mathrm{P}=\mathrm{N}\mathrm{P}$, these optimization problems over a Stiefel manifold do not have $\mathrm{F}\mathrm{P}\mathrm{T}\mathrm{A}\mathrm{S}$. As an aside we extend our results to flag manifolds. Combined with earlier findings, this shows that manifold optimization is a difficult endeavor – even the simplest problems like LP and unconstrained QP are already NP-hard on the most common manifolds.