2024年11月11日 星期一 登录 EN

学术活动
Linear Programming on the Stiefel Manifold
首页 - 学术活动
报告人:
Yong Xia, Professor, Beihang University
邀请人:
Xin Liu, Professor
题目:
Linear Programming on the Stiefel Manifold
时间地点:
15:30-16:30 November 7 (Tuesday), Z311
摘要:

我们研究Stiefel流形上线性规划(LPS):其目标是线性函数,变量是p个n维空间正交向量(即Stiefel流形约束,p<=n),额外再满足k个线性约束。据我们所知,该模型首次被研究。k=0的(LPS)是一个经典的多项式可解问题。

对一般的k该问题是NP-难。若采用经典的Shapiro-Barvinok-Pataki定理分析,当p(p+1)/2<=n-k时,(LPS)多项式可解。

我们惊讶地发现,该充分条件可以被改进到p<=n-k,从而当k=0时新的充分条件自动满足。这蕴含着Stiefel流形一个新的神奇性质。

此外,我们还可证明,非凸优化问题(LPS)在LICQ成立时,当p+1<=n-k时,满足标准二阶必要条件的解是全局最优解,从而所有局部解都是全局解。