+612 9045 4394
 
CHECKOUT
Linear Programming : Foundations and Extensions - Robert J. Vanderbei

Linear Programming

Foundations and Extensions

Paperback

Published: 31st March 1998
Ships: 5 to 9 business days
5 to 9 business days
$259.50
or 4 easy payments of $64.88 with Learn more

Other Available Formats (Hide)

  • Hardcover View Product Published: 31st December 1996
    $535.25

This book focuses largely on constrained optimization. It begins with a substantial treatment of linear programming and proceeds to convex analysis, network flows, integer programming, quadratic programming, and convex optimization. Along the way, dynamic programming and the linear complementarity problem are touched on as well.
This book aims to be the first introduction to the topic. Specific examples and concrete algorithms precede more abstract topics. Nevertheless, topics covered are developed in some depth, a large number of numerical examples worked out in detail, and many recent results are included, most notably interior-point methods. The exercises at the end of each chapter both illustrate the theory, and, in some cases, extend it.
Optimization is not merely an intellectual exercise: its purpose is to solve practical problems on a computer. Accordingly, the book comes with software that implements the major algorithms studied. At this point, software for the following four algorithms is available:

  • The two-phase simplex method
  • The primal-dual simplex method
  • The path-following interior-point method
  • The homogeneous self-dual methods.¬£/LIST¬£.

  • `Vanderbei's book is thoroughly modern. Vanderbei's book has many novel features. Some nice features. This book has style. Overall, I greatly enjoyed reviewing this book, and I highly recommend it as a textbook for an advanced undergraduate or master's level course in linear programming, particularly for courses in an engineering environment. In addition, it also is a good reference book for interior point methods as well as for implementation and computational aspects of linear programming. This is an excellent new book.'
    Robert Freund, (MIT) in Optima, 56 (1997)
    `In conclusion, Vanderbei's book gives an excellent introduction to linear programminbg, especially the algorithmic side of the subject. The book is highly recommended for both self study and as teaching material.'
    Optima, 58 (1998)

    Prefacep. xiii
    Preface to 2nd Editionp. xvii
    Basic Theory--The Simplex Method and Dualityp. 1
    Introductionp. 3
    Managing a Production Facilityp. 3
    The Linear Programming Problemp. 6
    Exercisesp. 8
    Notesp. 10
    The Simplex Methodp. 13
    An Examplep. 13
    The Simplex Methodp. 16
    Initializationp. 19
    Unboundednessp. 22
    Geometryp. 22
    Exercisesp. 24
    Notesp. 27
    Degeneracyp. 29
    Definition of Degeneracyp. 29
    Two Examples of Degenerate Problemsp. 29
    The Perturbation/Lexicographic Methodp. 32
    Bland's Rulep. 36
    Fundamental Theorem of Linear Programmingp. 38
    Geometryp. 39
    Exercisesp. 42
    Notesp. 43
    Efficiency of the Simplex Methodp. 45
    Performance Measuresp. 45
    Measuring the Size of a Problemp. 45
    Measuring the Effort to Solve a Problemp. 46
    Worst-Case Analysis of the Simplex Methodp. 47
    Exercisesp. 52
    Notesp. 53
    Duality Theoryp. 55
    Motivation--Finding Upper Boundsp. 55
    The Dual Problemp. 57
    The Weak Duality Theoremp. 58
    The Strong Duality Theoremp. 60
    Complementary Slacknessp. 66
    The Dual Simplex Methodp. 68
    A Dual-Based Phase I Algorithmp. 71
    The Dual of a Problem in General Formp. 73
    Resource Allocation Problemsp. 74
    Lagrangian Dualityp. 78
    Exercisesp. 79
    Notesp. 87
    The Simplex Method in Matrix Notationp. 89
    Matrix Notationp. 89
    The Primal Simplex Methodp. 91
    An Examplep. 96
    The Dual Simplex Methodp. 101
    Two-Phase Methodsp. 104
    Negative Transpose Propertyp. 105
    Exercisesp. 108
    Notesp. 109
    Sensitivity and Parametric Analysesp. 111
    Sensitivity Analysisp. 111
    Parametric Analysis and the Homotopy Methodp. 115
    The Parametric Self-Dual Simplex Methodp. 119
    Exercisesp. 120
    Notesp. 124
    Implementation Issuesp. 125
    Solving Systems of Equations: LU-Factorizationp. 126
    Exploiting Sparsityp. 130
    Reusing a Factorizationp. 136
    Performance Tradeoffsp. 140
    Updating a Factorizationp. 141
    Shrinking the Bumpp. 145
    Partial Pricingp. 146
    Steepest Edgep. 147
    Exercisesp. 149
    Notesp. 150
    Problems in General Formp. 151
    The Primal Simplex Methodp. 151
    The Dual Simplex Methodp. 153
    Exercisesp. 159
    Notesp. 160
    Convex Analysisp. 161
    Convex Setsp. 161
    Caratheodory's Theoremp. 163
    The Separation Theoremp. 165
    Farkas' Lemmap. 167
    Strict Complementarityp. 168
    Exercisesp. 170
    Notesp. 171
    Game Theoryp. 173
    Matrix Gamesp. 173
    Optimal Strategiesp. 175
    The Minimax Theoremp. 177
    Pokerp. 181
    Exercisesp. 184
    Notesp. 187
    Regressionp. 189
    Measures of Mediocrityp. 189
    Multidimensional Measures: Regression Analysisp. 191
    L[superscript 2]-Regressionp. 193
    L[superscript 1]-Regressionp. 195
    Iteratively Reweighted Least Squaresp. 196
    An Example: How Fast is the Simplex Method?p. 198
    Which Variant of the Simplex Method is Best?p. 202
    Exercisesp. 203
    Notesp. 208
    Network-Type Problemsp. 211
    Network Flow Problemsp. 213
    Networksp. 213
    Spanning Trees and Basesp. 216
    The Primal Network Simplex Methodp. 221
    The Dual Network Simplex Methodp. 225
    Putting It All Togetherp. 228
    The Integrality Theoremp. 231
    Exercisesp. 232
    Notesp. 240
    Applicationsp. 241
    The Transportation Problemp. 241
    The Assignment Problemp. 243
    The Shortest-Path Problemp. 244
    Upper-Bounded Network Flow Problemsp. 247
    The Maximum-Flow Problemp. 250
    Exercisesp. 252
    Notesp. 257
    Structural Optimizationp. 259
    An Examplep. 259
    Incidence Matricesp. 261
    Stabilityp. 262
    Conservation Lawsp. 264
    Minimum-Weight Structural Designp. 267
    Anchors Awayp. 269
    Exercisesp. 272
    Notesp. 272
    Interior-Point Methodsp. 275
    The Central Pathp. 277
    Warning: Nonstandard Notation Aheadp. 277
    The Barrier Problemp. 277
    Lagrange Multipliersp. 280
    Lagrange Multipliers Applied to the Barrier Problemp. 283
    Second-Order Informationp. 285
    Existencep. 285
    Exercisesp. 287
    Notesp. 289
    A Path-Following Methodp. 291
    Computing Step Directionsp. 291
    Newton's Methodp. 293
    Estimating an Appropriate Value for the Barrier Parameterp. 294
    Choosing the Step Length Parameterp. 295
    Convergence Analysisp. 296
    Exercisesp. 302
    Notesp. 306
    The KKT Systemp. 307
    The Reduced KKT Systemp. 307
    The Normal Equationsp. 308
    Step Direction Decompositionp. 310
    Exercisesp. 313
    Notesp. 313
    Implementation Issuesp. 315
    Factoring Positive Definite Matricesp. 315
    Quasidefinite Matricesp. 319
    Problems in General Formp. 325
    Exercisesp. 331
    Notesp. 331
    The Affine-Scaling Methodp. 333
    The Steepest Ascent Directionp. 333
    The Projected Gradient Directionp. 335
    The Projected Gradient Direction with Scalingp. 337
    Convergencep. 341
    Feasibility Directionp. 343
    Problems in Standard Formp. 344
    Exercisesp. 345
    Notesp. 346
    The Homogeneous Self-Dual Methodp. 349
    From Standard Form to Self-Dual Formp. 349
    Homogeneous Self-Dual Problemsp. 350
    Back to Standard Formp. 360
    Simplex Method vs Interior-Point Methodsp. 363
    Exercisesp. 367
    Notesp. 368
    Extensionsp. 371
    Integer Programmingp. 373
    Scheduling Problemsp. 373
    The Traveling Salesman Problemp. 375
    Fixed Costsp. 378
    Nonlinear Objective Functionsp. 378
    Branch-and-Boundp. 380
    Exercisesp. 392
    Notesp. 393
    Quadratic Programmingp. 395
    The Markowitz Modelp. 395
    The Dualp. 399
    Convexity and Complexityp. 402
    Solution Via Interior-Point Methodsp. 404
    Practical Considerationsp. 406
    Exercisesp. 409
    Notesp. 411
    Convex Programmingp. 413
    Differentiable Functions and Taylor Approximationsp. 413
    Convex and Concave Functionsp. 414
    Problem Formulationp. 414
    Solution Via Interior-Point Methodsp. 415
    Successive Quadratic Approximationsp. 417
    Merit Functionsp. 417
    Parting Wordsp. 421
    Exercisesp. 421
    Notesp. 423
    Source Listingsp. 425
    The Self-Dual Simplex Methodp. 426
    The Homogeneous Self-Dual Methodp. 429
    Answers to Selected Exercisesp. 433
    Bibliographyp. 435
    Indexp. 443
    Table of Contents provided by Syndetics. All Rights Reserved.

    ISBN: 9780792381419
    ISBN-10: 0792381416
    Series: International Series in Operations Research & Management Science
    Audience: General
    Format: Paperback
    Language: English
    Number Of Pages: 418
    Published: 31st March 1998
    Publisher: Springer
    Country of Publication: NL
    Dimensions (cm): 23.32 x 16.2  x 2.39
    Weight (kg): 0.72
    Edition Type: New edition