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

    Computing All Nonsingular Solutions of Cyclic-n Polynomial Using Polyhedral Homotopy Continuation Methods

  • Yang Dai
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Other Topics Tags , , , ,

    All isolated solutions of the cyclic-n polynomial equations are not known for larger dimensions than 11. We exploit two types of symmetric structures in the cyclic-n polynomial to compute all isolated nonsingular solutions of the equations efficiently by the polyhedral homotopy continuation method and to verify the correctness of the generated approximate solutions. Numerical results … 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