The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories
Authors:
D. A. Bayer and J. C. Lagarias
Journal:
Trans. Amer. Math. Soc. 314 (1989), 527581
MSC:
Primary 90C05; Secondary 34A99, 52A40
MathSciNet review:
1005526
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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 trajectories, as well as a related set of trajectories, called trajectories. The 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 onetoone 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 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 trajectory is part of a real algebraic curve. Each trajectory for a canonical form linear program lies in a plane in Legendre transform coordinates. The trajectory through in Legendre transform coordinates, called the central trajectory, is part of a straight line, and is contained in the trajectory through , called the central trajectory. Each trajectory is part of a real algebraic curve. The central trajectory is the locus of centers of a family of linear programs obtained by adding an extra equality constraint of the form . It is also the set of minima of a parametrized family of logarithmic barrier functions. Powerseries expansions are derived for the central trajectory, which is also the central trajectory. These powerseries have a simple recursive form and are useful in developing "higherorder" analogues of Karmarkar's algorithm. trajectories are defined for a general linear program. Using this definition, it is shown that the limit point of a central trajectory on the boundary of the feasible solution polytope is the center of the unique face of containing in its relative interior. The central trajectory of a combined primaldual 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 trajectories as trajectories. The Hamiltonian dynamical systems associated to these Lagrangian systems are completely integrable.
 [AKRV]
I. Adler, N. Karmarkar, M. Resende, and G. Veiga, An implementation of Karmarkar's algorithm for linear programming, preprint, Univ. of California, Berkeley, May 1986.
 [A]
Kurt
M. Anstreicher, A monotonic projective algorithm for fractional
linear programming, Algorithmica 1 (1986),
no. 4, 483–498. MR 880734
(88f:90162), http://dx.doi.org/10.1007/BF01840458
 [Ar]
