Electronic ISBN:  9780821877029 
Product Code:  CONM/114.E 
List Price:  $78.00 
MAA Member Price:  $70.20 
AMS Member Price:  $62.40 

Book DetailsContemporary MathematicsVolume: 114; 1991; 341 ppMSC: Primary 90; Secondary 00;
In recent years, there has been intense work in linear and nonlinear programming, much of it centered on understanding and extending the ideas underlying N. Karmarkar's interiorpoint linear programming algorithm, which was presented in 1984. This interdisciplinary research was the subject of an AMS Summer Research Conference on Mathematical Developments Arising from Linear Programming, held at Bowdoin College in the summer of 1988, which brought together researchers in mathematics, computer science, and operations research. This volume contains the proceedings from the conference.
Among the topics covered in this book are: completely integrable dynamical systems arising in optimization problems, Riemannian geometry and interiorpoint linear programming methods, concepts of approximate solution of linear programs, average case analysis of the simplex method, and recent results in convex polytopes. Some of the papers extend interiorpoint methods to quadratic programming, the linear complementarity problem, convex programming, multicriteria optimization, and integer programming. Other papers study the continuous trajectories underlying interior point methods. This book will be an excellent resource for those interested in the latest developments arising from Karmarkar's linear programming algorithm and in pathfollowing methods for solving differential equations. 
Table of Contents

1. Recent Progress and New Directions [ MR 1097861 ]

Carl W. Lee  Some recent results on convex polytopes [ MR 1097862 ]

KarlHeinz Borgwardt  Probabilistic analysis of the simplex method [ MR 1097863 ]

Nimrod Megiddo  On solving the linear programming problem approximately [ MR 1097864 ]

Narendra Karmarkar  Riemannian geometry underlying interiorpoint methods for linear programming [ MR 1097865 ]

A. M. Bloch  Steepest descent, linear programming, and Hamiltonian flows [ MR 1097866 ]

2. InteriorPoint Methods for Linear Programming [ MR 1097861 ]

Yinyu Ye  An $O(n^3L)$ potential reduction algorithm for linear programming [ MR 1097867 ]

R. J. Vanderbei and J. C. Lagarias  I. I. Dikin’s convergence result for the affinescaling algorithm [ MR 1097868 ]

Irvin J. Lustig  Phase $1$ search directions for a primaldual interior point method for linear programming [ MR 1097869 ]

Earl R. Barnes  Some results concerning convergence of the affine scaling algorithm [ MR 1097870 ]

Kurt M. Anstreicher  Dual ellipsoids and degeneracy in the projective algorithm for linear programming [ MR 1097871 ]

Miroslav D. Ašić, Vera V. KovačevićVujčić and Mirjana D. RadosavljevićNikolić  A note on limiting behavior of the projective and the affine rescaling algorithms [ MR 1097872 ]

3. Trajectories of InteriorPoint Methods [ MR 1097861 ]

Christoph Witzgall, Paul T. Boggs and Paul D. Domich  On the convergence behavior of trajectories for linear programming [ MR 1097873 ]

Ilan Adler and Renato D. C. Monteiro  Limiting behavior of the affine scaling continuous trajectories for linear programming problems [ MR 1097874 ]

Renato D. C. Monteiro  Convergence and boundary behavior of the projective scaling trajectories for linear programming [ MR 1097875 ]

4. Nonlinear Optimization [ MR 1097861 ]

F. Jarre, G. Sonnevend and J. Stoer  On the complexity of a numerical algorithm for solving generalized convex quadratic programs by following a central path [ MR 1097876 ]

Bahman Kalantari  Canonical problems for quadratic programming and projective methods for their solution [ MR 1097877 ]

Sanjay Mehrotra and Jie Sun  An interior point algorithm for solving smooth convex programs based on Newton’s method [ MR 1097878 ]

A. A. Goldstein  A modified Kantorovich inequality for the convergence of Newton’s method [ MR 1097879 ]

5. Integer Programming and MultiObjective Programming [ MR 1097861 ]

Narendra Karmarkar  An interiorpoint approach to NPcomplete problems. I [ MR 1097880 ]

John E. Mitchell and Michael J. Todd  Solving matching problems using Karmarkar’s algorithm [ MR 1097881 ]

