Linear Programming : Foundations and Extensions

by Vanderbei, Robert J.

• ISBN13: 9780387743875
• ISBN10: 0387743871
• Edition: 3rd
• Format: Hardcover
• Copyright: 2008-01-01
• Publisher: Springer Verlag

Summary

This Third Edition introduces the latest theory and applications in optimization. It emphasizes constrained optimization, beginning with linear programming and then proceeding to convex analysis, network flows, integer programming, quadratic programming, and convex optimization. You'll discover a host of practical business applications as well as non-business applications. With its focus on solving practical problems, the book features free C programs to implement the major algorithms covered. The book's accompanying website includes the C programs, JAVA tools, and new online instructional tools and exercises.

Table of Contents

Preface	p. xiii
Preface to 2nd Edition	p. xvii
Preface to 3rd Edition	p. xix
Basic Theory-The Simplex Method and Duality	p. 1
Introduction	p. 3
Managing a Production Facility	p. 3
The Linear Programming Problem	p. 6
Exercises	p. 8
Notes	p. 10
The Simplex Method	p. 13
An Example	p. 13
The Simplex Method	p. 16
Initialization	p. 19
Unboundedness	p. 22
Geometry	p. 22
Exercises	p. 24
Notes	p. 27
Degeneracy	p. 29
Definition of Degeneracy	p. 29
Two Examples of Degenerate Problems	p. 29
The Perturbation/Lexicographic Method	p. 32
Bland's Rule	p. 36
Fundamental Theorem of Linear Programming	p. 38
Geometry	p. 39
Exercises	p. 42
Notes	p. 43
Efficiency of the Simplex Method	p. 45
Performance Measures	p. 45
Measuring the Size of a Problem	p. 45
Measuring the Effort to Solve a Problem	p. 46
Worst-Case Analysis of the Simplex Method	p. 47
Exercises	p. 52
Notes	p. 53
Duality Theory	p. 55
Motivation-Finding Upper Bounds	p. 55
The Dual Problem	p. 57
The Weak Duality Theorem	p. 58
The Strong Duality Theorem	p. 60
Complementary Slackness	p. 66
The Dual Simplex Method	p. 68
A Dual-Based Phase I Algorithm	p. 71
The Dual of a Problem in General Form	p. 73
Resource Allocation Problems	p. 74
Lagrangian Duality	p. 78
Exercises	p. 79
Notes	p. 87
The Simplex Method in Matrix Notation	p. 89
Matrix Notation	p. 89
The Primal Simplex Method	p. 91
An Example	p. 96
The Dual Simplex Method	p. 101
Two-Phase Methods	p. 104
Negative Transpose Property	p. 105
Exercises	p. 108
Notes	p. 109
Sensitivity and Parametric Analyses	p. 111
Sensitivity Analysis	p. 111
Parametric Analysis and the Homotopy Method	p. 115
The Parametric Self-Dual Simplex Method	p. 119
Exercises	p. 120
Notes	p. 124
Implementation Issues	p. 125
Solving Systems of Equations: LU-Factorization	p. 126
Exploiting Sparsity	p. 130
Reusing a Factorization	p. 136
Performance Tradeoffs	p. 140
Updating a Factorization	p. 141
Shrinking the Bump	p. 145
Partial Pricing	p. 146
Steepest Edge	p. 147
Exercises	p. 149
Notes	p. 150
Problems in General Form	p. 151
The Primal Simplex Method	p. 151
The Dual Simplex Method	p. 153
Exercises	p. 159
Notes	p. 160
Convex Analysis	p. 161
Convex Sets	p. 161
Caratheodory's Theorem	p. 163
The Separation Theorem	p. 165
Farkas' Lemma	p. 167
Strict Complementarity	p. 168
Exercises	p. 170
Notes	p. 171
Game Theory	p. 173
Matrix Games	p. 173
Optimal Strategies	p. 175
The Minimax Theorem	p. 177
Poker	p. 181
Exercises	p. 184
Notes	p. 187
Regression	p. 189
Measures of Mediocrity	p. 189
Multidimensional Measures: Regression Analysis	p. 191
L[superscript 2]-Regression	p. 193
L[superscript 1]-Regression	p. 195
Iteratively Reweighted Least Squares	p. 196
An Example: How Fast is the Simplex Method?	p. 198
Which Variant of the Simplex Method is Best?	p. 202
Exercises	p. 203
Notes	p. 208
Financial Applications	p. 211
Portfolio Selection	p. 211
Option Pricing	p. 216
Exercises	p. 221
Notes	p. 222
Network-Type Problems	p. 223
Network Flow Problems	p. 225
Networks	p. 225
Spanning Trees and Bases	p. 228
The Primal Network Simplex Method	p. 233
The Dual Network Simplex Method	p. 237
Putting It All Together	p. 240
The Integrality Theorem	p. 243
Exercises	p. 244
Notes	p. 252
Applications	p. 253
The Transportation Problem	p. 253
The Assignment Problem	p. 255
The Shortest-Path Problem	p. 256
Upper-Bounded Network Flow Problems	p. 259
The Maximum-Flow Problem	p. 262
Exercises	p. 264
Notes	p. 269
Structural Optimization	p. 271
An Example	p. 271
Incidence Matrices	p. 273
Stability	p. 274
Conservation Laws	p. 276
Minimum-Weight Structural Design	p. 279
Anchors Away	p. 281
Exercises	p. 284
Notes	p. 284
Interior-Point Methods	p. 287
The Central Path	p. 289
Warning: Nonstandard Notation Ahead	p. 289
The Barrier Problem	p. 289
Lagrange Multipliers	p. 292
Lagrange Multipliers Applied to the Barrier Problem	p. 295
Second-Order Information	p. 297
Existence	p. 297
Exercises	p. 299
Notes	p. 301
A Path-Following Method	p. 303
Computing Step Directions	p. 303
Newton's Method	p. 305
Estimating an Appropriate Value for the Barrier Parameter	p. 306
Choosing the Step Length Parameter	p. 307
Convergence Analysis	p. 308
Exercises	p. 314
Notes	p. 318
The KKT System	p. 319
The Reduced KKT System	p. 319
The Normal Equations	p. 320
Step Direction Decomposition	p. 322
Exercises	p. 325
Notes	p. 325
Implementation Issues	p. 327
Factoring Positive Definite Matrices	p. 327
Quasidefinite Matrices	p. 331
Problems in General Form	p. 337
Exercises	p. 342
Notes	p. 342
The Affine-Scaling Method	p. 345
The Steepest Ascent Direction	p. 345
The Projected Gradient Direction	p. 347
The Projected Gradient Direction with Scaling	p. 349
Convergence	p. 353
Feasibility Direction	p. 355
Problems in Standard Form	p. 356
Exercises	p. 357
Notes	p. 358
The Homogeneous Self-Dual Method	p. 361
From Standard Form to Self-Dual Form	p. 361
Homogeneous Self-Dual Problems	p. 362
Back to Standard Form	p. 372
Simplex Method vs Interior-Point Methods	p. 375
Exercises	p. 379
Notes	p. 380
Extensions	p. 383
Integer Programming	p. 385
Scheduling Problems	p. 385
The Traveling Salesman Problem	p. 387
Fixed Costs	p. 390
Nonlinear Objective Functions	p. 390
Branch-and-Bound	p. 392
Exercises	p. 404
Notes	p. 405
Quadratic Programming	p. 407
The Markowitz Model	p. 407
The Dual	p. 412
Convexity and Complexity	p. 414
Solution Via Interior-Point Methods	p. 418
Practical Considerations	p. 419
Exercises	p. 422
Notes	p. 423
Convex Programming	p. 425
Differentiable Functions and Taylor Approximations	p. 425
Convex and Concave Functions	p. 426
Problem Formulation	p. 426
Solution Via Interior-Point Methods	p. 427
Successive Quadratic Approximations	p. 429
Merit Functions	p. 429
Parting Words	p. 433
Exercises	p. 433
Notes	p. 435
Source Listings	p. 437
The Self-Dual Simplex Method	p. 438
The Homogeneous Self-Dual Method	p. 441
Answers to Selected Exercises	p. 445
Bibliography	p. 449
Index	p. 457
Table of Contents provided by Ingram. All Rights Reserved.