V.
I. Arnold, Mathematical methods of classical mechanics,
SpringerVerlag, New YorkHeidelberg, 1978. Translated from the Russian by
K. Vogtmann and A. Weinstein; Graduate Texts in Mathematics, 60. MR 0690288
(57 #14033b)
 [B]
Earl
R. Barnes, A variation on Karmarkar’s algorithm for solving
linear programming problems, Math. Programming 36
(1986), no. 2, 174–182. MR 866987
(88h:90120), http://dx.doi.org/10.1007/BF02592024
 [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
(90h:90098a), http://dx.doi.org/10.1090/S00029947198910055256
 [BL]
, Karmarkar's linear programming algorithm and Newton's method, Math. Programming (to appear).
 [BM]
Salomon
Bochner and William
Ted Martin, Several Complex Variables, Princeton Mathematical
Series, vol. 10, Princeton University Press, Princeton, N. J., 1948. MR 0027863
(10,366a)
 [BT]
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
0145024 (26 #2561)
 [CH]
R. Courant and D. Hilbert, Methods of mathematical physics, Vols. I, II, Wiley, New York, 1962.
 [D1]
I.
I. Dikin, Iterative solution of problems of linear and quadratic
programming, Dokl. Akad. Nauk SSSR 174 (1967),
747–748 (Russian). MR 0221850
(36 #4902)
 [D2]
, About the convergence of an iterative process, Controllable Systems IM IK SO AN SSSR 1974, No. 12, 5460. (Russian)
 [F]
W.
Fenchel, On conjugate convex functions, Canadian J. Math.
1 (1949), 73–77. MR 0028365
(10,435b)
 [FM]
Anthony
V. Fiacco and Garth
P. McCormick, Nonlinear programming: Sequential unconstrained
minimization techniques, John Wiley and Sons, Inc., New
YorkLondonSydney, 1968. MR 0243831
(39 #5152)
 [Fl]
Wendell
H. Fleming, Functions of several variables, AddisonWesley
Publishing Co., Inc., Reading, MAss.London, 1965. MR 0174675
(30 #4875)
 [GZ]
C. B. Garcia and W. I. Zangwill, Pathways to solutions, fixed points and equilibria, PrenticeHall, Englewood Cliffs, N. J., 1981.
 [Go]
Clovis
C. Gonzaga, An algorithm for solving linear programming problems in
𝑂(𝑛³𝐿) operations, Progress in
mathematical programming (Pacific Grove, CA, 1987) Springer, New York,
1989, pp. 1–28. MR 982713
(90e:90078)
 [GMN]
J. Guckenheimer, J. Moser, and S. E. Newhouse, Dynamical systems, C.I.M.E. Lectures, Birkhäuser, Boston, Mass., 1980.
 [H]
D. Hilbert, Grundlagen der Geometrie, 7th ed., Leipzig, 1930. (English transl., Foundations of geometry.)
 [HK]
Kenneth
Hoffman and Ray
Kunze, Linear algebra, PrenticeHall Mathematics Series,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1961. MR 0125849
(23 #A3146)
 [Ho]
J. Hooker, Karmarkar's linear programming algorithm, Interfaces 16 (1986), 7590.
 [K]
N.
Karmarkar, A new polynomialtime algorithm for linear
programming, Combinatorica 4 (1984), no. 4,
373–395. MR
779900 (86i:90072), http://dx.doi.org/10.1007/BF02579150
 [KLSW]
Narendra
K. Karmarkar, Jeffrey
C. Lagarias, Lev
Slutsman, and Pyng
Wang, Power series variants of Karmarkartype algorithms,
AT&T Tech. J. 68 (1989), no. 3, 20–36. MR 1021069
(91g:90099)
 [KV]
S. Kapoor and P. M. Vaidya, First algorithms for convex quadratic programming and multicommodity flows, Proc. 18th ACM Sympos. on Theory of Computing, 1986, pp. 147159.
 [KMY]
Masakazu
Kojima, Shinji
Mizuno, and Akiko
Yoshise, A primaldual interior point algorithm for linear
programming, Progress in mathematical programming (Pacific Grove, CA,
1987) Springer, New York, 1989, pp. 29–47. MR 982714
(90k:90093)
 [L3]
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
(91g:90100), http://dx.doi.org/10.1090/S00029947199010581990
 [Ln]
Cornelius
Lanczos, The Variational Principles of Mechanics, Mathematical
Expositions, no. 4, University of Toronto Press, Toronto, Ont., 1949. MR 0034139
(11,549a)
 [M]
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
 [M2]
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
(90c:90147)
 [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 (90c:90148), http://dx.doi.org/10.1287/moor.14.1.97
 [Mo]
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
(83a:58042a)
 [N]
J.
L. Nazareth, Homotopy techniques in linear programming,
Algorithmica 1 (1986), no. 4, 529–535. MR 880737
(89b:90129), http://dx.doi.org/10.1007/BF01840461
 [Os]
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
(88f:90097), http://dx.doi.org/10.1017/S0334270000005610
 [Re]
James
Renegar, A polynomialtime algorithm, based on Newton’s
method, for linear programming, Math. Programming 40
(1988), no. 1, (Ser. A), 59–93. MR 923697
(89b:90130), http://dx.doi.org/10.1007/BF01580724
 [R1]
R.
T. Rockafellar, Conjugates and Legendre transforms of convex
functions, Canad. J. Math. 19 (1967), 200–205.
MR
0213496 (35 #4358)
 [R2]
, Convex analysis, Princeton Univ. Press, Princeton, N. J., 1970.
 [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)
Lecture Notes in Control and Inform. Sci., vol. 84, Springer, Berlin,
1986, pp. 866–875. MR 903521
(88g:90133), http://dx.doi.org/10.1007/BFb0043914
 [So2]
, A new method for solving a set of linear (convex) inequalities and its application for identification and optimization, Proc. Sympos. on Dynamic Modelling, IFACIFORS, Budapest, June 1986.
 [SW]
Josef
Stoer and Christoph
Witzgall, Convexity and optimization in finite dimensions. I,
Die Grundlehren der mathematischen Wissenschaften, Band 163,
SpringerVerlag, New YorkBerlin, 1970. MR 0286498
(44 #3707)
 [TB]
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
(88c:90089), http://dx.doi.org/10.1007/BF01840455
 [V]
P. Vaidya, An algorithm for linear programming which requires arithmetic operations, Proc. 19th ACM Sympos. on Theory of Computing, 1987, pp. 2938.
 [VMF]
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 (88e:90052), http://dx.doi.org/10.1007/BF01840454
 [AKRV]
 I. Adler, N. Karmarkar, M. Resende, and G. Veiga, An implementation of Karmarkar's algorithm for linear programming, preprint, Univ. of California, Berkeley, May 1986.
 [A]
 K. Anstreicher, A monotonic projective algorithm for fractional linear programming, Algorithmica 1 (1986), 483498. MR 880734 (88f:90162)
 [Ar]
 V. I. Arnold, Mathematical methods of classical mechanics, SpringerVerlag, New York, 1978. MR 0690288 (57:14033b)
 [B]
 E. R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Math. Programming 36 (1986), 174182. MR 866987 (88h:90120)
 [BL1]
 D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming. I. Affine and projective scaling trajectories, Trans. Amer. Math. Soc. (to appear). MR 1005525 (90h:90098a)
 [BL]
 , Karmarkar's linear programming algorithm and Newton's method, Math. Programming (to appear).
 [BM]
 S. Bochner and W. T. Martin, Several complex variables, Princeton Univ. Press, Princeton, N. J., 1948. MR 0027863 (10:366a)
 [BT]
 B. Bernstein and R. A. Toupin, Some properties of the Hessian of a strictly convex function, J. Reine Angew. Math. 210 (1962), 6572. MR 0145024 (26:2561)
 [CH]
 R. Courant and D. Hilbert, Methods of mathematical physics, Vols. I, II, Wiley, New York, 1962.
 [D1]
 I. I. Dikin, Iterative solution of problems of linear and quadratic programming, Dokl. Akad. Nauk SSSR 174 (1967), 747748. (English transl., Soviet Math. Dokl. 8 (1967), 674675.) MR 0221850 (36:4902)
 [D2]
 , About the convergence of an iterative process, Controllable Systems IM IK SO AN SSSR 1974, No. 12, 5460. (Russian)
 [F]
 W. Fenchel, On conjugate convex functions, Canad. J. Math. 1 (1949), 7377. MR 0028365 (10:435b)
 [FM]
 A. V. Fiacco and G. W. McCormick, Nonlinear programming: Sequential unconstrained minimization techniques, Wiley, New York, 1968. MR 0243831 (39:5152)
 [Fl]
 W. H. Fleming, Functions of several variables, AddisonWesley, Reading, Mass., 1965. MR 0174675 (30:4875)
 [GZ]
 C. B. Garcia and W. I. Zangwill, Pathways to solutions, fixed points and equilibria, PrenticeHall, Englewood Cliffs, N. J., 1981.
 [Go]
 C. Gonzaga, An algorithm for solving linear programming problems in operations, Progress in Mathematical Programming, InteriorPoint and Related Methods (N. Megiddo, Ed.), SpringerVerlag, New York, 1989, pp. 128. MR 982713 (90e:90078)
 [GMN]
 J. Guckenheimer, J. Moser, and S. E. Newhouse, Dynamical systems, C.I.M.E. Lectures, Birkhäuser, Boston, Mass., 1980.
 [H]
 D. Hilbert, Grundlagen der Geometrie, 7th ed., Leipzig, 1930. (English transl., Foundations of geometry.)
 [HK]
 K. Hoffman and R. Kunze, Linear algebra, PrenticeHall, Englewood Cliffs, N. J., 1961. MR 0125849 (23:A3146)
 [Ho]
 J. Hooker, Karmarkar's linear programming algorithm, Interfaces 16 (1986), 7590.
 [K]
 N. Karmarkar, A new polynomial time algorithm for linear programming, Combinatorica 4 (1984), 373395. MR 779900 (86i:90072)
 [KLSW]
 N. Karmarkar, J. C. Lagarias, L. Slutsman and P. Wang, Powerseries variants of Karmarkartype algorithms, A.T.&T. Tech. J. 68 (to appear). MR 1021069 (91g:90099)
 [KV]
 S. Kapoor and P. M. Vaidya, First algorithms for convex quadratic programming and multicommodity flows, Proc. 18th ACM Sympos. on Theory of Computing, 1986, pp. 147159.
 [KMY]
 M. Kojima, S. Mizuno, and A. Yoshise, A primaldual interior point algorithm for linear programming, Progress in Mathematical Programming, InteriorPoint and Related Methods (N. Megiddo, Ed.), SpringerVarlag, New York, 1989, pp. 2948. MR 982714 (90k:90093)
 [L3]
 J. C. Lagarias, The nonlinear geometry of linear programming. III, Projective Legendre transform coordinates and Hilbert geometry, Trans. Amer. Math. Soc. (to appear). MR 1058199 (91g:90100)
 [Ln]
 C. Lanczos, The variational principles of mechanics, Univ. of Toronto Press, Toronto, 1949. MR 0034139 (11:549a)
 [M]
 N. Megiddo, On the complexity of linear programming, Advances in Economic Theory (T. Bewley, Ed.), Cambridge Univ. Press, 1986. MR 1117042
 [M2]
 , Pathways to the optimal set in linear programming, Progress in Mathematical Programming, InteriorPoint and Related Methods (N. Megiddo, Ed.), SpringerVerlag, New York, 1989, pp. 131158. MR 982720 (90c:90147)
 [MS]
 N. Megiddo and M. Shub, Boundary behavior of interior point algorithms in linear programming, preprint, IBM Research Report RJ 5319, 1986. MR 984561 (90c:90148)
 [Mo]
 J. Moser, Various aspects of integrable Hamiltonian systems, pp. 233290 in [GMN]. MR 589592 (83a:58042a)
 [N]
 J. L. Nazareth, Homotopy techniques in linear programming, Algorithmica 1 (1986), 528535. MR 880737 (89b:90129)
 [Os]
 M. R. Osborne, Dual barrier functions with superfast rates of convergence for the linear programming problem, J. Austral. Math. Soc. (Ser. B) 29 (1987), 3958. MR 889576 (88f:90097)
 [Re]
 J. Renegar, A polynomialtime algorithm, based on Newton's method, for linear programming, Math. Programming 40 (1988), 5994. MR 923697 (89b:90130)
 [R1]
 R. T. Rockafellar, Conjugates and Legendre transforms of convex functions, Canad. J. Math. 19 (1967), 200205. MR 0213496 (35:4358)
 [R2]
 , Convex analysis, Princeton Univ. Press, Princeton, N. J., 1970.
 [So1]
 Gy. Sonnevend, An "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, Proc. 12th IFIP Conf. System Modelling, Budapest, 1985, Lecture Notes in Computer Science, 1986. MR 903521 (88g:90133)
 [So2]
 , A new method for solving a set of linear (convex) inequalities and its application for identification and optimization, Proc. Sympos. on Dynamic Modelling, IFACIFORS, Budapest, June 1986.
 [SW]
 J. Stoer and C. Witzgall, Convexity and optimization in finite dimensions. I, SpringerVerlag, New York, 1970. MR 0286498 (44:3707)
 [TB]
 M. Todd and B. Burrell, An extension of Karmarkar's algorithm for linear programming using dual variables, Algorithmica 1 (1986), 409424. MR 880731 (88c:90089)
 [V]
 P. Vaidya, An algorithm for linear programming which requires arithmetic operations, Proc. 19th ACM Sympos. on Theory of Computing, 1987, pp. 2938.
 [VMF]
 R. J. Vanderbei, M. J. Meketon and B. A. Freedman, A modification of Karmarkar's linear programming algorithm, Algorithmica 1 (1986), 395407. MR 880730 (88e:90052)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC:
90C05,
34A99,
52A40
Retrieve articles in all journals
with MSC:
90C05,
34A99,
52A40
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029947198910055268
PII:
S 00029947(1989)10055268
Article copyright:
© Copyright 1989
American Mathematical Society
