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

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]**Kurt M. Anstreicher,*Linear programming and the Newton barrier flow*, Math. Programming**41**(1988), no. 3, (Ser. A), 367–373. MR**955212**, https://doi.org/10.1007/BF01580774**[BL1]**D. A. Bayer and J. C. Lagarias,*The nonlinear geometry of linear programming. I. Affine and projective scaling trajectories*, Trans. Amer. Math. Soc.**314**(1989), no. 2, 499–526. MR**1005525**, https://doi.org/10.1090/S0002-9947-1989-1005525-6**[BL2]**D. A. Bayer and J. C. Lagarias,*The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories*, Trans. Amer. Math. Soc.**314**(1989), no. 2, 527–581. MR**1005526**, https://doi.org/10.1090/S0002-9947-1989-1005526-8**[BL]**-,*Karmarkar's linear programming algorithm and Newton's method*, Math. Programming (to appear).**[Bi]**Garrett Birkhoff,*Extensions of Jentzsch’s theorem*, Trans. Amer. Math. Soc.**85**(1957), 219–227. MR**0087058**, https://doi.org/10.1090/S0002-9947-1957-0087058-6**[Bu1]**Herbert Busemann,*The geometry of geodesics*, Academic Press Inc., New York, N. Y., 1955. MR**0075623****[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,*A general version of Beltrami’s theorem in the large*, Pacific J. Math.**115**(1984), no. 2, 299–315. MR**765189****[Bush]**P. J. Bushell,*On the projective contraction ratio for positive linear mappings*, J. London Math. Soc. (2)**6**(1973), 256–258. MR**0331003**, https://doi.org/10.1112/jlms/s2-6.2.256**[Bush2]**P. J. Bushell,*Hilbert’s metric and positive contraction mappings in a Banach space*, Arch. Rational Mech. Anal.**52**(1973), 330–338. MR**0336473**, https://doi.org/10.1007/BF00247467**[Fe1]**W. Fenchel,*A remark on convex sets and polarity*, Comm. Sém. Math. Univ. Lund [Medd. Lunds Univ. Mat. Sem.]**1952**(1952), no. Tome Supplémentaire, 82–89. MR**0051535****[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]**David Hilbert,*Mathematical problems*, Bull. Amer. Math. Soc.**8**(1902), no. 10, 437–479. MR**1557926**, https://doi.org/10.1090/S0002-9904-1902-00923-3**[H3]**David Hilbert,*Foundations of geometry*, Second edition. Translated from the tenth German edition by Leo Unger, Open Court, LaSalle, Ill., 1971. MR**0275262****[K]**N. Karmarkar,*A new polynomial-time algorithm for linear programming*, Combinatorica**4**(1984), no. 4, 373–395. MR**779900**, https://doi.org/10.1007/BF02579150**[K1]**Victor Klee,*Adjoints of projective transformations and face-figures of convex polytopes*, Math. Programming Stud.**8**(1978), 208–216. Polyhedral combinatorics. MR**510377****[Ko]**Shoshichi Kobayashi,*Invariant distances for projective structures*, Symposia Mathematica, Vol. XXVI (Rome, 1980) Academic Press, London-New York, 1982, pp. 153–161. MR**663030****[KP]**Elon Kohlberg and John W. Pratt,*The contraction mapping approach to the Perron-Frobenius theory: why Hilbert’s metric?*, Math. Oper. Res.**7**(1982), no. 2, 198–210. MR**665557**, https://doi.org/10.1287/moor.7.2.198**[MS]**Nimrod Megiddo and Michael Shub,*Boundary behavior of interior point algorithms in linear programming*, Math. Oper. Res.**14**(1989), no. 1, 97–146. MR**984561**, https://doi.org/10.1287/moor.14.1.97**[Sh]**Michael Shub,*On the asymptotic behavior of the projective rescaling algorithm for linear programming*, J. Complexity**3**(1987), no. 3, 258–269. MR**919676**, https://doi.org/10.1016/0885-064X(87)90015-X**[S1]**F. W. Sinden,*A geometric representation for pairs of dual quadratic or linear programs*, J. Math. Anal. Appl.**5**(1962), 378–402. MR**0145997**, https://doi.org/10.1016/0022-247X(62)90014-8**[S2]**Frank W. Sinden,*Duality in convex programming and in projective space*, J. Soc. Indust. Appl. Math.**11**(1963), 535–552. MR**0158764****[So1]**Gy. Sonnevend,*An “analytical centre” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming*, System modelling and optimization (Budapest, 1985) Lect. Notes Control Inf. Sci., vol. 84, Springer, Berlin, 1986, pp. 866–875. MR**903521**, https://doi.org/10.1007/BFb0043914**[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