Preface	13
	Preface to 2rd Edition	17
	Preface to 3rd Edition	19
	Part 1. Basic Theory---The Simplex Method and Duality	20
	Chapter 1. Introduction	22
	1. Managing a Production Facility	22
	2. The Linear Programming Problem	25
	Exercises	27
	Notes	29
	Chapter 2. The Simplex Method	31
	1. An Example	31
	2. The Simplex Method	34
	3. Initialization	37
	4. Unboundedness	40
	5. Geometry	40
	Exercises	42
	Notes	45
	Chapter 3. Degeneracy	46
	1. Definition of Degeneracy	46
	2. Two Examples of Degenerate Problems	46
	3. The Perturbation/Lexicographic Method	49
	4. Bland's Rule	53
	5. Fundamental Theorem of Linear Programming	55
	6. Geometry	56
	Exercises	59
	Notes	60
	Chapter 4. Efficiency of the Simplex Method	62
	1. Performance Measures	62
	2. Measuring the Size of a Problem	62
	3. Measuring the Effort to Solve a Problem	63
	4. Worst-Case Analysis of the Simplex Method	64
	Exercises	69
	Notes	70
	Chapter 5. Duality Theory	72
	1. Motivation---Finding Upper Bounds	72
	2. The Dual Problem	74
	3. The Weak Duality Theorem	75
	4. The Strong Duality Theorem	77
	5. Complementary Slackness	83
	6. The Dual Simplex Method	85
	7. A Dual-Based Phase I Algorithm	88
	8. The Dual of a Problem in General Form	90
	9. Resource Allocation Problems	91
	10. Lagrangian Duality	95
	Exercises	96
	Notes	104
	Chapter 6. The Simplex Method in Matrix Notation	105
	1. Matrix Notation	105
	2. The Primal Simplex Method	107
	3. An Example	112
	4. The Dual Simplex Method	117
	5. Two-Phase Methods	120
	6. Negative Transpose Property	121
	Exercises	124
	Notes	125
	Chapter 7. Sensitivity and Parametric Analyses	126
	1. Sensitivity Analysis	126
	2. Parametric Analysis and the Homotopy Method	130
	3. The Parametric Self-Dual Simplex Method	134
	Exercises	135
	Notes	139
	Chapter 8. Implementation Issues	140
	1. Solving Systems of Equations: LU-Factorization	141
	2. Exploiting Sparsity	145
	3. Reusing a Factorization	151
	4. Performance Tradeoffs	155
	5. Updating a Factorization	156
	6. Shrinking the Bump	160
	7. Partial Pricing	161
	8. Steepest Edge	162
	Exercises	164
	Notes	165
	Chapter 9. Problems in General Form	166
	1. The Primal Simplex Method	166
	2. The Dual Simplex Method	168
	Exercises	174
	Notes	175
	Chapter 10. Convex Analysis	176
	1. Convex Sets	176
	2. Carathéodory's Theorem	178
	3. The Separation Theorem	180
	4. Farkas' Lemma	182
	5. Strict Complementarity	183
	Exercises	185
	Notes	186
	Chapter 11. Game Theory	187
	1. Matrix Games	187
	2. Optimal Strategies	189
	3. The Minimax Theorem	191
	4. Poker	195
	Exercises	198
	Notes	201
	Chapter 12. Regression	202
	1. Measures of Mediocrity	202
	2. Multidimensional Measures: Regression Analysis	204
	3. L2-Regression	206
	4. L1-Regression	208
	5. Iteratively Reweighted Least Squares	209
	6. An Example: How Fast is the Simplex Method?	211
	7. Which Variant of the Simplex Method is Best?	215
	Exercises	216
	Notes	221
	Chapter 13. Financial Applications	223
	1. Portfolio Selection	223
	2. Option Pricing	228
	Exercises	233
	Notes	234
	Part 2. Network-Type Problems	235
	Chapter 14. Network Flow Problems	237
	1. Networks	237
	2. Spanning Trees and Bases	240
	3. The Primal Network Simplex Method	245
	4. The Dual Network Simplex Method	249
	5. Putting It All Together	252
	6. The Integrality Theorem	255
	Exercises	256
	Notes	264
	Chapter 15. Applications	265
	1. The Transportation Problem	265
	2. The Assignment Problem	267
	3. The Shortest-Path Problem	268
	4. Upper-Bounded Network Flow Problems	271
	5. The Maximum-Flow Problem	274
	Exercises	276
	Notes	281
	Chapter 16. Structural Optimization	282
	1. An Example	282
	2. Incidence Matrices	284
	3. Stability	285
	4. Conservation Laws	287
	5. Minimum-Weight Structural Design	290
	6. Anchors Away	292
	Exercises	295
	Notes	295
	Part 3. Interior-Point Methods	298
	Chapter 17. The Central Path	300
	Warning: Nonstandard Notation Ahead	300
	1. The Barrier Problem	300
	2. Lagrange Multipliers	303
	3. Lagrange Multipliers Applied to the Barrier Problem	306
	4. Second-Order Information	308
	5. Existence	308
	Exercises	310
	Notes	312
	Chapter 18. A Path-Following Method	313
	1. Computing Step Directions	313
	2. Newton's Method	315
	3. Estimating an Appropriate Value for the Barrier Parameter	316
	4. Choosing the Step Length Parameter	317
	5. Convergence Analysis	318
	Exercises	324
	Notes	328
	Chapter 19. The KKT System	329
	1. The Reduced KKT System	329
	2. The Normal Equations	330
	3. Step Direction Decomposition	332
	Exercises	335
	Notes	335
	Chapter 20. Implementation Issues	336
	1. Factoring Positive Definite Matrices	336
	2. Quasidefinite Matrices	340
	3. Problems in General Form	346
	Exercises	351
	Notes	351
	Chapter 21. The Affine-Scaling Method	354
	1. The Steepest Ascent Direction	354
	2. The Projected Gradient Direction	356
	3. The Projected Gradient Direction with Scaling	358
	4. Convergence	362
	5. Feasibility Direction	364
	6. Problems in Standard Form	365
	Exercises	366
	Notes	367
	Chapter 22. The Homogeneous Self-Dual Method	369
	1. From Standard Form to Self-Dual Form	369
	2. Homogeneous Self-Dual Problems	370
	3. Back to Standard Form	380
	4. Simplex Method vs Interior-Point Methods	383
	Exercises	387
	Notes	388
	Part 4. Extensions	390
	Chapter 23. Integer Programming	392
	1. Scheduling Problems	392
	2. The Traveling Salesman Problem	394
	3. Fixed Costs	397
	4. Nonlinear Objective Functions	397
	5. Branch-and-Bound	399
	Exercises	411
	Notes	412
	Chapter 24. Quadratic Programming	413
	1. The Markowitz Model	413
	2. The Dual	418
	3. Convexity and Complexity	420
	4. Solution Via Interior-Point Methods	424
	5. Practical Considerations	425
	Exercises	428
	Notes	429
	Chapter 25. Convex Programming	430
	1. Differentiable Functions and Taylor Approximations	430
	2. Convex and Concave Functions	431
	3. Problem Formulation	431
	4. Solution Via Interior-Point Methods	432
	5. Successive Quadratic Approximations	434
	6. Merit Functions	434
	7. Parting Words	438
	Exercises	438
	Notes	440
	Appendix A. Source Listings	441
	1. The Self-Dual Simplex Method	442
	2. The Homogeneous Self-Dual Method	445
	Answers to Selected Exercises	445
	Bibliography	450
	Index	451