Title: Some Global Relaxation Methods for Quadratic and Semidefinite Programming
Date: May 9, 2023 (subject to change)
Time: 11:00 AM (subject to change)
Location: Skiles 005 and Zoom (link TBD)
Advisors:
Dr. Grigoriy Blekherman, School of Mathematics, Georgia Institute of Technology
Dr. Santanu S. Dey, School of Industrial and Systems Engineering, Georgia Institute of Technology
Committee:
Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Andy Sun, School of Management, Massachusetts Institute of Technology
Reader: Dr. Diego Cifuentes, School of Industrial and Systems Engineering, Georgia Institute of Technology
Thesis draft: https://www.dropbox.com/sh/bf6kv5vk4x3o1a3/AAAZB0bRE4Qg0CfhweetVKsIa?dl=0
Abstract: Quadratic programming and semidefinite programming are vital tools in discrete and continuous optimization, with broad applications. A major challenge is to develop methodologies and algorithms to solve instances with special structures. For this purpose, we study some global relaxation techniques to quadratic and semidefinite programming, and prove theoretical properties about their qualities. In the first half we study the negative eigenvalues of $k$-locally positive semidefinite matrices, which are closely related to the sparse relaxation of semidefinite programming. In the second half we study aggregations of quadratic inequalities, a tool that can be leveraged to obtain tighter relaxation to quadratic programming than the standard Shor relaxation. In particular, our results on finiteness of aggregations can potentially lead to efficient algorithms for certain classes of quadratic programming instances with two constraints.
