|
![](../../../img/spacer.gif) |
![](../../../img/spacer.gif) |
Fall 2011 Seminar Series
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
OPERATIONS RESEARCH CENTER
FALL 2011 SEMINAR SERIES
DATE: November 10th
LOCATION: E62-550
TIME: 4:15pm
Reception immediately following
TITLE
The Central Curve in Linear Programming
ABSTRACT
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. We determine the degree, genus and defining 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 the language of matroid theory. This yields new bounds on the total curvature of the central path, a quantity relevant for interior point methods.
Back to Seminar Series schedule page
|
![](../../../img/spacer.gif) |
![](../../../img/spacer.gif) |
![](../../../img/spacer.gif) |
|