Learning to relax nonconvex quadratically constrained quadratic programs

Quadratically constrained quadratic programs (QCQPs) are commonly encounteredin diverse disciplines like operations research, machine learning, power systems, andportfolio optimization. The solution of these non-convex problems is difficult sincethey are characterized by their NP-hard nature. Conventional methods employ eitherSemidefinite Programming (SDP) or Linear Programming (LP) relaxations;each of these methods is highly effective for certain subsets of problems and exhibitspoor performance for others. However, there is a lack of comprehensive understanding.This thesis seeks to create a relaxation selection procedure for QCQPs thattakes into account the structure of the problem. It intends to determine if an SDPorLP-based strategy is more beneficial based on the instance structure.We explore the spectral properties and sparsity patterns of data matrices to unravelthe structural properties of a QCQP instance. Our study is based on the generationof QCQP samples, along with an exploratory analysis of the dataset, and applyingmachine learning to classify the obtained instances by the most favorable relaxationtechnique.The main contribution of this work is to develop machine learning models that canaccurately predict ex-ante whether an SDP or LP relaxation will yield a tighterbound on new QCQP instances. These models are trained on features created fromthe spectral properties and sparsity patterns of the data matrices. This predictive capability increases the efficiency of solving non-convex QCQPs by guiding theselection of the most suitable relaxation method.