Back to search

Georgia Institute of Technology

Algebraic Methods in Optimization

Abstract

dc:description.abstract

This thesis broadly concerns the usage of techniques from algebra, the study of higher order structures in mathematics, toward understanding difficult optimization problems. Of particular interest will be optimization problems related to systems of polynomial equations, algebraic invariants of topological spaces, and algebraic structures in convex optimization. We will discuss various concrete examples of these kinds of problems. Firstly, we will describe new constructions for a class of polynomials known as hyperbolic polynomials which have connections to convex optimization. Secondly, we will describe how we can use ideas from algebraic geometry, notably the study of Stanley-Reisner varieties to study sparse structures in semidefinite programming. This will lead to quantitative bounds on some approximations for sparse problems and concrete connections to sparse linear regression and sparse PCA. Thirdly, we will use methods from algebraic topology to show that certain optimization problems on nonconvex topological spaces can be turned into convex problems due to a phenomenon known as 'hidden convexity'. Specifically, we give a sufficient condition for the image of a topological space under a continuous map to be convex, and give a number of examples of this phenomena with practical importance. This unifies and generalizes a number of existing results. Finally, we will describe how to use techniques inspired by the sum of squares method to find new variants of gradient descent which converge faster than typical gradient descent on smooth convex problems.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shu, Kevin
Advisor dc:contributor.advisor
  • Blekherman, Grigoriy
Committee members dc:contributor.committeemember
  • Dey, Santanu
  • Zhang, Shixuan
  • Singh, Mohit
  • Ahmadi, Amir Ali

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Shu, Kevin. Algebraic Methods in Optimization. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75260