Quadratization and convexification in polynomial binary optimization

doi:10.1007/s10878-025-01334-y

Quadratization and convexification in polynomial binary optimization

2025-10-05

0

PRE

AI

Elisabeth Rodríguez-Heck

DOI：10.1007/s10878-025-01334-y

原文链接

原文求助

摘要

En 中文

本文中，我们讨论了关于在二进制变量中极小化多项式（P）问题的几种重新表述和求解方法。我们回顾并整合了不同的文献流派，以描述一种由三个不同阶段组成的方法论，并为每个阶段提供了几种可能的变体。第一阶段确定了对每个感兴趣的单项式进行递归分解，将其分解为子单项式对，直至初始变量。该分解产生了一种所谓的二次化方案。第二阶段基于给定的二次化方案构建（P）的二次重新表述，通过为方案中出现的每个子单项式关联一个新的辅助变量实现。通过强制辅助变量与其所表示的单项式之间的关系（无论是通过线性约束还是通过目标函数中的惩罚项），得到（P）的二次重新表述。所得到的二次问题（QP）在一般情况下是非凸的，仍然难以求解。在这一阶段，我们引入了解决过程的第三阶段，即凸化（QP）。我们考虑了不同类型的凸化方法，包括完全线性化或二次凸重新表述。不同阶段的数学性质被正式建立，并阐明了一些它们之间的关系。最后，我们展示了一些实验结果，这些结果阐明了讨论内容，并支持二次重新表述方法的实际相关性。

Keyword:

Nonlinear binary optimization

Quadratic binary optimization

Reformulation

Convexification

Quadratization and convexification in polynomial binary optimization

摘要

期刊

机构