论文标题
通过从可变边界得出的约束加强SONC放松
Strengthening SONC Relaxations with Constraints Derived from Variable Bounds
论文作者
论文摘要
多项式非阴性证书可用于获得多项式优化问题的紧密双重界限。我们考虑了非负电路（SONC）多项式证书的总和，这非常适合稀疏问题，因为计算成本仅取决于多项式中的项数，并且不取决于多项式的程度。这项工作是将基于SONC的多项式问题放松纳入分支结合算法的第一步。为此，为了更好地利用可变界限，扩大了受约束优化问题的SONC放松，因为此属性是在分支和界定的背景下成功放松的关键。计算实验表明，所提出的扩展对于使SONC弛豫适用于最受限的多项式优化问题以及整合两种方法至关重要。
Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches.
