Computing the central sheet in linear, quadratic, and semi-definite programs

Convex optimization is the study of finding optimal solutions to various convex objective functions given a system of constraints defining a convex solution set. Interior point algorithms are utilized to obtain optimal solutions to a given convex program by navigating the solution space through Newton-type iterations. For linear programs, one can obtain an algebraic handle on the path of the interior point algorithm by finding the Zariski closure of such a path, called the central curve. Previous work has related computational complexity of these algorithms to the degree of the central curve. This degree has been computed for a generic linear program. This thesis will explore how to compute the degree of the central curve for the transportation problem over complete bipartite graphs. We will propose new methods for computing the central sheet—a higher dimensional object of the same degree as the central curve—for quadratic and semi-definite programs. We will also present conjectures about the degree of the central sheet for semidefinite programs supported by computational evidence.