.png){kind=icon}
.png){kind=icon}
Return
Stiefel optimization is NP-hard
.png){kind=icon}
PRE
AI
DOI：10.1007/s11590-025-02271-9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Stiefel manifold
Grassmannian
Flag manifold
Linear programming
Quadratic programming
NP-hard
Journal
O
IF:
1.1
Papers:
72
Citations:
2.4K