Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 295 - Mathematics Colloquium

Bernd Sturmfels

UC Berkeley

The central curve in linear programming

Abstract:

\indent The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. In this lecture we present joint work with Daniel Plaumann and Cynthia Vinzant on the geometry of central curves. We determine the degree, arithmetic genus and defining prime ideal of the central curve, thereby answering a question of Bayer and Lagarias. These invariants, along with the degree of the Gauss image of the curve, are expressed in terms of the matroid of the input matrix. Extending work of Dedieu, Malajovich and Shub, this yields an instance-specific bound on the total curvature of the central path, a quantity relevant for interior point methods.

Sponsor: Jiawang Nie

April 15, 2011

4:00 PM

AP&M 6402

****************************