English

运筹学学报 ›› 2011, Vol. 15 ›› Issue (1): 71-84.

• 运筹学 • 上一篇    下一篇

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

冀淑慧   

  • 出版日期:2011-03-15 发布日期:2011-03-15

New SDP Relaxations  for Unconstrained  0-1 Polynomial Problems 

JI Shu-Hui   

  • Online:2011-03-15 Published:2011-03-15

PDF

1512

摘要： 本文提出了一类新的构造0-1多项式规划的半定规划(SDP)松弛方法. 我们首先利用矩阵分解和分片线性逼近给出一种新的SDP松弛, 该 松弛产生的界比标准线性松弛产生的界更紧. 我们还利用 拉格朗日松弛和平方和(SOS)松弛方法给出了一种构造Lasserre的SDP 松弛的新方法.

Abstract: 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).