Abstract

Interior point methods track the central path in various convex optimization problems, including quadratic programs with linear constraints. The Zariski closure of the central path, called the central curve, is an algebraic curve, that has been studied by De Loera, Sturmfels and Vinzant for generic linear programs. We follow their footsteps and compute the degree of the central curve for generic quadratic programs. This gives a measure of algebraic complexity for the central curve and can be used to bound the curvature of the central path. We also construct a Grobner basis for the central curve when the program is defined by a generic diagonal matrix.

Video Recording