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 —, Karmarkar’s linear programming algorithm and Newton’s method, Math. Programming (to appear).
- 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 —, 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.
- 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 —, 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]).
- 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 —, 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