About the BookAbout the AuthorTable of Contents

Optimization Theory is an active area of research with numerous applications; many of the books are designed for engineering classes, and thus have an emphasis on problems from such fields. Covering much of the same material, there is less emphasis on coding and detailed applications as the intended audience is more mathematical. There are still several important problems discussed (especially scheduling problems), but there is more emphasis on theory and less on the nuts and bolts of coding. A constant theme of the text is the “why” and the “how” in the subject. Why are we able to do a calculation efficiently? How should we look at a problem? Extensive effort is made to motivate the mathematics and isolate how one can apply ideas/perspectives to a variety of problems. As many of the key algorithms in the subject require too much time or detail to analyze in a first course (such as the run-time of the Simplex Algorithm), there are numerous comparisons to simpler algorithms which students have either seen or can quickly learn (such as the Euclidean algorithm) to motivate the type of results on run-time savings.

Steven J. Miller, Williams College, Williamstown, MA

•Acknowledgements 14
• Preface 16
• Course Outlines 20

• Part 1. Classical Algorithms 24
Chapter 1. Efficient Multiplication, I 26
1.1. Introduction 26
1.2. Babylonian Multiplication 27
1.3. Horner's Algorithm 28
1.4. Fast Multiplication 29
1.5. Strassen's Algorithm 31
1.6. Eigenvalues, Eigenvectors and the Fibonacci Numbers 32
1.7. Exercises 34

Chapter 2. Efficient Multiplication, II 44
2.1. Binomial Coefficients 44
2.2. Pascal's Triangle 45
2.3. Dimension 47
2.4. From the Pascal to the Sierpinski Triangle 49
2.5. The Euclidean Algorithm 51
2.6. Exercises 58

• Part 2. Introduction to Linear Programming 68
Chapter 3. Introduction to Linear Programming 70
3.1. Linear Algebra 71
3.2. Finding Solutions 73
3.3. Calculus Review: Local versus Global 74
3.4. An Introduction to the Diet Problem 77
3.5. Solving the Diet Problem 78
3.6. Applications of the Diet Problem 82
3.7. Exercises 83

Chapter 4. The Canonical Linear Programming Problem 90
4.1. Real Analysis Review 91
4.2. Canonical Forms and Quadratic Equations 93
4.3. Canonical Forms in Linear Programming: Statement 94
4.4. Canonical Forms in Linear Programming: Conversion 96
4.5. The Diet Problem: Round 2 98
4.6. A Short Theoretical Aside: Strict Inequalities 99
4.7. Canonical is Not Always Best 100
4.8. The Oil Problem 101
4.9. Exercises 102

Chapter 5. Symmetries and Dualities 106
5.1. Tic-Tac-Toe and a Chess Problem 106
5.2. Duality and Linear Programming 110
5.3. Appendix: Fun Versions of Tic-Tac-Toe 111
5.4. Exercises 113

Chapter 6. Basic Feasible and Basic Optimal Solutions 118
6.1. Review of Linear Independence 118
6.2. Basic Feasible and Basic Optimal Solutions 119
6.3. Properties of Basic Feasible Solutions 120
6.4. Optimal and Basic Optimal Solutions 122
6.5. Efficiency and Euclid's Prime Theorem 123
6.6. Exercises 125

Chapter 7. The Simplex Method 130
7.1. The Simplex Method: Preliminary Assumptions 130
7.2. The Simplex Method: Statement 131
7.3. Phase II implies Phase I 132
7.4. Phase II of the Simplex Method 133
7.5. Run-time of the Simplex Method 136
7.6. Efficient Sorting 136
7.7. Exercises 138
• Part 3. Advanced Linear Programming 142

Chapter 8. Integer Programming 144
8.1. The Movie Theater Problem 145
8.2. Binary Indicator Variables 148
8.3. Logical Statements 149
8.4. Truncation, Extrema and Absolute Values 151
8.5. Linearizing Quadratic Expressions 153
8.6. The Law of the Hammer and Sudoku 154
8.7. Bus Route Example 157
8.8. Exercises 158

Chapter 9. Integer Optimization 166
9.1. Maximizing a Product 166
9.2. The Knapsack Problem 169
9.3. Solving Integer Programs: Branch and Bound 170
9.4. Exercises 173

Chapter 10. Multi-Objective and Quadratic Programming 176
10.1. Multi-Objective Linear Programming 176
10.2. Quadratic Programming 177
10.3. Example: Quadratic Objective Function 178
10.4. Removing Quadratic (and Higher Order) Terms in Constraints 179
10.5. Summary 180
10.6. Exercises 180

Chapter 11. The Traveling Salesman Problem 184
11.1. Integer Linear Programming Version of the TSP 184
11.2. Greedy Algorithm to the TSP 187
11.3. The Insertion Algorithm 188
11.4. Sub-problems Method 189
11.5. Exercises 190

Chapter 12. Introduction to Stochastic Linear Programming 192
12.1. Deterministic and Stochastic Oil Problems 193
12.2. Expected Value approach 194
12.3. Recourse Approach 195
12.4. Probabilistic Constraints 197
12.5. Exercises 198
• Part 4 . Fixed Point Theorems 200

Chapter 13. Introduction to Fixed Point Theorems 202
13.1. Definitions and Uses 202
13.2. Examples 204
13.3. Real Analysis Preliminaries 205
13.4. One-Dimensional Fixed Point Theorem 207
13.5. Newton's Method versus Divide and Conquer 209
13.6. Equivalent Regions and Fixed Points 211
13.7. Exercises 214

Chapter 14. Contraction Maps 224
14.1. Definitions 224
14.2. Fixed Points of Contraction Maps 225
14.3. Introduction to Differential Equations 228
14.4. Real Analysis Review 231
14.5. First Order Differential Equations Theorem 233
14.6. Examples of Picard's Iteration Method 236
14.7. Exercises 238

Chapter 15. Sperner's Lemma 244
15.1. Statement of Sperner's Lemma 244
15.2. Proof Strategies for Sperner's Lemma 247
15.3. Proof of Sperner's Lemma 249
15.4. Rental Harmony 251
15.5. Exercises 254

Chapter 16. Brouwer's Fixed Point Theorem 262
16.1. Bolzano-Weierstrass Theorem 262
16.2. Barycentric Coordinates 263
16.3. Preliminaries for Brouwer's Fixed Point Theorem 264
16.4. Proof of Brouwer's Fixed Point Theorem 267
16.5. Nash Equilibrium 268
16.6. Exercises 272
• Part 5. Advanced Topics 276

Chapter 17. Gale-Shapley Algorithm 278
17.1. Introduction 278
17.2. Three Parties 280
17.3. Gale-Shapley Algorithm 281
17.4. Generalization 284
17.5. Applications 285
17.6. Exercises 287

Chapter 18. Interpolating Functions 290
18.1. Lagrange Interpolation 291
18.2. Interpolation Error 293
18.3. Chebyshev Polynomials and Interpolation 295
18.4. Splines 297
18.5. Exercises 301

Chapter 19. The Four Color Problem 306
19.1. A Brief History 307
19.2. Preliminaries 309
19.3. Birkhoff and the Modern Proof 316
19.4. Appel-Haken Proof 317
19.5. Computational Improvements 320
19.6. Exercises 324

Chapter 20. The Kepler Conjecture 326
20.1. Introduction 326
20.2. Sphere Packing 329
20.3. Challenges in Proving the Kepler Conjecture 331
20.4. Local Density Inequalities 333
20.5. Computer-Aided Proof 336
20.6. Exercises 338

Bibliography 340
Index 346