Exploiting sparsity in primal-dual interior-point methods for semidefinite programming

被引：90

作者：

Fujisawa, K

Kojima, M

Nakata, K

机构：

[1] Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology, Tokyo 152, 2-12-1 Oh-Okayama, Meguro-ku

来源：

MATHEMATICAL PROGRAMMING | 1997年 / 79卷 / 1-3期

关键词：

interior-point methods; semidefinite programming; sparsity;

D O I：

10.1007/BF02614319

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro and Nesterov-Todd search directions have been used in many primal-dual interior-point methods for semidefinite programs. This paper proposes an efficient method for computing the two directions when the semidefinite program to be solved is large scale and sparse. (C) 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

引用

页码：235 / 253

页数：19

共 21 条

[1]

ALIZADEH F, 1994, PRIMAL DUAL INTERIOR

[2]

ALIZADEH F, IN PRESS SIAM J OPTI

[3]

Boyd S., 1994, SIAM

[4]

BRIXIUS N, 1996, 971996 U IOW DEPT MA

[5]

FUJISAWA K, 1996, SDPA SEMIDEFINITE PR

[6] An interior-point method for semidefinite programming [J].

Helmberg, C ;

Rendl, F ;

Vanderbei, RJ ;

Wolkowicz, H .

SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (02) :342-361

[7] Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices [J].

Kojima, M ;

Shindoh, S ;

Hara, S .

SIAM JOURNAL ON OPTIMIZATION, 1997, 7 (01) :86-125

[8]

KOJIMA M, IN PRESS MATH PROGRA

[9]

LIN CJ, 1996, INF ATL FALL M

[10]

LIN CJ, 1995, PREDICTOR CORRECTOR

← 1 2 3 →