Preface ..................................................... xiii
Preface to 2nd Edition ...................................... xvii
Preface to 3rd Edition ....................................... xix
Part 1. Basic Theory—The Simplex Method and Duality ............ 1
Chapter 1. Introduction ........................................ 3
1. Managing a Production Facility ............................. 3
2. The Linear Programming Problem ............................. 6
Exercises .................................................. 8
Notes ..................................................... 10
Chapter 2. The Simplex Method ................................. 13
1. An Example ................................................ 13
2. The Simplex Method ........................................ 16
3. Initialization ............................................ 19
4. Unboundedness ............................................. 22
5. Geometry .................................................. 22
Exercises .................................................... 24
Notes ........................................................ 27
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
Exercises ................................................. 42
Notes ..................................................... 43
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 Exercises ....... 47
Exercises ..................................................... 52
Notes ........................................................ 53
Chapter 5. Duality Theory
1. Motivation—Finding Upper Bounds ........................... 55
2 The Dual Problem .......................................... 55
3. The Weak Duality Theorem .................................. 57
4. The Strong Duality Theorem ................................ 58
5. Complementary Slackness ................................... 60
6. The Dual Simplex Method ................................... 66
7. Dual-Based Phase I Algorithm .............................. 68
8. The Dual of a Problem in General For ...................... 71
9. Resource Allocation Problems .............................. 73
10.Lagrangian Duality ........................................ 74
Exercises .................................................... 78
Exercises .................................................... 79
Notes ........................................................ 87
Chapter 6. The Simplex Method in Matrix Notation
1. Matrix Notation ........................................... 89
2. The Primal Simplex Method ................................. 89
3. An Example ................................................ 91
4. The Dual Simplex Method ................................... 96
5. Two-Phase Methods ........................................ 101
6. Negative Transpose Property .............................. 104
Exercises ................................................... 108
Notes ....................................................... 109
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 Exercises ........ 119
Notes ....................................................... 120
Chapter 8. Implementation Issues ............................. 124
1. Solving Systems of Equations: LI-Factorization ........... 125
2. Exploiting Sparsity ...................................... 126
3. Reusing a Factorization .................................. 130
4. Performance Tradeoffs .................................... 136
5. Updating a Factorization ................................. 141
6. Shrinking the Bump ....................................... 145
7. Partial Pricing .......................................... 146
S. Steepest Edge ............................................ 147
Exercises ................................................... 149
Notes ....................................................... 150
Chapter 9. Problems in General Form .......................... 151
1. The Primal Simplex Method ................................ 151
2. The Dual Simplex Method .................................. 153
Exercises ................................................... 159
Notes ....................................................... 160
Chapter 10. Convex Analysis .................................. 161
1. Com ex Sets .............................................. 161
2. Caratheodory's Theorem ................................... 163
3. The Separation Theorem ................................... 165
4. Farkas' Lemma ............................................ 167
5. Strict Complementarity ................................... 168
Exercises ................................................... 170
Notes ....................................................... 171
Chapter 11. Game Theory ...................................... 173
1. Matrix Games ............................................. 173
2. Optimal Strategies ....................................... 175
3. The Minimax Theorem ...................................... 177
4. Poker .................................................... 181
Exercises ................................................... 184
Notes ....................................................... 187
Chapter 12. Regression ....................................... 189
1. Measures of Mediocrity ................................... 189
2. Multidimensional Measures: Regression Analysis ........... 191
3. L-'-Regression ........................................... 193
4. I'-Regression ............................................ 195
5. Iteratively Reweighted Least Squares ..................... 196
6. An Example: How Fast is the Simplex Method? .............. 198
7. Whieh Variant of the Simplex Method is Best? ............. 202
Exercises ................................................... 203
Notes ....................................................... 208
Chapter 13. Financial Applications ........................... 211
1. Portfolio Selection ...................................... 211
2. Option Pricing ........................................... 216
Exercises ................................................... 221
Notes ....................................................... 222
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
5. Putting It All Together .................................. 240
6. The Integrality Theorem .................................. 243
Exercises ................................................... 244
Notes ....................................................... 252
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
Exercises ................................................... 264
Notes ....................................................... 269
Chapter 16. Structural Optimization .......................... 271
1. An Example ............................................... 271
2. Incidence Matrices ....................................... 273
3. Stability ................................................ 274
4. Conservation Laws ........................................ 276
5. Minimum-Weight Structural Design ......................... 279
6. Anchors Away ............................................. 281
Exercises ................................................... 284
Notes ....................................................... 284
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
Exercises ................................................... 299
Notes ....................................................... 301
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
Exercises ................................................... 314
Notes ....................................................... 318
Chapter 19. The KKT System ................................... 319
1. The Reduced KKT System ................................... 319
2. The Normal Equations ..................................... 320
3. Step Direction Decomposition ............................. 322
Exercises ................................................... 325
Notes ....................................................... 325
Chapter 20. Implementation Issues ............................ 327
1. Factoring Positive Definite Matrices ..................... 327
2. Quasidefinite Matrices ................................... 331
3. Problems in General Form ................................. 337
Exercises ................................................... 342
Notes ....................................................... 342
Chapter 21. The Aftine-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
Exercises ................................................... 357
Notes ....................................................... 358
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
Exercises ................................................... 379
Notes ....................................................... 380
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
Exercises ................................................... 404
Notes ....................................................... 405
Chapter 24. Quadratic Programming ............................ 407
The Markowitz Model ...................................... 407
The Dual ................................................. 412
Convexity and Complexity ................................. 414
4. Solution Via Interior-Point Methods ...................... 418
Practical Considerations .................................... 419
Exercises ................................................... 422
Notes ....................................................... 423
Chapter 25. Convex Programming ............................... 425
Differentiable Functions and Taylor Approximations ....... 425
Convex and Concave Functions ............................. 426
Problem Formulation ...................................... 426
4. Solution Via Interior-Point Methods ...................... 427
Successive Quadratic Approximations ......................... 429
6. Merit Functions .......................................... 429
7. Parting Words ............................................ 433
Exercises ................................................... 433
Notes ....................................................... 435
Appendix A. Source Listings ................................. 437
1. The Self-Dual Simplex Method ............................. 438
2. The Homogeneous Self-Dual Method ......................... 441
Answers to Selected Exercises ............................... 445
Bibliography ................................................ 449
Index ....................................................... 457
| 
