Semidefinite programming relaxation for nonconvex quadratic programs

被引：94

作者：

Fujie, T ^{[1
]}

Kojima, M ^{[1
]}

机构：

[1] TOKYO INST TECHNOL,DEPT MATH & COMP SCI,MEGURO KU,TOKYO 152,JAPAN

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 1997年 / 10卷 / 04期

关键词：

semidefinite program; relaxation method; interior-point method; nonconvex quadratic program; linear matrix inequality;

D O I：

10.1023/A:1008282830093

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper applies the SDP (semidefinite programming) relaxation originally developed for a 0-1 integer program to a general nonconvex QP (quadratic program) having a linear objective function and quadratic inequality constraints, and presents some fundamental characterizations of the SDP relaxation including its equivalence to a relaxation using convex-quadratic valid inequalities for the feasible region of the QP.

引用

页码：367 / 380

页数：14

共 29 条

[1] INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].