{"ID":2898874,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.02839","arxiv_id":"2507.02839","title":"Stiefel optimization is NP-hard","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2507.02839","url_pdf":"https://arxiv.org/pdf/2507.02839v2","authors":"[\"Zehua Lai\",\"Lek-Heng Lim\",\"Tianyun Tang\"]","published":"2025-07-03T17:47:22Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.CC\"]","methods":"[]","has_code":false}