Optimization Online


Correlative sparsity in primal-dual interior-point methods for LP, SDP and SOCP

Kazuhiro Kobayashi (kazuhir2***at***is.titech.ac.jp)
Sunyoung Kim (skim***at***ewha.ac.kr)
Masakazu Kojima (kojima***at***is.titech.ac.jp)

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 that is determined by the sparsity of an optimization problem (linear program, semidefinite program or second-order 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.

Keywords: Correlative sparsity, primal-dual interior-point method, linear program, semidefinite program, second-order program, partial separability, chordal graph

Category 1: Linear, Cone and Semidefinite Programming

Citation: Research Report B-434, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1-W8-29, Oh-Okayama, Meguro-ku, Tokyo 152-8552 Japan

Download: [PDF]

Entry Submitted: 09/09/2006
Entry Accepted: 09/09/2006
Entry Last Modified: 09/09/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society