S. S. Abhyankar, T. L. Morin and T. Trafalis  Efficient faces of polytopes: interior point algorithms, parameterization of algebraic varieties, and multiple objective optimization [ MR 1097882 ]


Request Review Copy

Get Permissions
 Book Details
 Table of Contents

 Request Review Copy
 Get Permissions
In recent years, there has been intense work in linear and nonlinear programming, much of it centered on understanding and extending the ideas underlying N. Karmarkar's interiorpoint linear programming algorithm, which was presented in 1984. This interdisciplinary research was the subject of an AMS Summer Research Conference on Mathematical Developments Arising from Linear Programming, held at Bowdoin College in the summer of 1988, which brought together researchers in mathematics, computer science, and operations research. This volume contains the proceedings from the conference.
Among the topics covered in this book are: completely integrable dynamical systems arising in optimization problems, Riemannian geometry and interiorpoint linear programming methods, concepts of approximate solution of linear programs, average case analysis of the simplex method, and recent results in convex polytopes. Some of the papers extend interiorpoint methods to quadratic programming, the linear complementarity problem, convex programming, multicriteria optimization, and integer programming. Other papers study the continuous trajectories underlying interior point methods. This book will be an excellent resource for those interested in the latest developments arising from Karmarkar's linear programming algorithm and in pathfollowing methods for solving differential equations.

1. Recent Progress and New Directions [ MR 1097861 ]

Carl W. Lee  Some recent results on convex polytopes [ MR 1097862 ]

KarlHeinz Borgwardt  Probabilistic analysis of the simplex method [ MR 1097863 ]

Nimrod Megiddo  On solving the linear programming problem approximately [ MR 1097864 ]

Narendra Karmarkar  Riemannian geometry underlying interiorpoint methods for linear programming [ MR 1097865 ]

A. M. Bloch  Steepest descent, linear programming, and Hamiltonian flows [ MR 1097866 ]

2. InteriorPoint Methods for Linear Programming [ MR 1097861 ]

Yinyu Ye  An $O(n^3L)$ potential reduction algorithm for linear programming [ MR 1097867 ]

R. J. Vanderbei and J. C. Lagarias  I. I. Dikin’s convergence result for the affinescaling algorithm [ MR 1097868 ]

Irvin J. Lustig  Phase $1$ search directions for a primaldual interior point method for linear programming [ MR 1097869 ]

Earl R. Barnes  Some results concerning convergence of the affine scaling algorithm [ MR 1097870 ]

Kurt M. Anstreicher  Dual ellipsoids and degeneracy in the projective algorithm for linear programming [ MR 1097871 ]

Miroslav D. Ašić, Vera V. KovačevićVujčić and Mirjana D. RadosavljevićNikolić  A note on limiting behavior of the projective and the affine rescaling algorithms [ MR 1097872 ]

3. Trajectories of InteriorPoint Methods [ MR 1097861 ]

Christoph Witzgall, Paul T. Boggs and Paul D. Domich  On the convergence behavior of trajectories for linear programming [ MR 1097873 ]

Ilan Adler and Renato D. C. Monteiro  Limiting behavior of the affine scaling continuous trajectories for linear programming problems [ MR 1097874 ]

Renato D. C. Monteiro  Convergence and boundary behavior of the projective scaling trajectories for linear programming [ MR 1097875 ]

4. Nonlinear Optimization [ MR 1097861 ]

F. Jarre, G. Sonnevend and J. Stoer  On the complexity of a numerical algorithm for solving generalized convex quadratic programs by following a central path [ MR 1097876 ]

Bahman Kalantari  Canonical problems for quadratic programming and projective methods for their solution [ MR 1097877 ]

Sanjay Mehrotra and Jie Sun  An interior point algorithm for solving smooth convex programs based on Newton’s method [ MR 1097878 ]

A. A. Goldstein  A modified Kantorovich inequality for the convergence of Newton’s method [ MR 1097879 ]

5. Integer Programming and MultiObjective Programming [ MR 1097861 ]

Narendra Karmarkar  An interiorpoint approach to NPcomplete problems. I [ MR 1097880 ]

John E. Mitchell and Michael J. Todd  Solving matching problems using Karmarkar’s algorithm [ MR 1097881 ]

S. S. Abhyankar, T. L. Morin and T. Trafalis  Efficient faces of polytopes: interior point algorithms, parameterization of algebraic varieties, and multiple objective optimization [ MR 1097882 ]