Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Mathematical Developments Arising from Linear Programming
 
Edited by: Jeffrey C. Lagarias
Michael J. Todd
Mathematical Developments Arising from Linear Programming
eBook ISBN:  978-0-8218-7702-9
Product Code:  CONM/114.E
List Price: $125.00
MAA Member Price: $112.50
AMS Member Price: $100.00
Add to cart
Mathematical Developments Arising from Linear Programming
Click above image for expanded view
Mathematical Developments Arising from Linear Programming
Edited by: Jeffrey C. Lagarias
Michael J. Todd
eBook ISBN:  978-0-8218-7702-9
Product Code:  CONM/114.E
List Price: $125.00
MAA Member Price: $112.50
AMS Member Price: $100.00
Add to cart
  • Book Details
     
     
    Contemporary Mathematics
    Volume: 114; 1991; 341 pp
    MSC: 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 interior-point 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 interior-point 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 interior-point methods to quadratic programming, the linear complementarity problem, convex programming, multi-criteria 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 path-following 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 ]
    • Karl-Heinz 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 interior-point methods for linear programming [ MR 1097865 ]
    • A. M. Bloch — Steepest descent, linear programming, and Hamiltonian flows [ MR 1097866 ]
    • 2. Interior-Point 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 affine-scaling algorithm [ MR 1097868 ]
    • Irvin J. Lustig — Phase $1$ search directions for a primal-dual 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 Interior-Point 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 Multi-Objective Programming [ MR 1097861 ]
    • Narendra Karmarkar — An interior-point approach to NP-complete 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 ]
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Permission – for use of book, eBook, or Journal content
    Accessibility – to request an alternate format of an AMS title
Contemporary Mathematics
Volume: 114; 1991; 341 pp
MSC: 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 interior-point 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 interior-point 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 interior-point methods to quadratic programming, the linear complementarity problem, convex programming, multi-criteria 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 path-following methods for solving differential equations.
  • 1. Recent Progress and New Directions [ MR 1097861 ]
  • Carl W. Lee — Some recent results on convex polytopes [ MR 1097862 ]
  • Karl-Heinz 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 interior-point methods for linear programming [ MR 1097865 ]
  • A. M. Bloch — Steepest descent, linear programming, and Hamiltonian flows [ MR 1097866 ]
  • 2. Interior-Point 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 affine-scaling algorithm [ MR 1097868 ]
  • Irvin J. Lustig — Phase $1$ search directions for a primal-dual 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 Interior-Point 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 Multi-Objective Programming [ MR 1097861 ]
  • Narendra Karmarkar — An interior-point approach to NP-complete 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 ]
Review Copy – for publishers of book reviews
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Powered by MathJax
Please select which format for which you are requesting permissions.