Name
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, 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10208-012-9127-7 | Foundations of Computational Mathematics |
Keywords | Field | DocType |
Linear programming,Central path,Hyperplane arrangement,Interior-point methods,Complementary slackness,Matroid,Tutte polynomial,Hyperbolic polynomial,Gauss map,Degree,Curvature,Total curvature,Projective variety,Gröbner basis,Prime ideal,90C05,05B35,13P25,14H45,52C35 | Discrete mathematics,Mathematical optimization,Arithmetic genus,Curvature,Total curvature,Curve fitting,Algebraic curve,Mathematical analysis,Stable curve,Moore curve,Butterfly curve (algebraic),Mathematics | Journal |
Volume | Issue | ISSN |
12 | 4 | Foundations of Computational Mathematics: Volume 12, Issue 4
(2012), Page 509-540 |
Citations | PageRank | References |
2 | 0.65 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jesús A. De Loera | 1 | 357 | 42.24 |
| Bernd Sturmfels | 2 | 926 | 136.85 |
| Cynthia Vinzant | 3 | 79 | 11.85 |