Linear programming : foundations and extensions / Robert J. Vanderbei.

Format:

Book

Author/Creator:

Vanderbei, Robert J.

Contributor:

Louis A. Duhring Fund.

Series:

International series in operations research & management science ; 114.

International series in operations research & management science ; 114

Language:

English

Subjects (All):

Linear programming.

Mathematical optimization.

Physical Description:

xix, 464 pages : illustrations (some color) ; 25 cm.

Edition:

Third edition.

Place of Publication:

New York : Springer, [2008]

Summary:

Linear Programming: Foundations and Extensions, Third Edition is an introduction to the field of optimization. The book emphasizes constrained optimization, beginning with a substantial treatment of linear programming, and proceeds to cover convex analysis, network flows, integer programming, quadratic programming, and convex optimization. The book is carefully written with specific examples and concrete algorithms preceding more abstract topics. Topics are clearly developed with a large number of numerical examples worked out in detail.

Moreover, Linear Programming: Foundations and Extensions, Third Edition underscores the purpose of optimization-to solve practical problems on a computer. Accordingly, the book is coordinated with free efficient C programs that implement the major algorithms studied: The two-phase simplex method, The primal-dual simplex method, The path-following interior-point method, The homogeneous self-dual methods. In addition, there are online JAVA applets which illustrate various pivot rules and variants of the simplex method, both for linear programming and for network flows. These C programs and JAVA tools can be found on the books webpage: http://www.princeton.edu/-rvdb/LPbook/. Also check the book's webpage for new online instructional tools and exercises that have been added in the new edition.

Contents:

Part 1 Basic Theory-The Simplex Method and Duality 1

1 Managing a Production Facility 3

2 The Linear Programming Problem 6

Chapter 2 The Simplex Method 13

2 The Simplex Method 16

3 Initialization 19

4 Unboundedness 22

5 Geometry 22

Chapter 3 Degeneracy 29

1 Definition of Degeneracy 29

2 Two Examples of Degenerate Problems 29

3 The Perturbation/Lexicographic Method 32

4 Bland's Rule 36

5 Fundamental Theorem of Linear Programming 38

6 Geometry 39

Chapter 4 Efficiency of the Simplex Method 45

1 Performance Measures 45

2 Measuring the Size of a Problem 45

3 Measuring the Effort to Solve a Problem 46

4 Worst-Case Analysis of the Simplex Method 47

Chapter 5 Duality Theory 55

1 Motivation-Finding Upper Bounds 55

2 The Dual Problem 57

3 The Weak Duality Theorem 58

4 The Strong Duality Theorem 60

5 Complementary Slackness 66

6 The Dual Simplex Method 68

7 A Dual-Based Phase I Algorithm 71

8 The Dual of a Problem in General Form 73

9 Resource Allocation Problems 74

10 Lagrangian Duality 78

Chapter 6 The Simplex Method in Matrix Notation 89

1 Matrix Notation 89

2 The Primal Simplex Method 91

4 The Dual Simplex Method 101

5 Two-Phase Methods 104

6 Negative Transpose Property 105

Chapter 7 Sensitivity and Parametric Analyses 111

1 Sensitivity Analysis 111

2 Parametric Analysis and the Homotopy Method 115

3 The Parametric Self-Dual Simplex Method 119

Chapter 8 Implementation Issues 125

1 Solving Systems of Equations: LU-Factorization 126

2 Exploiting Sparsity 130

3 Reusing a Factorization 136

4 Performance Tradeoffs 140

5 Updating a Factorization 141

6 Shrinking the Bump 145

7 Partial Pricing 146

8 Steepest Edge 147

Chapter 9 Problems in General Form 151

1 The Primal Simplex Method 151

2 The Dual Simplex Method 153

Chapter 10 Convex Analysis 161

1 Convex Sets 161

2 Caratheodory's Theorem 163

3 The Separation Theorem 165

4 Farkas' Lemma 167

5 Strict Complementarity 168

Chapter 11 Game Theory 173

1 Matrix Games 173

2 Optimal Strategies 175

3 The Minimax Theorem 177

4 Poker 181

Chapter 12 Regression 189

1 Measures of Mediocrity 189

2 Multidimensional Measures: Regression Analysis 191

3 L[superscript 2]-Regression 193

4 L[superscript 1]-Regression 195

5 Iteratively Reweighted Least Squares 196

6 An Example: How Fast is the Simplex Method? 198

7 Which Variant of the Simplex Method is Best? 202

Chapter 13 Financial Applications 211

1 Portfolio Selection 211

2 Option Pricing 216

Part 2 Network-Type Problems 223

Chapter 14 Network Flow Problems 225

1 Networks 225

2 Spanning Trees and Bases 228

3 The Primal Network Simplex Method 233

4 The Dual Network Simplex Method 237

6 The Integrality Theorem 243

Chapter 15 Applications 253

1 The Transportation Problem 253

2 The Assignment Problem 255

3 The Shortest-Path Problem 256

4 Upper-Bounded Network Flow Problems 259

5 The Maximum-Flow Problem 262

Chapter 16 Structural Optimization 271

2 Incidence Matrices 273

3 Stability 274

4 Conservation Laws 276

5 Minimum-Weight Structural Design 279

6 Anchors Away 281

Part 3 Interior-Point Methods 287

Chapter 17 The Central Path 289

Warning: Nonstandard Notation Ahead 289

1 The Barrier Problem 289

2 Lagrange Multipliers 292

3 Lagrange Multipliers Applied to the Barrier Problem 295

4 Second-Order Information 297

5 Existence 297

Chapter 18 A Path-Following Method 303

1 Computing Step Directions 303

2 Newton's Method 305

3 Estimating an Appropriate Value for the Barrier Parameter 306

4 Choosing the Step Length Parameter 307

5 Convergence Analysis 308

Chapter 19 The KKT System 319

1 The Reduced KKT System 319

2 The Normal Equations 320

3 Step Direction Decomposition 322

Chapter 20 Implementation Issues 327

1 Factoring Positive Definite Matrices 327

2 Quasidefinite Matrices 331

3 Problems in General Form 337

Chapter 21 The Affine-Scaling Method 345

1 The Steepest Ascent Direction 345

2 The Projected Gradient Direction 347

3 The Projected Gradient Direction with Scaling 349

4 Convergence 353

5 Feasibility Direction 355

6 Problems in Standard Form 356

Chapter 22 The Homogeneous Self-Dual Method 361

1 From Standard Form to Self-Dual Form 361

2 Homogeneous Self-Dual Problems 362

3 Back to Standard Form 372

4 Simplex Method vs Interior-Point Methods 375

Part 4 Extensions 383

Chapter 23 Integer Programming 385

1 Scheduling Problems 385

2 The Traveling Salesman Problem 387

3 Fixed Costs 390

4 Nonlinear Objective Functions 390

5 Branch-and-Bound 392

Chapter 24 Quadratic Programming 407

1 The Markowitz Model 407

2 The Dual 412

3 Convexity and Complexity 414

4 Solution Via Interior-Point Methods 418

Chapter 25 Convex Programming 425

1 Differentiable Functions and Taylor Approximations 425

2 Convex and Concave Functions 426

3 Problem Formulation 426

4 Solution Via Interior-Point Methods 427

5 Successive Quadratic Approximations 429

6 Merit Functions 429

7 Parting Words 433

1 The Self-Dual Simplex Method 438

2 The Homogeneous Self-Dual Method 441.

Notes:

Includes bibliographical references (pages 449-456) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Louis A. Duhring Fund.

ISBN:

0387743871

9780387743875

9780387743882

038774388X

OCLC:

173807299