New semidefinite programming relaxations for box constrained quadratic program

被引：6

作者：

Xia Yong ^{[1
]}

机构：

[1] Beihang Univ, Sch Math & Syst Sci, State Key Lab Software Dev Environm, LMIB,Minist Educ, Beijing 100191, Peoples R China

来源：

SCIENCE CHINA-MATHEMATICS | 2013年 / 56卷 / 04期

基金：

中国国家自然科学基金;

关键词：

box constrained quadratic program; Lagrangian dual; semidefinite programming; D; C; optimization; lower bound; zonotope; DUALITY GAP; OPTIMIZATION;

D O I：

10.1007/s11425-012-4512-x

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We establish in this paper optimal parametric Lagrangian dual models for box constrained quadratic program based on the generalized D.C. (difference between convex) optimization approach, which can be reformulated as semidefinite programming problems. As an application, we propose new valid linear constraints for rank-one relaxation.

引用

收藏

页码：877 / 886

页数：10

相关论文

共 19 条

[1] A polynomial case of unconstrained zero-one quadratic optimization [J].

Allemand, K ;

Fukuda, K ;

Liebling, TM ;

Steiner, E .

MATHEMATICAL PROGRAMMING, 2001, 91 (01) :49-52

[2] Reverse search for enumeration [J].

Avis, D ;

Fukuda, K .

DISCRETE APPLIED MATHEMATICS, 1996, 65 (1-3) :21-46

[3] Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem [J].

Cela, Eranda ;

Klinz, Bettina ;

Meyer, Christophe .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2006, 12 (03) :187-215

[4]

Edelsburunner H, 1987, ALGORITHMS COMBINATO

[5] Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm [J].

Ferrez, JA ;

Fukuda, K ;

Liebling, TM .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 166 (01) :35-50

[6] Solutions and optimality criteria to box constrained nonconvex minimization problems [J].

Gao, David Yang .

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2007, 3 (02) :293-304

[7] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].

Goemans, MX ;

Williamson, DP .

JOURNAL OF THE ACM, 1995, 42 (06) :1115-1145

[8] An improved lower bound and approximation algorithm for binary constrained quadratic programming problem [J].

Lu, Cheng ;

Wang, Zhenbo ;

Xing, Wenxun .

JOURNAL OF GLOBAL OPTIMIZATION, 2010, 48 (03) :497-508

[9] On the gap between the quadratic integer programming problem and its semidefinite relaxation [J].

Malik, U ;

Jaimoukha, IM ;

Halikias, GD ;

Gungah, SK .

MATHEMATICAL PROGRAMMING, 2006, 107 (03) :505-515

[10] Semidefinite relaxation and nonconvex quadratic optimization [J].

Nesterov, Y .

OPTIMIZATION METHODS & SOFTWARE, 1998, 9 (1-3) :141-160