Fall 2014

Degree of Central Curve in Quadratic Programming

Wednesday, October 15th, 2014 4:35 pm5:00 pm

Add to Calendar


Calvin Lab Auditorium

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.