Sunyoung Kim

Order-2 Tightness of Block-Sparse SOS Relaxations for One-Layer ReLU Network Verification with a Matching Input-Sharing Graph

Categories Data Science Theory, Quadratic Programming, Semi-definite Programming Tags , , , ,

Azuma, Kim, and Yamashita formulated the verification problem for one-layer ReLU networks as a quadratically constrained quadratic program and established tight semidefinite relaxations for the edgeless case and for one-unit settings. In this work, we represent the sharing pattern of undecided ReLUs over a box input set through an input-sharing graph and focus on the … Read more

Tight Conic Relaxations for Rank-one Doubly Nonnegative Matrix Completion

Categories Cone Programming, Global Optimization Applications, Quadratic Programming Tags , , , ,

We study tight conic relaxations for a quadratically constrained quadratic programming (QCQP) formulation of rank-one doubly nonnegative (DNN) matrix completion. Motivated by sparse QCQPs whose lifted matrix variables include elements not directly specified by the objective or constraints, we interpret tightness as a rank-one completion property for the unspecified elements. For sparsity patterns whose blocks … Read more

Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs

Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , , , , , ,

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 optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity … Read more

Separable QCQPs and Their Exact SDP Relaxations

Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , , ,

This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters … Read more

Tight Semidefinite Relaxations for Verifying Robustness of Neural Networks

Categories Optimization in Data Science, Quadratic Programming, Semi-definite Programming Tags , , , ,

For verifying the safety of neural networks (NNs), Fazlyab et al. (2019) introduced a semidefinite programming (SDP) approach called DeepSDP. This formulation can be viewed as the dual of the SDP relaxation for a problem formulated as a quadratically constrained quadratic program (QCQP). While SDP relaxations of QCQPs generally provide approximate solutions with some gaps, … Read more

Extending Exact Convex Relaxations of Quadratically Constrained Quadratic Programs

Categories Convex Optimization, Global Optimization, Semi-definite Programming Tags , , , ,

A convex relaxation of a quadratically constrained quadratic program (QCQP) is called exact if it has a rank-$1$ optimal solution that corresponds to an optimal solution of the  QCQP. Given a QCQP whose convex relaxation is exact,  this paper investigates the incorporation of additional quadratic inequality constraints under a non-intersecting quadratic constraint condition while maintaining … Read more

Constructing QCQP Instances Equivalent to Their SDP Relaxations

Categories Global Optimization Applications, Quadratic Programming, Semi-definite Programming Tags , ,

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 semidefinite programming (SDP) relaxations. It is well-known that the optimal value η of the SDP relaxation problem bounds the optimal value ζ  of the QCQP from below, i.e., … Read more

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

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). Sufficient conditions for the exactness of SDP relaxations for QCQPs with finitely many constraints have been extensively studied, notably by Argue … Read more

T-semidefinite programming relaxation with third-order tensors for constrained polynomial optimization

Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

We study T-semidefinite programming (SDP) relaxation for constrained polynomial optimization problems (POPs). T-SDP relaxation for unconstrained POPs was introduced by Zheng, Huang and Hu in 2022. In this work, we propose a T-SDP relaxation for POPs with polynomial inequality constraints and show that the resulting T-SDP relaxation formulated with third-order tensors can be transformed into … Read more

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

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