3 citations · 8 across the 20 of their papers we have counts for
20 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…
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…
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…
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…
Further Development in Convex Conic Reformulation of Geometric Nonconvex Conic Optimization Problems
Naohiko Arima, Sunyoung Kim, Masakazu Kojima
A geometric nonconvex conic optimization problem (COP) was recently proposed by Kim, Kojima and Toh as a unified framework for convex conic reformulation of a class of quadratic op…
Equivalent Sufficient Conditions for Global Optimality of Quadratically Constrained Quadratic Program
Sunyoung Kim, Masakazu Kojima
We study the equivalence of several well-known sufficient optimality conditions for a general quadratically constrained quadratic program (QCQP). The conditions are classified in t…
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 +2
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 u…
Exact SDP relaxations for quadratic programs with bipartite graph structures
Godai Azuma, Mituhiro Fukuda, Sunyoung Kim +1
For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact fo…
Strong duality of a conic optimization problem with a single hyperplane and two cone constraints
Sunyoung Kim, Masakazu Kojima
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 o…
Generating Cutting Inequalities Successively for Quadratic Optimization Problems in Binary Variables
Sunyoung Kim, Masakazu Kojima
We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull…
Solving Challenging Large Scale QAPs
Koichi Fujii, Naoki Ito, Sunyoung Kim +3
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 probl…
Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
Godai Azuma, Mituhiro Fukuda, Sunyoung Kim +1
We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data ma…
A Newton-bracketing method for a simple conic optimization problem
Sunyoung Kim, Masakazu Kojima, Kim-Chuan Toh
For the Lagrangian-DNN relaxation of quadratic optimization problems (QOPs), we propose a Newton-bracketing method to improve the performance of the bisection-projection method imp…
Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures
Sunyoung Kim, Masakazu Kojima, Kim-Chuan Toh
We study the equivalence among a nonconvex QOP, its CPP and DNN relaxations under the assumption that the aggregated and correlative sparsity of the data matrices of the CPP relaxa…
A Geometrical Analysis of a Class of Nonconvex Conic Programs for Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems
Sunyoung Kim, Masakazu Kojima, Kim-Chuan Toh
We present a geometrical analysis on the completely positive programming reformulation of quadratic optimization problems and its extension to polynomial optimization problems with…
A dual spectral projected gradient method for log-determinant semidefinite problems
Takashi Nakagaki, Mituhiro Fukuda, Sunyoung Kim +1
We extend the result on the spectral projected gradient method by Birgin et al. in 2000 to a log-determinant semidefinite problem (SDP) with linear constraints and propose a spectr…
Solving Pooling Problems by LP and SOCP Relaxations and Rescheduling Methods
Masaki Kimizuka, Sunyoung Kim, Makoto Yamashita
The pooling problem is an important industrial problem in the class of network flow problems for allocating gas flow in pipeline transportation networks. For P-formulation of the p…
BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints
Naoki Ito, Sunyoung Kim, Masakazu Kojima +2
The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (…