Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

For convex optimization problems, such as linear, quadratic, or semidefinite programming, a class of interior point algorithms track the so-called central path to an optimal solution. The central curve, the Zariski closure of the central path, is an algebraic curve and it has been recently studied by De Loera, Sturmfels, and Vinzant in the linear case. In particular, the degree of the central curve for linear programming has been computed, and this has implications for the complexity of the interior point algorithms. We tackle the next case, the degree of the central curve for quadratic programming. We prove a formula for this degree, and after a reduction to the "diagonal" case, we give a Groebner basis for the ideal defining the central curve. We also explore the geometry and combinatorics of the system of polynomial equations that give rise to the central curve, shedding more insight to the quadratic as well as linear case. This work is joint with Dennis Schlief from SFSU.