Parallel solver for semidefinite programming problem having sparse Schur complement matrix

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

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

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

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

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

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

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

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

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

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