Masakazu Kojima

A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part I: Proposed Approach and Application to Semidefinite Programming

  • Yoshihiro Kanno
  • Masakazu Kojima
  • Kazuo Murota
  • Sadayoshi Kojima
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    Motivated by recent interest in group-symmetry in semidefinite programming, we propose a numerical method for finding a finest simultaneous block-diagonalization of a finite number of matrices, or equivalently the irreducible decomposition of the generated matrix *-algebra. The method is composed of numerical-linear algebraic computations such as eigenvalue computation, and automatically makes full use of the … Read more

    Efficient Evaluation of Polynomials and Their Partial Derivatives in Homotopy Continuation Methods

  • Masakazu Kojima
    • Categories Branch and Cut Algorithms, Other Topics Tags , ,

    The aim of this paper is to study how efficiently we evaluate a system of multivariate polynomials and their partial derivatives in homotopy continuation methods. Our major tool is an extension of the Hornor scheme, which is popular in evaluating a univariate polynomial, to a multivariate polynomial. But the extension is not unique, and there … Read more

    Correlative sparsity in primal-dual interior-point methods for LP, SDP and SOCP

  • Sunyoung Kim
  • Masakazu Kojima
  • Kazuhiro Kobayashi
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient … Read more

    Recognizing Underlying Sparsity in Optimization

  • Sunyoung Kim
  • Masakazu Kojima
  • Philippe L. Toint
    • Categories Combinatorial Optimization, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem’s functions can be improved by performing a nonsingular linear transformation in the space corresponding … Read more

    Dynamic Enumeration of All Mixed Cells

  • Masakazu Kojima
  • Tomohiko Mizutani
  • Akiko Takeda
    • Categories 0-1 Programming, Branch and Cut Algorithms, Polyhedra Tags , , , ,

    The polyhedral homotopy method, which has been known as a powerful numerical method for computing all isolated zeros of a polynomial system, requires all mixed cells of the support of the system to construct a family of homotopy functions. Finding the mixed cells is formulated in terms of a linear inequality system with an additional … Read more

    A Note on Sparse SOS and SDP Relaxations for Polynomial Optimization Problems over Symmetric Cones

  • Masakazu Kojima
  • Masakazu Muramatsu
    • Categories Constrained Nonlinear Optimization, Global Optimization, Semi-definite Programming Tags , , , , , ,

    This short note extends the sparse SOS (sum of squares) and SDP (semidefinite programming) relaxation proposed by Waki, Kim, Kojima and Muramatsu for normal POPs (polynomial optimization problems) to POPs over symmetric cones, and establishes its theoretical convergence based on the recent convergence result by Lasserre on the sparse SOS and SDP relaxation for normal … 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

    SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Global Optimization, Optimization Software and Modeling Systems, Semi-definite Programming Tags , , , , ,

    SparesPOP is a MATLAB implementation of a sparse semidefinite programming (SDP) relaxation method proposed for polynomial optimization problems (POPs) in the recent paper by Waki et al. The sparse SDP relaxation is based on a hierarchy of LMI relaxations of increasing dimensions by Lasserre, and exploits a sparsity structure of polynomials in POPs. The efficiency … Read more

    Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity

  • Sunyoung Kim
  • Masakazu Kojima
  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Constrained Nonlinear Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) … Read more

    An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones

  • Masakazu Kojima
  • Masakazu Muramatsu
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , , , , ,

    This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let ${\cal E}$ and ${\cal E}_+$ be a finite dimensional real vector space and a symmetric cone embedded in ${\cal E}$; examples of $\calE$ and $\calE_+$ include a pair of the … Read more