Fatma Kilinc-Karzan, Carnegie Mellon University

Exactness in SDP Relaxations of Quadratically Constrained Quadratic Programs
Date
Nov 20, 2020, 11:00 am12:30 pm
Event Description

Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems. In a QCQP, we are asked to minimize a (possibly nonconvex) quadratic function subject to a number of (possibly nonconvex) quadratic constraints. Such problems arise naturally in many areas of operations research, computer science, and engineering. Although QCQPs are NP-hard to solve in general, they admit a natural family of tractable convex relaxations. In this talk, we will study the standard semidefinite program (SDP) relaxation for general QCQPs and examine when this relaxation is exact. By analyzing the "geometry" of the SDP relaxation, we will give both sufficient conditions and necessary conditions for different types of "exactness" conditions, and discuss a number of implications of these results for various applications.

This is joint work with Alex L. Wang and C.J. Argue.

Short Bio: Fatma Kılınç-Karzan is an Associate Professor of Operations Research at Tepper School of Business, Carnegie Mellon University. She holds the Frank A. and Helen E. Risch Faculty Development Chair. She is also an Associate Professor of Computer Science (by courtesy) at the School of Computer Science, and is a member of the Algorithms Combinatorics and Optimization (ACO) PhD Program. She completed her PhD at Georgia Institute of Technology in the H. Milton Stewart School of Industrial & Systems Engineering Department with a minor in Mathematics. Her research interests are broadly in Operations Research, Analytics, and Machine Learning. She is currently working on developing foundational theory and algorithms for convex optimization and structured nonconvex optimization, and their applications in optimization under uncertainty (robust optimization, chance constraints and distributionally robust optimization), machine learning (preference learning from limited data) and business analytics.

Recording