**Contemporary Mathematics**

Volume: 114;
1991;
341 pp;
Softcover

MSC: Primary 90;
Secondary 00

Print ISBN: 978-0-8218-5121-0

Product Code: CONM/114

List Price: $78.00

AMS Member Price: $62.40

MAA Member Price: $70.20

**Electronic ISBN: 978-0-8218-7702-9
Product Code: CONM/114.E**

List Price: $78.00

AMS Member Price: $62.40

MAA Member Price: $70.20

# Mathematical Developments Arising from Linear Programming

Share this page *Edited by *
*Jeffrey C. Lagarias; Michael J. Todd*

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

## Mathematical Developments Arising from Linear Programming

- Contents ix10 free
- 1. Recent Progress and New Directions 116 free
- Some Recent Results on Convex Polytopes 318
- Probabilistic Analysis of the Simplex Method 2136
- On Solving the Linear Programming Problem Approximately 3550
- Riemannian Geometry Underlying Interior-Point Methods for Linear Programming 5166
- Steepest Descent, Linear Programming, and Hamiltonian Flows 7792

- 2. Interior-Point Methods for Linear Programming 89104
- An O(n3 L) Potential Reduction Algorithm for Linear Programming 91106
- I. I. Dikin's Convergence Result for the Affine-Scaling Algorithm 109124
- Phase I Search Directions for a Primal-Dual Interior Point Method for Linear Programming 121136
- Some Results Concerning Convergence of the Affine Scaling Algorithm 131146
- Dual Ellipsoids and Degeneracy in the Projective Algorithm for Linear Programming 141156
- A Note on Limiting Behavior of the Projective and the Affine Rescaling Algorithms 151166

- 3. Trajectories of Interior-Point Methods 159174
- 4. Nonlinear Optimization 231246
- On the Complexity of a Numerical Algorithm for Solving Generalized Convex Quadratic Programs by Following a Central Path 233248
- Canonical Problems for Quadratic Programming and Projective Methods for Their Solution 243258
- An Interior Point Algorithm for Solving Smooth Convex Programs Based on Newton's Method 265280
- A Modified Kantorovich Inequality for the Convergence of Newton's Method 285300

- 5. Integer Programming and Multi-Objective Programming 295310