## The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories

HTML articles powered by AMS MathViewer

- by D. A. Bayer and J. C. Lagarias
- Trans. Amer. Math. Soc.
**314**(1989), 527-581 - DOI: https://doi.org/10.1090/S0002-9947-1989-1005526-8
- PDF | Request permission

## Abstract:

Karmarkar’s projective scaling algorithm for solving linear programming problems associates to each objective function a vector field defined in the interior of the polytope of feasible solutions of the problem. This paper studies the set of trajectories obtained by integrating this vector field, called $P$-*trajectories*, as well as a related set of trajectories, called $A$-

*trajectories*. The $A$-trajectories arise from another linear programming algorithm, the affine scaling algorithm. The affine and projective scaling vector fields are each defined for linear programs of a special form, called

*standard form*and

*canonical form*, respectively. These trajectories are studied using a nonlinear change of variables called

*Legendre transform coordinates*, which is a projection of the gradient of a logarithmic barrier function. The Legendre transform coordinate mapping is given by rational functions, and its inverse mapping is algebraic. It depends only on the constraints of the linear program, and is a one-to-one mapping for canonical form linear programs. When the polytope of feasible solutions is bounded, there is a unique point mapping to zero, called the

*center*. The $A$-trajectories of standard form linear programs are linearized by the Legendre transform coordinate mapping. When the polytope of feasible solutions is bounded, they are the complete set of geodesics of a Riemannian geometry isometric to Euclidean geometry. Each $A$-trajectory is part of a real algebraic curve. Each $P$-trajectory for a canonical form linear program lies in a plane in Legendre transform coordinates. The $P$-trajectory through ${\mathbf {0}}$ in Legendre transform coordinates, called the

*central*$P$-

*trajectory*, is part of a straight line, and is contained in the $A$-trajectory through ${\mathbf {0}}$, called the

*central*$A$-

*trajectory*. Each $P$-trajectory is part of a real algebraic curve. The central $A$-trajectory is the locus of centers of a family of linear programs obtained by adding an extra equality constraint of the form $\langle {\mathbf {c}},{\mathbf {x}}\rangle = \mu$. It is also the set of minima of a parametrized family of logarithmic barrier functions. Power-series expansions are derived for the central $A$-trajectory, which is also the central $P$-trajectory. These power-series have a simple recursive form and are useful in developing "higher-order" analogues of Karmarkar’s algorithm. $A$-trajectories are defined for a general linear program. Using this definition, it is shown that the limit point ${{\mathbf {x}}_\infty }$ of a central $A$-trajectory on the boundary of the feasible solution polytope $P$ is the center of the unique face of $P$ containing ${{\mathbf {x}}_\infty }$ in its relative interior. The central trajectory of a combined primal-dual linear program has a simple set of polynomial relations determining it as an algebraic curve. These relations are a relaxed form of the complementary slackness conditions. This central trajectory algebraically projects onto the central trajectories of both the primal and dual linear programs, and this gives an algebraic correspondence between points on the positive parts of the central trajectories of the primal and dual linear programs. Two Lagrangian dynamical systems with simple Lagrangians are shown to have $A$-trajectories as ${\mathbf {\dot q}}$-trajectories. The Hamiltonian dynamical systems associated to these Lagrangian systems are completely integrable.

## References

