The nonlinear geometry of linear programming. III. Projective Legendre transform coordinates and Hilbert geometry

Author:
J. C. Lagarias

Journal:
Trans. Amer. Math. Soc. **320** (1990), 193-225

MSC:
Primary 90C05

DOI:
https://doi.org/10.1090/S0002-9947-1990-1058199-0

MathSciNet review:
1058199

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper studies projective scaling trajectories, which are the trajectories obtained by following the infinitesimal version of Karmarkar's linear programming algorithm. A nonlinear change of variables, *projective Legendre transform coordinates*, is introduced to study these trajectories. The projective Legendre transform mapping has a coordinate-free geometric interpretation in terms of the notion of "centering by a projective transformation." Let be a set of linear programming constraints on such that its polytope of feasible solutions is bounded and contains in its interior. The projective Legendre transform mapping is given by

**[A]**K. Ansteicher,*Linear programming and the Newton barrier flow*, Math. Programming**41**(1988), 367-374. MR**955212 (89h:90139)****[BL1]**D. Bayer and J. C. Lagarias,*The nonlinear geometry of linear programming*. I.*Affine and projective scaling trajectories*, Trans. Amer. Math. Soc.**314**(1989), 499-526. MR**1005525 (90h:90098a)****[BL2]**-,*The nonlinear geometry of linear programming*. II.*Legendre transform coordinates and central trajectories*, Trans. Amer. Math. Soc.**314**(1989), 527-581. MR**1005526 (90h:90098b)****[BL]**-,*Karmarkar's linear programming algorithm and Newton's method*, Math. Programming (to appear).**[Bi]**G. Birkhoff,*Extensions of Jentzch's theorem*, Trans. Amer. Math. Soc.**85**(1957), 219-227. MR**0087058 (19:296a)****[Bu1]**H. Busemann,*The geometry of geodesics*, Academic Press, New York, 1955. MR**0075623 (17:779a)****[Bu2]**-,*Spaces with distinguished shortest joins*, Mathematical Developments Arising from Hilbert Problems, Proc. Sympos. Pure Math., vol. 28, Amer. Math. Soc., Providence, R.I., 1976, pp. 131-142.**[BP]**H. Busemann and B. B. Phadke,*Beltrami's theorem in the large*, Pacific J. Math.**115**(1984), 299-315. MR**765189 (85m:53084)****[Bush]**P. Bushnell,*On the projective contraction ratio for positive linear mappings*, J. London Math. Soc.**6**(1973), 256-258. MR**0331003 (48:9338)****[Bush2]**-,*Hilbert's metric and positive contraction mappings in a Banach space*, Arch. Rational Math. Anal.**52**(1973), 330-338. MR**0336473 (49:1247)****[Fe1]**W. Fenchel,*A remark on convex sets and polarity*, Comm. Sém. Math. Univ. Lund, Tome Suppl., 1952, pp. 82-89. MR**0051535 (14:495a)****[Fe2]**-,*Convex cones, sets, and functions*, Mimeographed Lecture Notes, Princeton Univ., 1953.**[H1]**D. Hilbert,*Ueber die gerade Linie als Kürzeste Verbindung zwier punkte*, Math. Ann.**46**(1895), 91-96 (Appendix I of [H3]).**[H2]**-,*Mathematical problems*, Bull. Amer. Math. Soc.**8**(1902), 437-479. (Transl. of*Mathematische Probleme*, Gottinger Nachrichten, 1900, pp. 253-297). MR**1557926****[H3]**-,*Foundations of geometry*, 10th ed. (translated by Leo Ungar), Open Court, La Salle, Ill., 1971. MR**0275262 (43:1019)****[K]**N. Karmarkar,*A new polynomial time algorithm for linear programming*, Combinatorica**4**(1984), 373-395. MR**779900 (86i:90072)****[K1]**V. Klee,*Adjoints of projective transformations and face figures of convex polytopes*, Math. Programming Stud.**3**(1978) 208-216. MR**510377 (80b:52014)****[Ko]**S. Kobayashi,*Invariant distances for projective structures*, Sympos. Math.**26**(1982), 153-161. MR**663030 (83i:53037)****[KP]**E. Kohlberg and J. W. Pratt,*The contraction mapping approach to the Perron-Frobenius theory: Why Hilbert's metric?*, Math. Oper. Res.**7**(1982), 198-250. MR**665557 (83m:15013)****[MS]**N. Megiddo and M. Shub,*Boundary behavior of interior point algorithms in linear programming*, Math. Oper. Res.**14**(1989), 97-146. MR**984561 (90c:90148)****[Sh]**M. Shub,*On the asymptotic behavior of the projective rescaling algorithm for linear programming*, IBM Report RC 12522, 1987. MR**919676 (89a:90084)****[S1]**F. Sinden,*A geometric representation for pairs of dual quadratic or linear programs*, J. Math. Anal. Appl.**5**(1962), 378-402. MR**0145997 (26:3523)****[S2]**-,*Duality in convex programming and in projective space*, J. Soc. Indust. Appl. Math.**11**(1963), 535-552. MR**0158764 (28:1987)****[So1]**G. Sonnevend,*An "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming*, Proc. 12th IFIP Conf. System Modelling and Optimization 1985, Lecture Notes in Control and Information Science Vol. 84, Springer-Verlag, New York, 1986. MR**903521 (88g:90133)****[So2]**-,*A new method of solving a set of linear (convex) inequalities and its application for identification and optimization*, Proc. Sympos. Dynamic Modelling, IFAC-IFORS, Budapest, 1986.**[St]**E. Steinitz,*Bedingt konvergente Reihen und konvexe Systeme*. I, II, III, J. Reine Angew Math.**143**(1913), 128-195;**144**(1914), 1-40:**146**(1916), 1-52.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
90C05

Retrieve articles in all journals with MSC: 90C05

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1990-1058199-0

Article copyright:
© Copyright 1990
American Mathematical Society