Improved Convex and Concave Relaxations of Composite Bilinear Forms
Improved Convex and Concave Relaxations of Composite Bilinear Forms
复制标题
DOI：
10.1007/s10957-023-02196-2
复制
发表时间：
2023-03
影响因子：
1.9
通讯作者：
Matthew E. Wilhelm;M. D. Stuber
中科院分区：
文献类型：
--
作者：
Matthew E. Wilhelm;M. D. Stuber
确定性非凸优化求解器通过利用底层因子表示生成非凸函数的凸松弛。一种方法是引入分配给每个因素的辅助变量，将问题提升到更高维度的决策空间。相比之下，广义McCormick松弛方法提供了在原始问题的低维空间中构造松弛而不引入辅助变量的显著优势，通常被称为“简化空间”方法。最近的贡献说明了如何在可因式规划中使用附加的非平凡不等式约束来收紧泛在双线性项的松弛。在这项工作中，我们利用麦考密克松弛和可因子规划的类似表示来表述原始决策空间中的更紧松弛。当先验的凸/凹松弛已知为中间双线性项时，我们发展了基本理论来产生必要的更紧密的简化空间McCormick松弛。然后，我们展示了这些规则如何通过三种不同的方法在麦考密克松弛方案中推广：使用与仿射算法耦合的麦考密克松弛，由次梯度隐含的仿射松弛的传播，以及直接使用每个因素松弛的枚举方法。开发的方法在使用EAGO的优化问题库上进行了基准测试。杰的优化器。还考虑了两个案例研究来展示这些发展：在先进制造中的应用，以优化供应链质量指标，以及在动力学机制的严格模型验证的全局动态优化应用。所提出的亚梯度方法使所考虑的问题达到全局最优所需的CPU时间得到改善。
Deterministic nonconvex optimization solvers generate convex relaxations of nonconvex functions by making use of underlying factorable representations. One approach introduces auxiliary variables assigned to each factor that lifts the problem into a higher-dimensional decision space. In contrast, a generalized McCormick relaxation approach offers the significant advantage of constructing relaxations in the lower dimensionality space of the original problem without introducing auxiliary variables, often referred to as a “reduced-space” approach. Recent contributions illustrated how additional nontrivial inequality constraints may be used in factorable programming to tighten relaxations of the ubiquitous bilinear term. In this work, we exploit an analogous representation of McCormick relaxations and factorable programming to formulate tighter relaxations in the original decision space. We develop the underlying theory to generate necessarily tighter reduced-space McCormick relaxations when a priori convex/concave relaxations are known for intermediate bilinear terms. We then show how these rules can be generalized within a McCormick relaxation scheme via three different approaches: the use of a McCormick relaxations coupled to affine arithmetic, the propagation of affine relaxations implied by subgradients, and an enumerative approach that directly uses relaxations of each factor. The developed approaches are benchmarked on a library of optimization problems using the EAGO.jl optimizer. Two case studies are also considered to demonstrate the developments: an application in advanced manufacturing to optimize supply chain quality metrics and a global dynamic optimization application for rigorous model validation of a kinetic mechanism. The presented subgradient method leads to an improvement in CPU time required to solve the considered problems to-global optimality.