Speaker
Dr
Tianyun Tang
(University of Chicago)
Description
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 opti- mization 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.
Authors
Prof.
Lek-Heng Lim
(The University of Chicago)
Dr
Zehua Lai
(University of Texas at Austin)