Linear Programming on the Stiefel Manifold
首次研究施蒂费尔流形上的线性规划问题，目标是在正交向量组上最小化线性函数并满足额外线性约束。发现当p≤n-k时存在精确半定松弛，且在一定条件下局部最优性条件可保证全局最优。
.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 \(\mathbb{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\le n-k\), which is tight when \(p=1\). Surprisingly, we can greatly strengthen this sufficient exactness condition to \(p\le n-k\), which covers the classical case \(p\le 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\le n-k\).Keywordslinear programmingStiefel manifoldquadratically constrained quadratic optimizationsemidefinite programmingoptimality conditionsMSC codes90C2690C2290C4690C20