Solving large-scale sparse semidefinite programs for combinatorial optimization

被引：180

作者：

Benson, SJ ^{[3
]}

Ye, YY

Zhang, X

机构：

[1] Univ Iowa, Dept Management Sci, Iowa City, IA 52242 USA

[2] Huazhong Univ Sci & Technol, Sch Mech Engn, Wuhan 430074, Hubei, Peoples R China

[3] Univ Iowa, Computat Optimizat Lab, Iowa City, IA 52242 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 2000年 / 10卷 / 02期

关键词：

semidefinite programming; dual potential reduction algorithm; maximum cut problem;

D O I：

10.1137/S1052623497328008

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present a dual-scaling interior-point algorithm and show how it exploits the structure and sparsity of some large-scale problems. We solve the positive semidefinite relaxation of combinatorial and quadratic optimization problems subject to boolean constraints. We report the first computational results of interior-point algorithms for approximating maximum cut semidefinite programs with dimension up to 3,000.

引用

页码：443 / 461

页数：19

共 36 条

[1] CORRECTION [J].

ADLER, I .

MATHEMATICAL PROGRAMMING, 1991, 50 (03) :415-415

[2]

Alizadeh F, 1994, 659 NEW YORK U COMP

[3]

ALIZADEH F, 1991, THESIS U MINNESOTA M

[4]

ANSTREICHER KM, 1996, LONG STEP PATH FOLLO

[5]

Atkinson K. E., 1989, INTRO NUMERICAL ANAL

[6]

DUFF IS, 1997, STATE ART NUMERICAL, P27

[7] A COMPUTATIONAL STUDY OF GRAPH PARTITIONING [J].

FALKNER, J ;

RENDL, F ;

WOLKOWICZ, H .

MATHEMATICAL PROGRAMMING, 1994, 66 (02) :211-239

[8] Semidefinite programming relaxation for nonconvex quadratic programs [J].

Fujie, T ;

Kojima, M .

JOURNAL OF GLOBAL OPTIMIZATION, 1997, 10 (04) :367-380

[9]

FUJISAWA K, 1997, B324 TOK I TECHN DEP

[10]

FUJISAWA K, 1997, B330 TOK I TECHN DEP

← 1 2 3 4 →