SDP の前処理 (SparseCoLO)

以下の SDP 用の疎性を利用した前処理ツール SparseCoLO が公開されることになった。

http://www.is.titech.ac.jp/~kojima/SparseCoLO/SparseCoLO.htm

全部の SDP に対して有効ではないが、この conversion が有効な問題の特性はだいだい掴むことができる。

1: 現在は MATLAB のプログラムだが、C/C++ に変更した方が高速化、汎用性の向上が期待できる。MATLAB を C/C++ のソースに直すのではなく、一から作り直した方が長期的には得になる
2: SDPA Online Solver の中にこの前処理のプログラムを入れてしまうのも良さそう。

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.