# Stiefel optimization is NP-hard

arXiv: https://arxiv.org/abs/2507.02839 · HTML: https://mlsanity.com/paper/2507.02839/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Deflation-Free Optimal Scoring](https://mlsanity.com/paper/2604.25664/) (2026)

## Abstract (arXiv)

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 P=NP, these optimization problems over a Stiefel manifold do not have FPTAS. 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.