科研进展
多项式优化问题新进展(王杰等)
发布时间:2022-11-07 |来源:

  多项式优化是目标函数和约束条件均由多项式给出的一类非凸优化问题。因其强大的建模能力和与实代数几何密切的内在联系,多项式优化正受到越来越多研究者的关注,广泛地应用于最优电力流、信号处理、计算机视觉、组合优化、神经网络、量子信息等许多不同的领域。2001年,法国数学家Lasserre对多项式优化提出了Moment-SOS分层的求解框架,即用一系列半定松弛问题逼近多项式优化问题,紧性条件下可以在有限步内取到全局最优值(解)。然而Moment-SOS分层给出的半定松弛问题的大小随原问题的规模增长非常快,在实际应用中面临着严重的可拓展性的问题。近期,数学机械化实验室王杰副研究员与法国国家科学中心Lasserre教授等人合作,从两方面提高了Moment-SOS分层的可拓展性:一是利用多项式优化问题描述中的项稀疏性,结合经典的变量稀疏性,建立了基于变量-项联合稀疏性的Moment-SOS分层,在最优电力流问题上得到了成功的应用;二是证明了任何紧集上的多项式优化问题的Moment松弛问题均具有常数迹性质,并基于此性质设计了更加高效的一阶求解算法。

  这两项工作揭示了多项式优化问题Moment-SOS分层蕴含的新结构,为提高Moment-SOS分层的可拓展性提供了新的角度,将有效推动多项式优化在实际问题中的应用。

  [1] CS-TSSOS: Correlative and Term Sparsity for Large-Scale Polynomial Optimization, Jie Wang, Victor Magron, Jean-Bernard Lasserre and Ngoc Hoang Anh Mai. To appear in ACM Transactions on Mathematical Software, 2022.
  [2] Exploiting Constant Trace Property in Large-Scale Polynomial Optimization, Ngoc Hoang Anh Mai, Jean-Bernard Lasserre, Victor Magron and Jie Wang. To appear in ACM Transactions on Mathematical Software, 2022.

附件下载:

    联系我们
    参考
    相关文章