Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 $ {\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

$\displaystyle {\psi _{\mathsf{H}}}({\mathbf{x}}) = \frac{{{\phi _{\mathsf{H}}}(... ...{{{\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 [Enhancements On Off] (What's this?)

  • [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.

Similar Articles

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

American Mathematical Society