Solving large-scale sparse semidefinite programs for combinatorial optimization

被引：178

作者：

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
ADLER, I
[J]. 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
FALKNER, J
RENDL, F
WOLKOWICZ, H
[J]. MATHEMATICAL PROGRAMMING, 1994, 66 (02) : 211 - 239
[8] Semidefinite programming relaxation for nonconvex quadratic programs
Fujie, T
Kojima, M
[J]. 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 →