Linear Programming on the Stiefel Manifold

.Linear programming on the Stiefel manifold (LPS) is studied for the first time. It aims at minimizing a linear objective function over the set of all \(p\)-tuples of orthonormal vectors in \(R^n\) satisfying \(k\) additional linear constraints. Despite the classical polynomial-time solvable case \(k=0\), general (LPS) is NP-hard. According to the Shapiro–Barvinok–Pataki theorem, (LPS) admits an exact semidefinite programming relaxation when \(p(p+1)/2≤ n-k\), which is tight when \(p=1\). Surprisingly, we can greatly strengthen this sufficient exactness condition to \(p≤ n-k\), which covers the classical case \(p≤ n\) and \(k=0\). Regarding (LPS) as a smooth nonlinear programming problem, we reveal a nice property that under the linear independence constraint qualification, the standard first- and second-order local necessary optimality conditions are sufficient for global optimality when \(p+1≤ n-k\).