Masakazu Kojima

Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Second-Order Cone Programming, Semi-definite Programming Tags , , ,

    We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S.~Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of objective quadratic functions and diagonal coefficient matrices … Read more

    Lagrangian dual interior-point methods for semidefinite programs

  • Mituhiro Fukuda
  • Masakazu Kojima
  • Masayuki Shida
    • Categories Convex Optimization, Second-Order Cone Programming, Semi-definite Programming Tags , , , , , , , ,

    This paper proposes a new predictor-corrector interior-point method for a class of semidefinite programs, which numerically traces the central trajectory in a space of Lagrange multipliers. The distinguished features of the method are full use of the BFGS quasi-Newton method in the corrector procedure and an application of the conjugate gradient method with an effective … 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