We show that unconstrained quadratic optimization over a Grassmannian Gr(k, n) is NP-hard. Our results cover all scenarios: (i) when k and n are both allowed to grow, (ii) when k is arbitrary but fixed, and (iii) when k is fixed at its lowest possible value 1. We then deduce the NP-hardness of unconstrained cubic optimization over the Stiefel manifold V(k, n) and the orthogonal group O(n). As an addendum we demonstrate the NP-hardness of unconstrained quadratic optimization over the Cartan manifold, i.e., the positive definite cone \BbbS n ++ regarded as a Riemannian manifold, another popular example in manifold optimization. We will also establish the nonexistence of FPTAS in all cases.

Publication:

SIAM JOURNAL ON OPTIMIZATION

http://dx.doi.org/10.1137/24M1672596

Author:

KE YE

State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science,Chinese Academy of Sciences, Beijing 100190, China

keyk@amss.ac.cn