0-1多项式规划问题的SDP松弛方法

摘要

本文提出了一类新的构造0-1多项式规划的半定规划(SDP)松弛方法.我们首先利用矩阵分解和分片线性逼近给出一种新的SDP松弛,该松弛 产生的界比标准线性松弛产生的界更紧.我们还利用拉格朗日松弛和平方和(SOS)松弛方法给出了一种构造Lasserre的SDP松弛的新方法.%In this paper, we present new semidefinite programming (SDP)relaxation schemes for 0-1 unconstrained polynomial programming (0-1UPP) problems. We first construct an SDP relaxation based on matrix cone decomposition and (piecewise) linear approximation for (0-1UPP). It is shown that this SDP bound is tighter than the standard linear form (SLF). We then use Lagrangian dual and sum of squares (SOS) relaxation to obtain SDP relaxations which are equivalent to Lasserre's SDP relaxations for (0-1UPP). This provides a new way to derive Lasserre's hierarchy of SDP relaxations for (0-1UPP).