|
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 |
|