Optimization Online


The central curve in linear programming

Jesus De Loera(deloera***at***math.ucdavis.edu)
Cynthia Vinzant(cvinzant***at***math.berkeley.edu)
Bernd Sturmfels(bernd***at***math.berkeley.edu)

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.

Keywords: Linear programming, central path, interior point methods, matroid, Tutte polynomial, hyperbolic polynomial, Gauss map, degree, curvature, projective variety, Groebner basis, hyperplane arrangement.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Nonlinear Optimization (Other )

Citation: submitted, University of California, 2010

Download: [PDF]

Entry Submitted: 12/17/2010
Entry Accepted: 12/17/2010
Entry Last Modified: 12/17/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society