- I. Adler, N. Karmarkar, M. Resende, and G. Veiga,
- Kurt M. Anstreicher,
*A monotonic projective algorithm for fractional linear programming*, Algorithmica**1**(1986), no. 4, 483–498. MR**880734**, DOI 10.1007/BF01840458 - V. Arnold,
*Les méthodes mathématiques de la mécanique classique*, Éditions Mir, Moscow, 1976 (French). Traduit du russe par Djilali Embarek. MR**0474391** - Earl R. Barnes,
*A variation on Karmarkar’s algorithm for solving linear programming problems*, Math. Programming**36**(1986), no. 2, 174–182. MR**866987**, DOI 10.1007/BF02592024 - 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
—, - Salomon Bochner and William Ted Martin,
*Several Complex Variables*, Princeton Mathematical Series, vol. 10, Princeton University Press, Princeton, N. J., 1948. MR**0027863** - B. Bernstein and R. A. Toupin,
*Some properties of the Hessian matrix of a strictly convex function*, J. Reine Angew. Math.**210**(1962), 65–72. MR**145024**
R. Courant and D. Hilbert, - I. I. Dikin,
*Iterative solution of problems of linear and quadratic programming*, Dokl. Akad. Nauk SSSR**174**(1967), 747–748 (Russian). MR**0221850**
—, - W. Fenchel,
*On conjugate convex functions*, Canad. J. Math.**1**(1949), 73–77. MR**28365**, DOI 10.4153/cjm-1949-007-x - Anthony V. Fiacco and Garth P. McCormick,
*Nonlinear programming: Sequential unconstrained minimization techniques*, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR**0243831** - Wendell H. Fleming,
*Functions of several variables*, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1965. MR**0174675**
C. B. Garcia and W. I. Zangwill, - Clovis C. Gonzaga,
*An algorithm for solving linear programming problems in $O(n^3L)$ operations*, Progress in mathematical programming (Pacific Grove, CA, 1987) Springer, New York, 1989, pp. 1–28. MR**982713**
J. Guckenheimer, J. Moser, and S. E. Newhouse, - Kenneth Hoffman and Ray Kunze,
*Linear algebra*, Prentice-Hall Mathematics Series, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1961. MR**0125849**
J. Hooker, - N. Karmarkar,
*A new polynomial-time algorithm for linear programming*, Combinatorica**4**(1984), no. 4, 373–395. MR**779900**, DOI 10.1007/BF02579150 - Narendra K. Karmarkar, Jeffrey C. Lagarias, Lev Slutsman, and Pyng Wang,
*Power series variants of Karmarkar-type algorithms*, AT&T Tech. J.**68**(1989), no. 3, 20–36. MR**1021069**
S. Kapoor and P. M. Vaidya, - Masakazu Kojima, Shinji Mizuno, and Akiko Yoshise,
*A primal-dual interior point algorithm for linear programming*, Progress in mathematical programming (Pacific Grove, CA, 1987) Springer, New York, 1989, pp. 29–47. MR**982714** - J. C. Lagarias,
*The nonlinear geometry of linear programming. III. Projective Legendre transform coordinates and Hilbert geometry*, Trans. Amer. Math. Soc.**320**(1990), no. 1, 193–225. MR**1058199**, DOI 10.1090/S0002-9947-1990-1058199-0 - Cornelius Lanczos,
*The Variational Principles of Mechanics*, Mathematical Expositions, No. 4, University of Toronto Press, Toronto, Ont., 1949. MR**0034139** - Nimrod Megiddo,
*On the complexity of linear programming*, Advances in economic theory (Cambridge, MA, 1985) Econom. Soc. Monogr., vol. 12, Cambridge Univ. Press, Cambridge, 1989, pp. 225–268. MR**1117042** - Nimrod Megiddo,
*Pathways to the optimal set in linear programming*, Progress in mathematical programming (Pacific Grove, CA, 1987) Springer, New York, 1989, pp. 131–158. MR**982720** - 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 - J. Moser,
*Various aspects of integrable Hamiltonian systems*, Dynamical systems (C.I.M.E. Summer School, Bressanone, 1978) Progr. Math., vol. 8, Birkhäuser, Boston, Mass., 1980, pp. 233–289. MR**589592** - J. L. Nazareth,
*Homotopy techniques in linear programming*, Algorithmica**1**(1986), no. 4, 529–535. MR**880737**, DOI 10.1007/BF01840461 - M. R. Osborne,
*Dual barrier functions with superfast rates of convergence for the linear programming problem*, J. Austral. Math. Soc. Ser. B**29**(1987), no. 1, 39–58. MR**889576**, DOI 10.1017/S0334270000005610 - James Renegar,
*A polynomial-time algorithm, based on Newton’s method, for linear programming*, Math. Programming**40**(1988), no. 1, (Ser. A), 59–93. MR**923697**, DOI 10.1007/BF01580724 - R. T. Rockafellar,
*Conjugates and Legendre transforms of convex functions*, Canadian J. Math.**19**(1967), 200–205. MR**213496**, DOI 10.4153/CJM-1967-012-4
—, - 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
—, - Josef Stoer and Christoph Witzgall,
*Convexity and optimization in finite dimensions. I*, Die Grundlehren der mathematischen Wissenschaften, Band 163, Springer-Verlag, New York-Berlin, 1970. MR**0286498** - Michael J. Todd and Bruce P. Burrell,
*An extension of Karmarkar’s algorithm for linear programming using dual variables*, Algorithmica**1**(1986), no. 4, 409–424. MR**880731**, DOI 10.1007/BF01840455
P. Vaidya, - Robert J. Vanderbei, Marc S. Meketon, and Barry A. Freedman,
*A modification of Karmarkar’s linear programming algorithm*, Algorithmica**1**(1986), no. 4, 395–407. MR**880730**, DOI 10.1007/BF01840454

*An implementation of Karmarkar’s algorithm for linear programming*, preprint, Univ. of California, Berkeley, May 1986.

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

*Methods of mathematical physics*, Vols. I, II, Wiley, New York, 1962.

*About the convergence of an iterative process*, Controllable Systems IM IK SO AN SSSR 1974, No. 12, 54-60. (Russian)

*Pathways to solutions, fixed points and equilibria*, Prentice-Hall, Englewood Cliffs, N. J., 1981.

*Dynamical systems*, C.I.M.E. Lectures, Birkhäuser, Boston, Mass., 1980. D. Hilbert,

*Grundlagen der Geometrie*, 7th ed., Leipzig, 1930. (English transl.,

*Foundations of geometry*.)

*Karmarkar’s linear programming algorithm*, Interfaces

**16**(1986), 75-90.

*First algorithms for convex quadratic programming and multicommodity flows*, Proc. 18th ACM Sympos. on Theory of Computing, 1986, pp. 147-159.

*Convex analysis*, Princeton Univ. Press, Princeton, N. J., 1970.

*A new method for solving a set of linear (convex) inequalities and its application for identification and optimization*, Proc. Sympos. on Dynamic Modelling, IFAC-IFORS, Budapest, June 1986.

*An algorithm for linear programming which requires*$O(((m + n){n^2} + {(m + n)^{1.5}}n)L)$

*arithmetic operations*, Proc. 19th ACM Sympos. on Theory of Computing, 1987, pp. 29-38.

## Bibliographic Information

- © Copyright 1989 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**314**(1989), 527-581 - MSC: Primary 90C05; Secondary 34A99, 52A40
- DOI: https://doi.org/10.1090/S0002-9947-1989-1005526-8
- MathSciNet review: 1005526