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:

ZEHUA LAI

Department of Mathematics, University of Texas, Austin, TX 78712 USA

zehua.lai@austin.utexas.edu

LEK-HENG LIM\ddagger ,

Computational and Applied Mathematics Initiative, Department of Statistics, University ofChicago, Chicago, IL 60637 USA

lekheng@uchicago.edu

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