Masakazu Kojima

Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Cone Programming, Semi-definite Programming Tags , , ,

    We investigate exact semidefinite programming (SDP) relaxations for the problem of minimizing a nonconvex quadratic objective function over a feasible region defined by both finitely and infinitely many nonconvex quadratic inequality constraints (semi-infinite QCQPs). Specifically, we present two sufficient conditions on the feasible region under which the QCQP, with any quadratic objective function over the … Read more

    An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c

  • Koichi Fujii
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Yuji Shinano
    • Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming Tags , , , , ,

    Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original … Read more

    Further Development in Convex Conic Reformulation of Geometric Nonconvex Conic Optimization Problems

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    A geometric nonconvex conic optimization problem (COP) was recently proposed by Kim, Kojima and Toh asa unified framework for convex conic reformulation of a class of quadratic optimization problems and polynomial optimization problems. The nonconvex COP minimizes a linear function over the intersection of a nonconvex cone K, a convex subcone J of the convex … Read more

    Equivalent Sufficient Conditions for Global Optimality of Quadratically Constrained Quadratic Program

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    We study the equivalence of several well-known sufficient optimality conditions for a general quadratically constrained quadratic program (QCQP). The conditions are classified in two categories. The first one is for determining an optimal solution and the second one is for finding an optimal value. The first category of conditions includes the existence of a saddle … Read more

    The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint

  • Koichi Fujii
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Yuji Shinano
    • Categories 0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming Tags , , , , ,

    Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48\% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which … Read more

    Strong duality of a conic optimization problem with a single hyperplane and two cone constraints

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Convex Optimization, Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags , , , ,

    Strong (Lagrangian) duality of general conic optimization problems (COPs) has long been studied and its profound and complicated results appear in different forms in a wide range of literatures. As a result, characterizing the known and unknown results can sometimes be difficult. The aim of this article is to provide a unified and geometric view … Read more

    Generating Cutting Inequalities Successively for Quadratic Optimization Problems in Binary Variables

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories 0-1 Programming, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , , , ,

    We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull of the set of the optimal solutions $\subset \{0, 1\}^n$, while the standard cutting inequalities are used for the convex hull of the feasible region. An arbitrary linear inequality with integer coefficients … Read more

    MatQapNB User Guide: A branch-and-bound program for QAPs in Matlab with the Newton-Bracketing method

  • Koichi Fujii
  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Kim-Chuan Toh
  • Yuji Shinano
    • Categories Global Optimization Applications, Optimization Software Design Principles, Quadratic Programming Tags , , ,

    MatQapNB is a MATLAB toolbox that implements a parallel branch-and-bound method using NewtBracket (the Newton bracketing method [4]) for its lower bounding procedure. It can solve small to medium scale Quadratic Assignment Problem (QAP) instances with dimension up to 30. MatQapNB was used in the numerical experiments on QAPs in the recent article “Solving challenging … Read more

    Solving Challenging Large Scale QAPs

  • Koichi Fujii
  • Naoki Ito
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Sunyoung Kim
  • Yuji Shinano
    • Categories Applications - OR and Management Sciences Tags ,

    We report our progress on the project for solving larger scale quadratic assignment problems (QAPs). Our main approach to solve large scale NP-hard combinatorial optimization problems such as QAPs is a parallel branch-and-bound method eciently implemented on a powerful computer system using the Ubiquity Generator (UG) framework that can utilize more than 100,000 cores. Lower … Read more

    User manual of NewtBracket: “A Newton-Bracketing method for a simple conic optimization problem” with applications to QOPs in binary variables

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

    We describe the Matlab package NewtBracket for solving a simple conic optimization problem that minimizes a linear objective function subject to a single linear equality constraint and a convex cone constraint. The problem is converted into the problem of finding the largest zero $y^*$ of a continuously differentiable (except at $y^*$) convex function $g : … Read more