 Linear Programming: Foundations and Extensions (Vanderbei Robert J.)

# Linear Programming: Foundations and Extensions

 Автор(ы): Vanderbei Robert J. 06.10.2007 Год изд.: 2001 Описание: This book is about constrained optimization. It begins with a thorough 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. The book aims to be a first introduction to the subject. Specific examples and concrete algorithms precede more abstract topics. Nevertheless, topics covered are developed in some depth, a large number of numerical examples are worked out in detail, and many recent topics 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. Оглавление: Обложка книги. Part 1. Basic Theory—The Simplex Method and Duality  Chapter 1. Introduction    1. Managing a Production Facility    2. The Linear Programming Problem      Exercises      Notes  Chapter 2. The Simplex Method    1. An Example    2. The Simplex Method    3. Initialization    4. Unboundedness    5. Geometry      Exercises      Notes  Chapter 3. Degeneracy    1. Definition of Degeneracy    2. Two Examples of Degenerate Problems    3. The Perturbation/Lexicographic Method    4. Eland's Rule    5. Fundamental Theorem of Linear Programming    6. Geometry      Exercises      Notes  Chapter 4. Efficiency of the Simplex Method    1. Performance Measures    2. Measuring the Size of a Problem    3. Measuring the Effort to Solve a Problem    4. Worst-Case Analysis of the Simplex Method      Exercises      Notes  Chapter 5. Duality Theory    1. Motivation—Finding Upper Bounds    2. The Dual Problem    3. The Weak Duality Theorem    4. The Strong Duality Theorem    5. Complementary Slackness    6. The Dual Simplex Method    7. A Dual-Based Phase I Algorithm    8. The Dual of a Problem in General Form    9. Resource Allocation Problems    10. Lagrangian Duality      Exercises      Notes  Chapter 6. The Simplex Method in Matrix Notation    1. Matrix Notation    2. The Primal Simplex Method    3. An Example    4. The Dual Simplex Method    5. Two-Phase Methods    6. Negative Transpose Property      Exercises      Notes  Chapter 7. Sensitivity and Parametric Analyses    1. Sensitivity Analysis    2. Parametric Analysis and the Homotopy Method    3. The Parametric Self-Dual Simplex Method      Exercises      Notes  Chapter 8. Implementation Issues    1. Solving Systems of Equations: LU-Factorization    2. Exploiting Sparsity    3. Reusing a Factorization    4. Performance Tradeoffs    5. Updating a Factorization    6. Shrinking the Bump    7. Partial Pricing    8. Steepest Edge      Exercises      Notes  Chapter 9. Problems in General Form    1. The Primal Simplex Method    2. The Dual Simplex Method      Exercises      Notes  Chapter 10. Convex Analysis    1. Convex Sets    2. Caratheodory's Theorem    3. The Separation Theorem    4. Parkas' Lemma    5. Strict Complementarity      Exercises      Notes  Chapter 11. Game Theory    1. Matrix Games    2. Optimal Strategies    3. The Minimax Theorem    4. Poker      Exercises      Notes  Chapter 12. Regression    1. Measures of Mediocrity    2. Multidimensional Measures: Regression Analysis    3. L(?)-Regression    4. L(?) -Regression    5. Iteratively Reweighted Least Squares    6. An Example: How Fast is the Simplex Method?    7. Which Variant of the Simplex Method is Best?      Exercises      Notes  Part 2. Network-Type Problems  Chapter 13. Network Flow Problems    1. Networks    2. Spanning Trees and Bases    3. The Primal Network Simplex Method    4. The Dual Network Simplex Method    5. Putting It All Together    6. The Integrality Theorem      Exercises      Notes  Chapter 14. Applications    1. The Transportation Problem    2. The Assignment Problem    3. The Shortest-Path Problem    4. Upper-Bounded Network Flow Problems    5. The Maximum-Flow Problem      Exercises      Notes  Chapter 15. Structural Optimization    1. An Example    2. Incidence Matrices    3. Stability    4. Conservation Laws    5. Minimum-Weight Structural Design    6. Anchors Away      Exercises      Notes  Part3. Interior-Point Methods  Chapter 16. The Central Path      Warning: Nonstandard Notation Ahead    1. The Barrier Problem    2. Lagrange Multipliers    3. Lagrange Multipliers Applied to the Barrier Problem    4. Second-Order Information    5. Existence      Exercises      Notes  Chapter 17. A Path-Following Method    1. Computing Step Directions    2. Newton's Method    3. Estimating an Appropriate Value for the Barrier Parameter    4. Choosing the Step Length Parameter    5. Convergence Analysis      Exercises      Notes  Chapter 18. The KKT System    1. The Reduced KKT System    2. The Normal Equations    3. Step Direction Decomposition      Exercises      Notes  Chapter 19. Implementation Issues    1. Factoring Positive Definite Matrices    2. Quasidefinite Matrices    3. Problems in General Form      Exercises      Notes  Chapter 20. The Affine-Scaling Method    1. The Steepest Ascent Direction    2. The Projected Gradient Direction    3. The Projected Gradient Direction with Scaling    4. Convergence    5. Feasibility Direction    6. Problems in Standard Form      Exercises      Notes  Chapter 21. The Homogeneous Self-Dual Method    1. From Standard Form to Self-Dual Form    2. Homogeneous Self-Dual Problems    3. Back to Standard Form    4. Simplex Method vs Interior-Point Methods      Exercises      Notes  Part 4. Extensions  Chapter 22. Integer Programming    1. Scheduling Problems    2. The Traveling Salesman Problem    3. Fixed Costs    4. Nonlinear Objective Functions    5. Branch-and-Bound      Exercises      Notes  Chapter 23. Quadratic Programming    1. The Markowitz Model    2. The Dual    3. Convexity and Complexity    4. Solution Via Interior-Point Methods    5. Practical Considerations      Exercises      Notes  Chapter 24. Convex Programming    1. Differentiable Functions and Taylor Approximations    2. Convex and Concave Functions    3. Problem Formulation    4. Solution Via Interior-Point Methods    5. Successive Quadratic Approximations    6. Merit Functions    7. Parting Words      Exercises      Notes  Appendix A. Source Listings    1. The Self-Dual Simplex Method    2. The Homogeneous Self-Dual Method  Answers to Selected Exercises  Bibliography  Index  Формат: djvu Размер: 2284007 байт Язык: ENG Рейтинг: 254 Открыть: Ссылка (RU)