Back to search

Georgia Institute of Technology

Some global relaxation methods for quadratic and semidefinite programming

Abstract

dc:description.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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sun, Shengding
Advisors dc:contributor.advisor
  • Blekherman, Grigoriy
  • Dey, Santanu S.
Committee members dc:contributor.committeemember
  • Singh, Mohit
  • Sun, Andy
  • Cifuentes, Diego

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/72665

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sun, Shengding. Some global relaxation methods for quadratic and semidefinite programming. Doctoral thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/72665