Leveraging Algebraic and Geometric Structures in Optimization Open Access

Abstract

Mathematical optimization has been a highly active field in recent years. Typically, one seeks to leverage structure, such as convexity, when studying optimization problems. We focus on several optimization problems for which structures in the objective function or constraints are naturally phrased in the language of algebraic geometry. 

The first problem we consider is regression over the space of rational functions in tropical (max-plus) algebra. Such functions form a widely expressive class of function approximators and have recently proven useful in the theoretical analysis of ReLU neural networks. We develop an alternating heuristic to solve regression problems over tropical rational functions by leveraging known results from tropical linear systems and polynomial regression. Numerical experiments show the strengths and weaknesses of the heuristic and we provide a connection between our method and geometric aspects of the loss function. 

The second problem we consider is semidefinite programming in the *_M tensor-tensor product framework. We demonstrate that the choice of matrix M corresponds to the representation theory of an underlying group action. This connection lends the *_M product to be a natural framework for certain invariant semidefinite programs. We demonstrate the M-SDP framework on certain invariant sums of squares polynomials and low rank tensor completion problems

The final problem we consider is the expression of the convex hull of a set defined by three quadratic inequality constraints using nonnegative linear combinations (aggregations) of the constraints. Our approach relates the problem to the topology of the spectral curve, defined as the zero set of the determinant of linear combinations of the defining quadratics. In particular, we characterize the nonexistence of solutions to systems of inequalities in terms of the hyperbolicity of the spectral curve. Hyperbolic curves are well-studied in real algebraic geometry, as their zero sets consist of maximally nested ovals, the innermost of which bounds a convex cone. By studying (non)intersections of polyhedral cones of aggregations with hyperbolicity cones of the spectral curve, we provide a sufficient condition for the convex hull to be given by aggregations and characterize when finitely many aggregations suffice for such a description.

Table of Contents

1) Introduction

2) Preliminaries

3) Regression with Tropical Rational Functions

4) Tensor-Tensor Products and Semidefinite Programs

5) Topological Approach to Aggregations of Quadratic Inequalities

6) Conclusions and Future Directions

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Mathematics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Mathematics
Keyword	Convex Optimization Real Algebraic Geometry Neural Networks Tensors Tropical Geometry Algebraic Topology
Committee Chair / Thesis Advisor	Lars Ruthotto, Emory University Grigoriy Blekherman, Georgia Institute of Technology
Committee Members	Elizabeth Newman, Emory University David Borthwick, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Leveraging Algebraic and Geometric Structures in Optimization ()	2025-07-02 08:59:37 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions