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

HTML articles powered by AMS MathViewer

- by J. C. Lagarias
- Trans. Amer. Math. Soc.
**320**(1990), 193-225 - DOI: https://doi.org/10.1090/S0002-9947-1990-1058199-0
- PDF | Request permission

## 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 ${\mathsf {H}}$ be a set of linear programming constraints $\{ \langle {{\mathbf {a}}_j},{\mathbf {x}}\rangle \geq {b_j}:1 \leq j \leq m\}$ on ${{\mathbf {R}}^n}$ such that its polytope of feasible solutions ${P_{\mathsf {H}}}$ is bounded and contains ${\mathbf {0}}$ in its interior. The projective Legendre transform mapping ${\psi _{\mathsf {H}}}$ is given by \[ {\psi _{\mathsf {H}}}({\mathbf {x}}) = \frac {{{\phi _{\mathsf {H}}}({\mathbf {x}})}} {{m + \langle {\phi _{\mathsf {H}}}({\mathbf {x}}),{\mathbf {x}}\rangle }},\quad {\mathsf {where}}{\phi _{\mathsf {H}}}({\mathbf {x}}) = - \sum \limits _{j = 1}^m {\frac {{{{\mathbf {a}}_j}}} {{\langle {{\mathbf {a}}_j},{\mathbf {x}}\rangle - {b_j}}}.} \] Here ${\phi _{\mathsf {H}}}(x)$ is the Legendre transform coordinate mapping introduced in part II. ${\psi _{\mathsf {H}}}({\mathbf {x}})$ is a one-to-one and onto mapping of the interior of the feasible solution polytope $\operatorname {Int} ({P_{\mathsf {H}}})$ to the interior of its polar polytope $\operatorname {Int} (P_{\mathsf {H}}^\circ )$. The set of projective scaling trajectories with objective function $\langle {\mathbf {c}},{\mathbf {x}}\rangle - {c_0}$ are mapped under ${\psi _{\mathsf {H}}}$ to the set of straight line segments in $\operatorname {Int} (P_{\mathsf {H}} ^\circ )$ passing through the boundary point $- {\mathbf {c}}/{c_0}$ of $P_{\mathsf {H}} ^\circ$. As a consequence the projective scaling trajectories (for all objective functions) can be interpreted as the complete set of "geodesics" (actually distinguished chords) of a projectively invariant metric geometry on $\operatorname {Int} ({P_{\mathsf {H}}})$, which is isometric to Hilbert geometry on the interior of the polar polytope $P_{\mathsf {H}}^\circ$.

## References

- Kurt M. Anstreicher,
*Linear programming and the Newton barrier flow*, Math. Programming**41**(1988), no. 3, (Ser. A), 367–373. MR**955212**, DOI 10.1007/BF01580774 - 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**, DOI 10.1090/S0002-9947-1989-1005525-6 - 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**, DOI 10.1090/S0002-9947-1989-1005525-6
—, - Garrett Birkhoff,
*Extensions of Jentzsch’s theorem*, Trans. Amer. Math. Soc.**85**(1957), 219–227. MR**87058**, DOI 10.1090/S0002-9947-1957-0087058-6 - Herbert Busemann,
*The geometry of geodesics*, Academic Press, Inc., New York, N.Y., 1955. MR**0075623**
—, - 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**, DOI 10.2140/pjm.1984.115.299 - P. J. Bushell,
*On the projective contraction ratio for positive linear mappings*, J. London Math. Soc. (2)**6**(1973), 256–258. MR**331003**, DOI 10.1112/jlms/s2-6.2.256 - P. J. Bushell,
*Hilbert’s metric and positive contraction mappings in a Banach space*, Arch. Rational Mech. Anal.**52**(1973), 330–338. MR**336473**, DOI 10.1007/BF00247467 - 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**51535**
—, - David Hilbert,
*Mathematical problems*, Bull. Amer. Math. Soc.**8**(1902), no. 10, 437–479. MR**1557926**, DOI 10.1090/S0002-9904-1902-00923-3 - David Hilbert,
*Foundations of geometry*, 2nd ed., Open Court, La Salle, Ill., 1971. Translated from the tenth German edition by Leo Unger. MR**0275262** - N. Karmarkar,
*A new polynomial-time algorithm for linear programming*, Combinatorica**4**(1984), no. 4, 373–395. MR**779900**, DOI 10.1007/BF02579150 - Victor Klee,
*Adjoints of projective transformations and face-figures of convex polytopes*, Math. Programming Stud.**8**(1978), 208–216. Polyhedral combinatorics. MR**510377**, DOI 10.1007/bfb0121203 - Shoshichi Kobayashi,
*Invariant distances for projective structures*, Symposia Mathematica, Vol. XXVI (Rome, 1980) Academic Press, London-New York, 1982, pp. 153–161. MR**663030** - 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**, DOI 10.1287/moor.7.2.198 - 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**, DOI 10.1287/moor.14.1.97 - Michael Shub,
*On the asymptotic behavior of the projective rescaling algorithm for linear programming*, J. Complexity**3**(1987), no. 3, 258–269. MR**919676**, DOI 10.1016/0885-064X(87)90015-X - F. W. Sinden,
*A geometric representation for pairs of dual quadratic or linear programs*, J. Math. Anal. Appl.**5**(1962), 378–402. MR**145997**, DOI 10.1016/0022-247X(62)90014-8 - Frank W. Sinden,
*Duality in convex programming and in projective space*, J. Soc. Indust. Appl. Math.**11**(1963), 535–552. MR**158764**, DOI 10.1137/0111039 - 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**, DOI 10.1007/BFb0043914
—,

*Karmarkar’s linear programming algorithm and Newton’s method*, Math. Programming (to appear).

*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.

*Convex cones, sets, and functions*, Mimeographed Lecture Notes, Princeton Univ., 1953. D. Hilbert,

*Ueber die gerade Linie als Kürzeste Verbindung zwier punkte*, Math. Ann.

**46**(1895), 91-96 (Appendix I of [H3]).

*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. 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.

## Bibliographic Information

- © Copyright 1990 American Mathematical Society
- 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