Masakazu Kojima

A Lagrangian-DNN Relaxation: a Fast Method for Computing Tight Lower Bounds for a Class of Quadratic Optimization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified Lagrangian-CPP relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012 takes one of the simplest forms, an unconstrained conic linear optimization problem … Read more

    Faster, but Weaker, Relaxations for Quadratically Constrained Quadratic Programs

  • Samuel Burer
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Convex Optimization, Global Optimization, Quadratic Programming Tags , , ,

    We introduce a new relaxation framework for nonconvex quadratically constrained quadratic programs (QCQPs). In contrast to existing relaxations based on semidefinite programming (SDP), our relaxations incorporate features of both SDP and second order cone programming (SOCP) and, as a result, solve more quickly than SDP. A downside is that the calculated bounds are weaker than … Read more

    Extension of Completely Positive Cone Relaxation to Polynomial Optimization

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose the moment cone relaxation for a class of polynomial optimization problems (POPs) to extend the results on the completely positive cone programming relaxation for the quadratic optimization (QOP) model by Arima, Kim and Kojima. The moment cone relaxation is constructed to take advantage of sparsity of the POPs, so that efficient numerical methods … Read more

    Parallel Implementation of Successive Sparse SDP Relaxations for Large-scale Euclidean Distance Geometry Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , ,

    The Euclidean distance geometry problem (EDGP) includes locating sensors in a sensor network and constructing a molecular configuration using given distances in the two or three-dimensional Euclidean space. When the locations of some nodes, called anchors, are given, the problem can be dealt with many existing methods. An anchor-free problem in the three-dimensional space, however, … Read more

    Simplified Copositive and Lagrangian Relaxations for Linearly Constrained Quadratic Optimization Problems in Continuous and Binary Variables

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    For a quadratic optimization problem (QOP) with linear equality constraints in continuous nonnegative variables and binary variables, we propose three relaxations in simplified forms with a parameter $\lambda$: Lagrangian, completely positive, and copositive relaxations. These relaxations are obtained by reducing the QOP to an equivalent QOP with a single quadratic equality constraint in nonnegative variables, … Read more

    A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We propose a class of quadratic optimization problems whose exact optimal objective values can be computed by their completely positive cone programming relaxations. The objective function can be any quadratic form. The constraints of each problem are described in terms of quadratic forms with no linear terms, and all constraints are homogeneous equalities, except one … Read more

    Enclosing Ellipsoids and Elliptic Cylinders of Semialgebraic Sets and Their Application to Error Bounds in Polynomial Optimization

  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    This paper is concerned with a class of ellipsoidal sets (ellipsoids and elliptic cylinders) in the m-dimensional Euclidean space which are determined by a freely chosen positive semidefinite matrix. All ellipsoidal sets in this class are similar to each other through a parallel transformation and a scaling around their centers by a constant factor. Based … Read more

    SFSDP: a Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Hayato Waki
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , ,

    SFSDP is a Matlab package for solving a sensor network localization problem. These types of problems arise in monitoring and controlling applications using wireless sensor networks. SFSDP implements the semidefinite programming (SDP) relaxation proposed in Kim et al. [2009] for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) … 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

    Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion

  • Sunyoung Kim
  • Masakazu Kojima
  • Martin Mevissen
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , ,

    A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two … Read more