Scholarlink

<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\textrm{P}=\textrm{NP}\)</EquationSource> </InlineEquation>, these optimization problems over a Stiefel manifold do not have <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\textrm{FPTAS}\)</EquationSource> </InlineEquation>. 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Stiefel optimization is NP-hard

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月19日

查看全文
  • Zehua Lai,
  • Lek-Heng Lim,
  • Tianyun Tang

摘要

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 \(\textrm{P}=\textrm{NP}\) , these optimization problems over a Stiefel manifold do not have \(\textrm{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.