Interior Point Methods for Linear Optimization

1. Front Matter

   Pages i-xxiv

   PDF

2. Introduction

   Pages 1-11

3. Introduction: Theory and Complexity

   1. Duality Theory for Linear Optimization

      Pages 15-46

   2. A Polynomial Algorithm for the Self—dual Model

      Pages 47-70

   3. Solving the Canonical Problem

      Pages 71-83

4. The Logarithmic Barrier Approach

   1. Preliminaries

      Pages 87-105

   2. The Dual Logarithmic Barrier Method

      Pages 107-147

   3. The Primal—Dual Logarithmic Barrier Method

      Pages 149-212

   4. Initialization

      Pages 213-216

5. The Target-following Approach

   1. Preliminaries

      Pages 219-234

   2. The Primal-Dual Newton Method

      Pages 235-245

   3. Applications

      Pages 247-258

   4. The Dual Newton Method

      Pages 259-268

   5. The Primal Newton Method

      Pages 269-275

   6. Application to the Method of Centers

      Pages 277-285

6. Miscellaneous Topics

   1. Karmarkar’s Projective Method

      Pages 289-305

   2. More Properties of the Central Path

      Pages 307-316

   3. Partial Updating

      Pages 317-328

   4. Higher-Order Methods

      Pages 329-359

   5. Parametric and Sensitivity Analysis

      Pages 361-399

Interior Point Methods for Linear Optimization is a comprehensive, thorough textbook on interior point methods (IPMs). The era of IPMs was initiated by N. Karmarkar’s 1984 paper, which triggered turbulent research and reshaped almost all areas of optimization theory and computational practice. This book gives a comprehensive review of the main results of more than a decade of IPM research. Numerous exercises are provided to aid in understanding the material.

• Interior point methods
• Linear programming
• Polynomial complexity
• algorithms
• complexity
• linear optimization
• optimization

From the reviews of the second edition:

"The second edition of this successful book on interior point methods for linear optimization appears eight years after the first one. It presents a unified framework for these algorithms and it is a comprehensive treatment of linear optimization from the perspective of interior point methods. … The presentation is clear and comprehensible, but concise, it comes along with many examples and illustrations … . Almost all aspects of interior point methods are discussed in this highly recommendable book … ." (Petra Huhn, Mathematical Methods of Operations Research, Vol. 65 (1), 2007)

• Delft University of Technology, The Netherlands

  Cornelis Roos

• McMaster University, Ontario, Canada

  Tamás Terlaky

• University of Geneva, Switzerland

  Jean-Philiipe Vial

Policies and ethics