Mathematics – Optimization and Control
Scientific paper
2010-12-17
Mathematics
Optimization and Control
26 pages, 5 figures, added section on average total curvature, minor revisions
Scientific paper
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, 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. The global geometry of central curves is studied in detail.
de Loera Jesus A.
Sturmfels Bernd
Vinzant Cynthia
No associations
LandOfFree
The central curve in linear programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The central curve in linear programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The central curve in linear programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-155356