×

zbMATH — the first resource for mathematics

The central curve in linear programming. (English) Zbl 1254.90108
Summary: 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.

MSC:
90C05 Linear programming
05B35 Combinatorial aspects of matroids and geometric lattices
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
14H45 Special algebraic curves and curves of low genus
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
Software:
Macaulay2
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] I. Adler, The expected number of pivots needed to solve parametric linear programs and the efficiency of the self-dual simplex method, Technical Report, University of California at Berkeley, CA (1983).
[2] A. Bachem, W. Kern, Linear Programming Duality. An Introduction to Oriented Matroids, Universitext (Springer, Berlin, 1992). · Zbl 0757.90050
[3] D. Bayer, J. Lagarias, The nonlinear geometry of linear programming. I. Affine and projective scaling trajectories, Trans. Am. Math. Soc. 314, 499–526 (1989). · Zbl 0671.90045
[4] D. Bayer, J. Lagarias, The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories, Trans. Am. Math. Soc. 314, 527–581 (1989). · Zbl 0671.90046
[5] R. Benedetti, M. Dedò, A geometric inequality for the total curvature of plane curves, Geom. Dedic. 22, 105–115 (1987). · Zbl 0611.53003
[6] A. Berget, Products of linear forms and Tutte polynomials, Eur. J. Comb. 31, 1924–1935 (2010). · Zbl 1219.05032 · doi:10.1016/j.ejc.2010.01.006
[7] A. Björner, The homology and shellability of matroids and geometric lattices, in Matroid Applications. Encyclopedia Math. Appl., vol. 40 (Cambridge Univ. Press, Cambridge, 1992), pp. 226–283. · Zbl 0772.05027
[8] K.H. Borgwardt, Probabilistic analysis of the simplex method, in Mathematical Developments Arising from Linear Programming, ed. by J.C. Lagarias, M.J. Todd. Contemporary Mathematics, vol. 114 (Am. Math. Soc., Providence, 1990), pp. 21–34. · Zbl 0725.90059
[9] E. Brugallé, L. López de Medrano, Inflection points of real and tropical plane curves, J. Singularities (2012). doi: 10.5427/jsing.2012.4e · Zbl 1292.14042
[10] T. Brylawski, J. Oxley, The Tutte polynomial and its applications, in Matroid Applications. Encyclopedia Math. Appl., vol. 40 (Cambridge Univ. Press, Cambridge, 1992), pp. 123–225. · Zbl 0769.05026
[11] J.P. Dedieu, G. Malajovich, M. Shub, On the curvature of the central path for linear programming theory, Found. Comput. Math. 5, 145–171 (2005). · Zbl 1119.90370 · doi:10.1007/s10208-003-0116-8
[12] A. Deza, T. Terlaky, Y. Zinchenko, A continuous d-step conjecture for polytopes, Discrete Comput. Geom. 41, 318–327 (2009). · Zbl 1168.52009 · doi:10.1007/s00454-008-9096-4
[13] A. Deza, T. Terlaky, Y. Zinchenko, Polytopes and arrangements: Diameter and curvature, Oper. Res. Lett. 36(2), 215–222 (2008). · Zbl 1144.52024 · doi:10.1016/j.orl.2007.06.007
[14] I.V. Dolgachev, Classical Algebraic Geometry: A Modern View (Cambridge University Press, Cambridge, 2012). · Zbl 1252.14001
[15] D. Grayson, M. Stillman, Macaulay 2, a software system for research in algebraic geometry, available at www.math.uiuc.edu/Macaulay2/ .
[16] P. Griffiths, On Cartan’s method of Lie groups and moving frames as applied to uniqueness and existence questions in differential geometry, Duke Math. J. 41, 775–814 (1974). · Zbl 0294.53034 · doi:10.1215/S0012-7094-74-04180-5
[17] M. Haimovich, The simplex algorithm is very good!: On the expected number of pivot steps and related properties of random linear programs. Technical Report, Columbia University, New York (1983).
[18] F. Klein, Eine neue Relation zwischen den Singularitäten einer algebraischer Curve, Math. Ann. 10, 199–210 (1876). · doi:10.1007/BF01442459
[19] E.L. Lawler, Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). · Zbl 0413.90040
[20] A. Lewis, P. Parrilo, M. Ramana, The Lax conjecture is true, Proc. Am. Math. Soc. 133, 2495–2499 (2005). · Zbl 1073.90029 · doi:10.1090/S0002-9939-05-07752-X
[21] N. Megiddo, M. Shub, Boundary behavior of interior point algorithms in linear programming. Math. Oper. Res., 14(1), 97–146 (1989). · Zbl 0675.90050 · doi:10.1287/moor.14.1.97
[22] R. Monteiro, T. Tsuchiya, 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, Math. Program., Ser. A 115, 105–149 (2008). · Zbl 1151.90023 · doi:10.1007/s10107-007-0141-5
[23] R. Piene, Numerical characters of a curve in projective space, in Real and Complex Singularities. Proc. Ninth Nordic Summer School Sympos. Math., Oslo, 1976 (1977), pp. 475–495. Sijthoff and Noordhoff.
[24] N. Proudfoot, D. Speyer, A broken circuit ring, Beiträge Algebra Geom. 47, 161–166 (2006). · Zbl 1095.13024
[25] J. Renegar, Hyperbolic programs, and their derivative relaxations, Found. Comput. Math. 6, 59–79 (2006). · Zbl 1130.90363 · doi:10.1007/s10208-004-0136-z
[26] C. Roos, T. Terlaky, J.-Ph. Vial, Theory and Algorithms for Linear Optimization: An Interior Point Approach 2nd edn. (Springer, New York, 2006).
[27] P. Rostalski, B. Sturmfels, Dualities in convex algebraic geometry. Rend. Mat. Appl. (7) 30(3–4), 285–327 (2010). · Zbl 1234.90012
[28] G. Sonnevend, J. Stoer, G. Zhao, On the complexity of following the central path of linear programs by linear extrapolation. II. Math. Program., Ser. B 52, 527–553 (1991). · Zbl 0742.90056 · doi:10.1007/BF01582904
[29] R.P. Stanley, Combinatorics and Commutative Algebra, 2nd edn. Progress in Mathematics, vol. 41 (Birkhäuser, Boston, 1996). · Zbl 0838.13008
[30] B. Sturmfels, C. Uhler, Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry, Ann. Inst. Stat. Math. 62, 603–638 (2010). · Zbl 1440.62255 · doi:10.1007/s10463-010-0295-4
[31] H. Terao, Algebras generated by reciprocals of linear forms, J. Algebra 250, 549–558 (2002). · Zbl 1049.13011 · doi:10.1006/jabr.2001.9121
[32] R.J. Vanderbei, Linear programming: foundations and extensions, in Operations Research & Management Science, 3rd edn. International Series, vol. 114 (Springer, New York, 2008). · Zbl 1139.90002
[33] S. Vavasis, Y. Ye, A primal-dual interior-point method whose running time depends only on the constraint matrix, Math. Program., Ser. A 74, 79–120 (1996). · Zbl 0868.90081
[34] V. Vinnikov, Self-adjoint determinantal representations of real plane curves, Math. Ann. 296(3), 453–479 (1993). · Zbl 0789.14029 · doi:10.1007/BF01445115
[35] T. Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Mem. Am. Math. Soc., 1, 154 (1975). · Zbl 0296.50010
[36] G. Zhao, J. Stoer, Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals, Appl. Math. Optim. 27, 85–103 (1993). · Zbl 0768.90056 · doi:10.1007/BF01182599
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.