TY - JOUR
T1 - Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP
AU - Kobayashi, Kazuhiro
AU - Kim, Sunyoung
AU - Kojima, Masakazu
N1 - Funding Information:
S. Kim’s research was supported by Kosef R01-2005-000-10271-0 and KRF-2006-312-C00062.
PY - 2008/8
Y1 - 2008/8
N2 - Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient matrix of the equation which is determined by the sparsity of an optimization problem (linear program, semidefinite program or second-order cone program). We show if an optimization problem is correlatively sparse, then the coefficient matrix of the Schur complement equation inherits the sparsity, and a sparse Cholesky factorization applied to the matrix results in no fill-in.
AB - Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient matrix of the equation which is determined by the sparsity of an optimization problem (linear program, semidefinite program or second-order cone program). We show if an optimization problem is correlatively sparse, then the coefficient matrix of the Schur complement equation inherits the sparsity, and a sparse Cholesky factorization applied to the matrix results in no fill-in.
KW - Chordal graph
KW - Correlative sparsity
KW - Linear program
KW - Partial separability
KW - Primal-dual interior-point method
KW - Second-order cone program
KW - Semidefinite program
UR - http://www.scopus.com/inward/record.url?scp=49049088376&partnerID=8YFLogxK
U2 - 10.1007/s00245-007-9030-9
DO - 10.1007/s00245-007-9030-9
M3 - Article
AN - SCOPUS:49049088376
VL - 58
SP - 69
EP - 88
JO - Applied Mathematics and Optimization
JF - Applied Mathematics and Optimization
SN - 0095-4616
IS - 1
ER -