Katsuki Fujisawa

Parallel solver for semidefinite programming problem having sparse Schur complement matrix

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
  • Maho Nakata
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , ,

    SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical programming. SDP provides a practical computation framework for many research fields. Some applications, however, require solving large-scale SDPs whose size exceeds the capacity of a single processor in terms of computational time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel version) developed … Read more

    A high-performance software package for semidefinite programs: SDPA 7

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
  • Kazushige Goto
  • Kazuhiro Kobayashi
  • Maho Nakata
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , ,

    The SDPA (SemiDefinite Programming Algorithm) Project launched in 1995 has been known to provide high-performance packages for solving large-scale Semidefinite Programs (SDPs). SDPA Ver. 6 solves efficiently large-scale dense SDPs, however, it required much computation time compared with other software packages, especially when the Schur complement matrix is sparse. SDPA Ver. 7 is now completely … Read more

    User’s Manual for SparseCoLO: Conversion Methods for Sparse Conic-form Linear Optimization Problems

  • Katsuki Fujisawa
  • Sunyoung Kim
  • Masakazu Kojima
  • Y. Okamoto
  • Makoto Yamashita
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , ,

    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, … Read more

    Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Masakazu Kojima
  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , ,

    The Semidefinite Program (SDP) is a fundamental problem in mathematical programming. It covers a wide range of applications, such as combinatorial optimization, control theory, polynomial optimization, and quantum chemistry. Solving extremely large-scale SDPs which could not be solved before is a significant work to open up a new vista of future applications of SDPs. Our … Read more

    Preprocessing sparse semidefinite programs via matrix completion

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
    • Categories Semi-definite Programming Tags , , , , ,

    Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more

    A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Graphs and Matroids, Parallel Algorithms, Semi-definite Programming Tags , , , , ,

    A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of … Read more

    PHoM – a Polyhedral Homotopy Continuation Method for Polynomial Systems

  • Katsuki Fujisawa
  • Sunyoung Kim
  • Masakazu Kojima
  • Tomohiko Mizutani
  • Takayuki Gunji
  • Akiko Takeda
    • Categories Nonlinear Systems and Least-Squares Tags , , , ,

    PHoM is a software package in C++ for finding all isolated solutions of polynomial systems using a polyhedral homotopy continuation method. Among three modules constituting the package, the first module StartSystem constructs a family of polyhedral-linear homotopy functions, based on the polyhedral homotopy theory, from input data for a given system of polynomial equations $\f(\x) … Read more

    SDPARA : SemiDefinite Programming Algorithm PARAllel Version

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , , ,

    Abstract: The SDPA (SemiDefinite Programming Algorithm) is known as efficient computer software based on primal-dual interior-point method for solving SDPs (Semidefinite Programs). In many applications, however, some SDPs become larger and larger, too large for the SDPA to solve on a single processor. In execution of the SDPA applied to large scale SDPs, the computation … Read more

    Implementation and Evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0

  • Katsuki Fujisawa
  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , , ,

    The SDPA (SemiDefinite Programming Algorithm) is a software package for solving general SDPs(SemiDefinite Programs). It is written in C++ with the help of {\it LAPACK} for numerical linear algebra for dense matrix computation. The purpose of this paper is to present a brief description of the latest version of the SDPA and its high performance … Read more

    Exploiting Sparsity in Semidefinite Programming via Matrix Completion II: Implementation and Numerical Results

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Masakazu Kojima
  • Kazuo Murota
  • Kazuhide Nakata
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods. This framework is based on some results about positive semidefinite matrix completion, and it can be embodied … Read more