Stiefel optimization is NP-hard
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917104501915648 |
|---|---|
| author | Lai, Zehua Lim, Lek-Heng Tang, Tianyun |
| author_facet | Lai, Zehua Lim, Lek-Heng Tang, Tianyun |
| contents | 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{NP}$, these optimization problems over a Stiefel manifold do not have $\mathrm{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02839 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Stiefel optimization is NP-hard Lai, Zehua Lim, Lek-Heng Tang, Tianyun Optimization and Control Computational Complexity 03D15, 90C26, 90C23, 65K10, 68Q25 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{NP}$, these optimization problems over a Stiefel manifold do not have $\mathrm{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. |
| title | Stiefel optimization is NP-hard |
| topic | Optimization and Control Computational Complexity 03D15, 90C26, 90C23, 65K10, 68Q25 |
| url | https://arxiv.org/abs/2507.02839 |