| 0-1多项式规划问题的SDP松弛方法(英) |
| |
| 引用本文： | 冀淑慧.0-1多项式规划问题的SDP松弛方法(英)[J].运筹学学报,2011,15(1):71-84. |
| |
| 作者姓名： | 冀淑慧 |
| |
| 作者单位： | 复旦大学管理学院,上海,200433 |
| |
| 基金项目： | supported by the National Natural Science Foundation of China under grants 10971034 and 70832002 |
| |
| 摘 要： | 本文提出了一类新的构造0-1多项式规划的半定规划(SDP)松弛方法. 我们首先利用矩阵分解和分片线性逼近给出一种新的SDP松弛, 该 松弛产生的界比标准线性松弛产生的界更紧. 我们还利用 拉格朗日松弛和平方和(SOS)松弛方法给出了一种构造Lasserre的SDP 松弛的新方法.
|
| 关 键 词： | 运筹学 无约束0-1多项式优化 半定松弛 矩阵分解 线性松弛 |
New SDP Relaxations for Unconstrained 0-1 Polynomial Problems |
| |
| Ji Shuhui.New SDP Relaxations for Unconstrained 0-1 Polynomial Problems[J].OR Transactions,2011,15(1):71-84. |
| |
| Authors: | Ji Shuhui |
| |
| Institution: | Ji Shuhui School of Management,Fudan University,Shanghai 200433,China |
| |
| 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 w... |
| |
| Keywords: | Operations research 0-1 unconstrained polynomial optimization semidefinite relaxation matrix decomposition linear relaxation |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
