The nonlinear geometry of linear programming. I. Affine and projective scaling trajectories
Authors:
D. A. Bayer and J. C. Lagarias
Journal:
Trans. Amer. Math. Soc. 314 (1989), 499526
MSC:
Primary 90C05; Secondary 34A99, 52A40
MathSciNet review:
1005525
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: This series of papers studies a geometric structure underlying Karmarkar's projective scaling algorithm for solving linear programming problems. A basic feature of the projective scaling algorithm is a vector field depending on the objective function which is defined on the interior of the polytope of feasible solutions of the linear program. The geometric structure studied is the set of trajectories obtained by integrating this vector field, which we call trajectories. We also study a related vector field, the affine scaling vector field, and its associated trajectories, called trajectories. The affine scaling vector field is associated to another linear programming algorithm, the affine scaling algorithm. Affine and projective scaling vector fields are each defined for linear programs of a special form, called strict standard form and canonical form, respectively. This paper derives basic properties of trajectories and trajectories. It reviews the projective and affine scaling algorithms, defines the projective and affine scaling vector fields, and gives differential equations for trajectories and trajectories. It shows that projective transformations map trajectories into trajectories. It presents Karmarkar's interpretation of trajectories as steepest descent paths of the objective function with respect to the Riemannian geometry restricted to the relative interior of the polytope of feasible solutions. trajectories of a canonical form linear program are radial projections of trajectories of an associated standard form linear program. As a consequence there is a polynomial time linear programming algorithm using the affine scaling vector field of this associated linear program: This algorithm is essentially Karmarkar's algorithm. These trajectories are studied in subsequent papers by two nonlinear changes of variables called Legendre transform coordinates and projective Legendre transform coordinates, respectively. It will be shown that trajectories have an algebraic and a geometric interpretation. They are algebraic curves, and they are geodesics (actually distinguished chords) of a geometry isometric to a Hubert geometry on a polytope combinatorially dual to the polytope of feasible solutions. The trajectories of strict standard form linear programs have similar interpretations: They are algebraic curves, and are geodesics of a geometry isometric to Euclidean geometry.
 [AKRV]
I. Adler, N. Karmarkar, G. Resende and S. Veiga, An implementation of Karmarkar's algorithm for linear programming, preprint, Univ. of California, Berkeley, 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
 [BL2]
D.
A. Bayer and J.
C. Lagarias, The nonlinear geometry of linear
programming. II. Legendre transform coordinates and central
trajectories, Trans. Amer. Math. Soc.
314 (1989), no. 2,
527–581. MR 1005526
(90h:90098b), http://dx.doi.org/10.1090/S00029947198910055268
 [BP]
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 (85m:53084)
 [Bu]
Herbert
Busemann, The geometry of geodesics, Academic Press Inc., New
York, N. Y., 1955. MR 0075623
(17,779a)
 [Bu2]
Herbert
Busemann, Spaces with distinguished shortest joins, A spectrum
of mathematics (Essays presented to H. G. Forder), Auckland Univ. Press,
Auckland, 1971, pp. 108–120. MR 0431075
(55 #4077)
 [CH]
R. Courant and D. Hubert, 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 SSR 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)
 [H]
D. Hilbert, Grundlagen der Geometrie, 7th ed., Leipzig, 1930. (English transl., Foundations of geometry.)
 [Ho]
J. Hooker, The projective linear programming algorithm, Interfaces 16 (1986), 7590.
 [II]
Masao
Iri and Hiroshi
Imai, A multiplicative barrier function method for linear
programming, Algorithmica 1 (1986), no. 4,
455–482. MR
880733 (88c:90081), http://dx.doi.org/10.1007/BF01840457
 [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, Fast 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)
 [M1]
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]
N. Megiddo and M. Shub, Boundary behavior of interior point algorithms in linear programming, IBM Research Report RJ5319, Sept. 1986.
 [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
 [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.
 [Sh]
Michael
Shub, On the asymptotic behavior of the projective rescaling
algorithm for linear programming, J. Complexity 3
(1987), no. 3, 258–269. MR 919676
(89a:90084), http://dx.doi.org/10.1016/0885064X(87)90015X
 [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)
 [Va]
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, G. Resende and S. Veiga, An implementation of Karmarkar's algorithm for linear programming, preprint, Univ. of California, Berkeley, 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)
 [BL2]
 D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming. II. Legendre transform coordinates, and central trajectories, Trans. Amer. Math. Soc. (to appear). MR 1005526 (90h:90098b)
 [BP]
 H. Busemann and B. B. Phadke, Beltrami's theorem in the large, Pacific J. Math. 115 (1984), 299315. MR 765189 (85m:53084)
 [Bu]
 H. Busemann, The geometry of geodesics, Academic Press, New York, 1955. MR 0075623 (17:779a)
 [Bu2]
 , Spaces with distinguished shortest joins, A Spectrum of Mathematics, Auckland, 1971, pp. 108120. MR 0431075 (55:4077)
 [CH]
 R. Courant and D. Hubert, 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 173 (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 SSR 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)
 [H]
 D. Hilbert, Grundlagen der Geometrie, 7th ed., Leipzig, 1930. (English transl., Foundations of geometry.)
 [Ho]
 J. Hooker, The projective linear programming algorithm, Interfaces 16 (1986), 7590.
 [II]
 M. Iri and H. Imai, A multiplicative barrier function method for linear programming, Algorithmica 1 (1986), 455482. MR 880733 (88c:90081)
 [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, Poser series variants of Karmarkartype algorithms, A.T. & T. Technical J. (to appear). MR 1021069 (91g:90099)
 [KV]
 S. Kapoor and P. M. Vaidya, Fast 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 method for linear programming, Progress in Mathematical Programming, InteriorPoint and Related Methods (N. Megiddo, Ed.), SpringerVerlag, 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)
 [M1]
 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, IBM Research Report RJ5319, Sept. 1986.
 [N]
 J. L. Nazareth, Homotopy techniques in linear programming, Algorithmica 1 (1986), 529535. MR 880737 (89b:90129)
 [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.
 [Sh]
 M. Shub, On the asymptotic behavior of the projective scaling algorithm for linear programming, IBM Tech. Report R5 12522, Feb. 1987. MR 919676 (89a:90084)
 [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)
 [Va]
 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/S00029947198910055256
PII:
S 00029947(1989)10055256
Article copyright:
© Copyright 1989
American Mathematical Society
