6 papers
Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs
Masakazu Kojima, Sunyoung Kim, Naohiko Arima
We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an o…
Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints
Naohiko Arima, Sunyoung Kim, Masakazu Kojima
We investigate exact semidefinite programming (SDP) relaxations for the problem of minimizing a nonconvex quadratic objective function over a feasible region defined by both finite…
Separable QCQPs and Their Exact SDP Relaxations
Masakazu Kojima, Sunyoung Kim, Naohiko Arima
This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger s…
Extending Exact Convex Relaxations of Quadratically Constrained Quadratic Programs
Masakazu Kojima, Sunyoung Kim, Naohiko Arima
A convex relaxation of a quadratically constrained quadratic program (QCQP) is called exact if it has a rank- optimal solution that corresponds to an optimal solution of the QCQ…
Constructing QCQP Instances Equivalent to Their SDP Relaxations
Masakazu Kojima, Naohiko Arima, Sunyoung Kim
General quadratically constrained quadratic programs (QCQPs) are challenging to solve as they are known to be NP-hard. A popular approach to approximating QCQP solutions is to use…
An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c
Koichi Fujii, Sunyoung Kim, Masakazu Kojima +2
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 optimiz…