Correlative Sparsity in Primal-Dual Interior-Point Methods for LP,SDP, and SOCP |
| |
Authors: | Kazuhiro Kobayashi Sunyoung Kim Masakazu Kojima |
| |
Institution: | (1) Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan;(2) Department of Mathematics, Ewha W. University, 11-1 Dahyun-dong, Sudaemoon-gu, Seoul, 120-750, Republic of Korea |
| |
Abstract: | 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.
S. Kim’s research was supported by Kosef R01-2005-000-10271-0 and KRF-2006-312-C00062. |
| |
Keywords: | Correlative sparsity Primal-dual interior-point method Linear program Semidefinite program Second-order cone program Partial separability Chordal graph |
本文献已被 SpringerLink 等数据库收录! |
|