Ellipsoidal approach to box-constrained quadratic problems

被引：17

作者：

De Angelis, PL ^{[1
]}

Bomze, IM

Toraldo, G

机构：

[1] Univ Naples PARTHENOPE, Inst Stat & Math, Naples, Italy

[2] Univ Vienna, Dept Stat & Decis Support Syst, Vienna, Austria

[3] CNR, CPS, I-80125 Naples, Italy

[4] Univ Naples Federico II, Dept Agr Engn & Agron, Naples, Italy

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2004年 / 28卷 / 01期

关键词：

nonconvex quadratic programming; ellipsoidal constraints; global optimization;

D O I：

10.1023/B:JOGO.0000006654.34226.fe

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present a new heuristic for the global solution of box constrained quadratic problems, based on the classical results which hold for the minimization of quadratic problems with ellipsoidal constraints. The approach is tested on several problems randomly generated and on graph instances from the DIMACS challenge, medium size instances of the Maximum Clique Problem. The numerical results seem to suggest some effectiveness of the proposed approach.

引用

页码：1 / 15

页数：15

共 20 条

[1] Finding independent sets in a graph using continuous multivariable polynomial formulations [J].

Abello, J ;

Butenko, S ;

Pardalos, PM ;

Resende, MGC .

JOURNAL OF GLOBAL OPTIMIZATION, 2001, 21 (02) :111-137

[2]

[Anonymous], CLIQUES COLORING SAT

[3] Global optimality conditions for quadratic optimization problems with binary constraints [J].

Beck, A ;

Teboulle, M .

SIAM JOURNAL ON OPTIMIZATION, 2000, 11 (01) :179-188

[4]

BOMZE IM, 1997, DEV GLOBAL OPTIMIZAT, P95

[5]

BOMZE IM, 2001, IN PRESS DISCRETE AP

[6]

Bomze IM, 1999, Handbook of Combinatorial Optimization, P1, DOI DOI 10.1007/978-1-4757-3023-4_1

[7]

DANNINGER G, 1994, GEN CONVEXITY, P137

[8]

DeAngelis Pasquale., 1997, Nonconvex Optimization and Its Applications, V18, P73

[9]

Han C. G., 1992, INFORMATICA, V3, P474

[10] TEST-CASE GENERATORS AND COMPUTATIONAL RESULTS FOR THE MAXIMUM CLIQUE PROBLEM [J].

HASSELBERG, J ;

PARDALOS, PM ;

VAIRAKTARAKIS, G .

JOURNAL OF GLOBAL OPTIMIZATION, 1993, 3 (04) :463-482

← 1 2 →