Algorithmic Principles of Mathematical Programming

✍ Scribed by Ulrich Faigle, Walter Kern, Georg Still (auth.)

• Publisher: Springer Netherlands
• Year: 2002
• Tongue: English
• Leaves: 342
• Series: Kluwer Texts in the Mathematical Sciences 24
• Edition: 1
• Category: Library

✦ Synopsis

Algorithmic Principles of Mathematical Programming investigates the mathematical structures and principles underlying the design of efficient algorithms for optimization problems. Recent advances in algorithmic theory have shown that the traditionally separate areas of discrete optimization, linear programming, and nonlinear optimization are closely linked. This book offers a comprehensive introduction to the whole subject and leads the reader to the frontiers of current research. The prerequisites to use the book are very elementary. All the tools from numerical linear algebra and calculus are fully reviewed and developed. Rather than attempting to be encyclopedic, the book illustrates the important basic techniques with typical problems. The focus is on efficient algorithms with respect to practical usefulness. Algorithmic complexity theory is presented with the goal of helping the reader understand the concepts without having to become a theoretical specialist. Further theory is outlined and supplemented with pointers to the relevant literature.

✦ Table of Contents

Front Matter....Pages i-x
Real Vector Spaces....Pages 1-20
Linear Equations and Linear Inequalities....Pages 21-53
Polyhedra....Pages 55-70
Linear Programs and the Simplex Method....Pages 71-94
Lagrangian Duality....Pages 95-108
An Interior Point Algorithm for Linear Programs....Pages 109-121
Network Flows....Pages 123-151
Complexity....Pages 153-172
Integer Programming....Pages 173-196
Convex Sets and Convex Functions....Pages 197-240
Unconstrained Optimization....Pages 241-271
Constrained Nonlinear Optimization....Pages 273-323
Back Matter....Pages 325-339

✦ Subjects

Optimization; Mathematics of Computing; Algorithms; Discrete Mathematics in Computer Science; Theory of Computation