MSc.Thesis Defense:Mebrure Buket Özen

LEARNING TO RELAX NONCONVEX QUADRATICALLY

CONSTRAINED QUADRATIC PROGRAMS

M. BUKET ÖZEN
Industrial Engineering, MSc. Thesis, 2014

Thesis Jury

Assoc. Prof. Burak Kocuk (Thesis Advisor),

 Prof. İsmail Kuban Altınel,

Asst. Prof. Sinan Yıldırım

Date & Time: July 19, 2024 – 1 PM

Place: FENS L067

Keywords : quadratically constrained quadratic program, linear programming

relaxations, semidefinite programming relaxations, global optimization, machine

learning, classification, regression

Abstract

Quadratically constrained quadratic programs (QCQPs) are commonly encountered in diverse disciplines like operations research, machine learning, power systems, and portfolio optimization. The solution of these non-convex problems is difficult since they are characterized by their NP-hard nature. Conventional methods employ either Semidefinite Programming (SDP) or Linear Programming (LP) relaxations; each of these methods is highly effective for certain subsets of problems and exhibits poor performance for others. However, there is a lack of comprehensive understanding. This thesis seeks to create a relaxation selection procedure for QCQPs that takes into account the structure of the problem. It intends to determine if an SDP- or LP-based strategy is more beneficial based on the instance structure.

We explore the spectral properties and sparsity patterns of data matrices to unravel the structural properties of a QCQP instance. Our study is based on the generation of QCQP samples, along with an exploratory analysis of the dataset, and applying machine learning to classify the obtained instances by the most favorable relaxation technique.


The main contribution of this work is to develop machine learning models that can accurately predict ex-ante whether an SDP or LP relaxation will yield a tighter bound on new QCQP instances. These models are trained on features created from the spectral properties and sparsity patterns of the data matrices. This predictive capability increases the efficiency of solving non-convex QCQPs by guiding the selection of the most suitable relaxation method.