An interior-point method for semidefinite programming

被引：478
作者：
Helmberg, C
Rendl, F
Vanderbei, RJ
Wolkowicz, H
机构：
[1] PRINCETON UNIV,SCH ENGN & APPL SCI,PRINCETON,NJ 08544
[2] UNIV WATERLOO,DEPT COMBINATOR & OPTIMIZAT,WATERLOO,ON N2L 3G1,CANADA
来源：
SIAM JOURNAL ON OPTIMIZATION | 1996年 / 6卷 / 02期
关键词：
semidefinite programming; interior-point methods; max-cut relaxations; max-min eigenvalue problems;
D O I：
10.1137/0806020
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We propose a new interior-point-based method to minimize a linear function of a matrix variable subject to linear equality and inequality constraints over the set of positive semidefinite matrices. We show that the approach is very efficient for graph bisection problems such as max-cut. Other applications include max-min eigenvalue problems and relaxations for the stable set problem.
引用
收藏
页码：342 / 361
页数：20
相关论文
共 30 条
[21]   LARGE-SCALE OPTIMIZATION OF EIGENVALUES [J].
Overton, Michael L. .
SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (01) :88-120
[22]   ON MINIMIZING THE MAXIMUM EIGENVALUE OF A SYMMETRIC MATRIX [J].
OVERTON, ML .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1988, 9 (02) :256-268
[23]   2ND DERIVATIVES FOR OPTIMIZING EIGENVALUES OF SYMMETRICAL MATRICES [J].
OVERTON, ML ;
WOMERSLEY, RS .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1995, 16 (03) :697-718
[24]   NONPOLYHEDRAL RELAXATIONS OF GRAPH-BISECTION PROBLEMS [J].
POLJAK, S ;
RENDL, F .
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (03) :467-487
[25]  
Rendi F., 1995, OPTIM METHODS SOFTW, V5, P1
[26]   A VERSION OF THE BUNDLE IDEA FOR MINIMIZING A NONSMOOTH FUNCTION: CONCEPTUAL IDEA, CONVERGENCE ANALYSIS, NUMERICAL RESULTS [J].
Schramm, Helga ;
Zowe, Jochem .
SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (01) :121-152
[27]   A PRIMAL-DUAL POTENTIAL REDUCTION METHOD FOR PROBLEMS INVOLVING MATRIX INEQUALITIES [J].
VANDENBERGHE, L ;
BOYD, S .
MATHEMATICAL PROGRAMMING, 1995, 69 (01) :205-236
[28]   SYMMETRICAL INDEFINITE SYSTEMS FOR INTERIOR POINT METHODS [J].
VANDERBEI, RJ ;
CARPENTER, TJ .
MATHEMATICAL PROGRAMMING, 1993, 58 (01) :1-32
[29]  
VIAL JP, 1994, OPTIMIZATION METHODS, V3, P285
[30]   SOME APPLICATIONS OF OPTIMIZATION IN MATRIX-THEORY [J].
WOLKOWICZ, H .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1981, 40 (OCT) :101-118
123