Session: Semidefinite Relaxations in Inference Problems
Chair: Yong Sheng Soh
Cluster: Conic and Semidefinite Optimization
Talk 1: On the exactness of SDP relaxation for quadratic assignment problem
Speaker: Shuyang Ling
Abstract: Quadratic assignment problem (QAP) is a fundamental problem in combinatorial optimization and finds numerous applications in operation research, computer vision, and pattern recognition. However, it is a very well-known NP-hard problem to find the global minimizer to the QAP. In this work, we study the semidefinite relaxation (SDR) of the QAP and investigate when the SDR recovers the global minimizer. In particular, we consider the two input matrices satisfy a simple signal-plus-noise model, and show that when the noise is sufficiently smaller than the signal, then the SDR is exact, i.e., it recovers the global minimizer to the QAP. It is worth noting that this sufficient condition is purely algebraic and does not depend on any statistical assumption of the input data. We apply our bound to several statistical models such as correlated Gaussian Wigner model. Despite the sub-optimality in theory under those models, empirical studies show the remarkable performance of the SDR. Our work could be the first step towards a deeper understanding of the SDR exactness for the QAP.
Talk 2: Exactness Conditions for Semidefinite Relaxations of the Quadratic Assignment Problem
Speaker: Junyu Chen
Abstract: The Quadratic Assignment Problem (QAP) is an important discrete optimization instance that encompasses many well-known combinatorial optimization problems, and has applications in a wide range of areas such as logistics and computer vision. The QAP, unfortunately, is NP-hard to solve. To address this difficulty, a number of semidefinite relaxations of the QAP have been developed. These techniques are known to be powerful in that they compute globally optimal solutions in many instances, and are often deployed as sub-routines within enumerative procedures for solving QAPs. In this paper, we investigate the strength of these semidefinite relaxations. Our main result is a deterministic set of conditions on the input matrices -- specified via linear inequalities -- under which these semidefinite relaxations are exact. Our result is simple to state, in the hope that it serves as a foundation for subsequent studies on semidefinite relaxations of the QAP as well as other related combinatorial optimization problems. As a corollary, we show that the semidefinite relaxation is exact under a perturbation model whereby the input matrices differ by a suitably small perturbation term. One technical difficulty we encounter is that the set of dual feasible solutions is not closed. To circumvent these difficulties, our analysis constructs a sequence of dual feasible solutions whose objective value approaches the primal objective, but never attains it.
Talk 3: Inference of planted subgraphs in random graphs
Speaker: Cheng Mao
Abstract: Suppose that we are given a graph G obtained from randomly planting a template graph in an Erdős–Rényi graph. Can we detect the presence and recover the location of the planted subgraph in G? This problem is well understood in the case where the template graph is a clique or a dense subgraph but has received less attention otherwise. We consider several settings where the planted subgraph is the power of a Hamiltonian cycle or a random geometric graph which arises in multiple applications. The difficulty of the detention or recovery problem primarily lies in the combinatorial nature of the associated optimization problem. To tackle the problem, we study computationally efficient methods such that subgraph counting and spectral methods which leverage the higher triangle density of the planted subgraph.
