The central curve in linear programming

DOI10.1007/s10208-012-9127-7zbMath1254.90108arXiv1012.3978OpenAlexW3121889995MaRDI QIDQ695626

Jesús A. De Loera, Cynthia Vinzant, Bernd Sturmfels

Publication date: 21 December 2012

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.3978

zbMATH Keywords

linear programmingGröbner basiscurvaturedegreeGauss mapinterior-point methodsprime idealmatroidTutte polynomialcentral pathhyperplane arrangementprojective varietytotal curvaturecomplementary slacknesshyperbolic polynomial

Mathematics Subject Classification ID

Linear programming (90C05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Special algebraic curves and curves of low genus (14H45) Combinatorial aspects of matroids and geometric lattices (05B35) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Related Items

Algebraic boundaries of convex semi-algebraic sets, The Hurwitz form of a projective variety, Log-Barrier Interior Point Methods Are Not Strongly Polynomial, On the complexity of analyticity in semi-definite optimization, Toric geometry of entropic regularization, The degree of the central curve in semidefinite, linear, and quadratic programming, The entropic discriminant, What Tropical Geometry Tells Us about the Complexity of Linear Programming, Exponential varieties, The Chow form of a reciprocal linear space, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, On maximally inflected hyperbolic curves, On Deformations of Hyperbolic Varities, Semi-inverted linear spaces and an analogue of the broken circuit complex, Computing complex and real tropical curves using monodromy, Real fibered morphisms and Ulrich sheaves, Coordinate-wise powers of algebraic varieties, On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate

Uses Software

• Macaulay2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Products of linear forms and Tutte polynomials
• A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
• Polytopes and arrangements: diameter and curvature
• A continuous \(d\)-step conjecture for polytopes
• A geometric inequality for the total curvature of plane curves
• On the complexity of following the central path of linear programs by linear extrapolation. II
• Linear programming duality: an introduction to oriented matroids
• Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
• On Cartan's method of Lie groups and moving frames as applied to uniqueness and existence questions in differential geometry
• Self-adjoint determinantal representations of real plane curves
• A primal-dual interior point method whose running time depends only on the constraint matrix
• Algebras generated by reciprocals of linear forms
• Combinatorics and commutative algebra.
• Hyperbolic programs, and their derivative relaxations
• Linear programming. Foundations and extensions.
• A broken circuit ring
• On the curvature of the central path of linear programming theory
• Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry
• Classical Algebraic Geometry
• Dualities in Convex Algebraic Geometry
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• The Lax conjecture is true
• INFLECTION POINTS OF REAL AND TROPICAL PLANE CURVES