Title   name
KSIAM 2006 Annual Meeting
 
  Title
  Speaker   Kim, Sunyoung  
  Date 2006-11-25
  Host
  Place 건국대학교
  File  의 1 번째 Real Media 동영상입니다. 의 1 번째 강연자료입니다.
 
Abstract : Exploiting sparsity has been a key issue in solving large-scale optimization pro blems. The mosttime-consuming part of primal-dual interior-point methods for linear programs, second-ordercone programs, and semidefinite programs is solving the Schur complement equation at eachiteration, usually by the Cholesky factorization. The computational efficiency is greatly affectedby the sparsity of the coefficient matrix of the equation that is determined by the sparsity ofan optimization problem (linear program, semidefinite program or second-order program). Weshow if an optimization problem is correlatively sparse, then the coefficient matrix of the Schurcomplement equation inherits the sparsity, and a sparse Cholesky factorization applied to thematrix results in no fill-in.