(Conversion Methods for SPARSE COnic-form Linear Optimization)

K. Fujisawa, S. Kim, M. Kojima, Y. Okamoto and M. Yamashita

February 12, 2008

Revised April, 2010

SparseCoLO is a Matlab package for implementing the four conversion methods, proposed by Kim, Kojima, Mevissen and Yamashita, via positive semidefinite matrix completion for an optimization problem with matrix inequalities satisfying a sparse chordal graph structure. It is based on quite a general description of optimization problem including both primal and dual form of linear, semidefinite, second-order cone programs with equality/inequality constraints. Among the four conversion methods,  two methods utilize the domain-space sparsity  of a semidefinite matrix  variable  and the other two methods the range-space sparsity of a  linear matrix inequality (LMI) constraint of the given problem. SparseCoLO can be used as a preprocessor to reduce the size of the given problem before applying semidefinite programming solvers.

Paper: S. Kim, M. Kojima, M. Mevissen, and M. Yamashita , "Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion," Research Report B-452, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, Japan.

We are collecting instances of sparse linear optimization problems (LOPs) to evaluate and improve the performance of SparseCoLO. Any instances of sparse LOPs that you could send us to

kojima.m.aa-sparsecolo ''insert at''

would be very much appreciated.

SparseCoLO is now distributed under the GNU GPL (General Public License) v2.

If you have any question, please send a message to kojima.m.aa-sparsecolo ''insert at''