Mathematics of Optimization: How to do Things Faster

Cover......Page 1
Title page......Page 4
Contents......Page 8
Acknowledgements......Page 14
Preface......Page 16
Course Outlines......Page 20
Part  1 . Classical Algorithms......Page 24
1.1. Introduction......Page 26
1.2. Babylonian Multiplication......Page 27
1.3. Horner’s Algorithm......Page 28
1.4. Fast Multiplication......Page 29
1.5. Strassen’s Algorithm......Page 31
1.6. Eigenvalues, Eigenvectors and the Fibonacci Numbers......Page 32
1.7. Exercises......Page 34
2.1. Binomial Coefficients......Page 44
2.2. Pascal’s Triangle......Page 45
2.3. Dimension......Page 47
2.4. From the Pascal to the Sierpinski Triangle......Page 49
2.5. The Euclidean Algorithm......Page 51
2.6. Exercises......Page 58
Part  2 . Introduction to Linear Programming......Page 68
Chapter 3. Introduction to Linear Programming......Page 70
3.1. Linear Algebra......Page 71
3.2. Finding Solutions......Page 73
3.3. Calculus Review: Local versus Global......Page 74
3.4. An Introduction to the Diet Problem......Page 77
3.5. Solving the Diet Problem......Page 78
3.6. Applications of the Diet Problem......Page 82
3.7. Exercises......Page 83
Chapter 4. The Canonical Linear Programming Problem......Page 90
4.1. Real Analysis Review......Page 91
4.2. Canonical Forms and Quadratic Equations......Page 93
4.3. Canonical Forms in Linear Programming: Statement......Page 94
4.4. Canonical Forms in Linear Programming: Conversion......Page 96
4.5. The Diet Problem: Round 2......Page 98
4.6. A Short Theoretical Aside: Strict Inequalities......Page 99
4.7. Canonical is Not Always Best......Page 100
4.8. The Oil Problem......Page 101
4.9. Exercises......Page 102
5.1. Tic-Tac-Toe and a Chess Problem......Page 106
5.2. Duality and Linear Programming......Page 110
5.3. Appendix: Fun Versions of Tic-Tac-Toe......Page 111
5.4. Exercises......Page 113
6.1. Review of Linear Independence......Page 118
6.2. Basic Feasible and Basic Optimal Solutions......Page 119
6.3. Properties of Basic Feasible Solutions......Page 120
6.4. Optimal and Basic Optimal Solutions......Page 122
6.5. Efficiency and Euclid’s Prime Theorem......Page 123
6.6. Exercises......Page 125
7.1. The Simplex Method: Preliminary Assumptions......Page 130
7.2. The Simplex Method: Statement......Page 131
7.3. Phase II implies Phase I......Page 132
7.4. Phase II of the Simplex Method......Page 133
7.6. Efficient Sorting......Page 136
7.7. Exercises......Page 138
Part  3 . Advanced Linear Programming......Page 142
Chapter 8. Integer Programming......Page 144
8.1. The Movie Theater Problem......Page 145
8.2. Binary Indicator Variables......Page 148
8.3. Logical Statements......Page 149
8.4. Truncation, Extrema and Absolute Values......Page 151
8.5. Linearizing Quadratic Expressions......Page 153
8.6. The Law of the Hammer and Sudoku......Page 154
8.7. Bus Route Example......Page 157
8.8. Exercises......Page 158
9.1. Maximizing a Product......Page 166
9.2. The Knapsack Problem......Page 169
9.3. Solving Integer Programs: Branch and Bound......Page 170
9.4. Exercises......Page 173
10.1. Multi-Objective Linear Programming......Page 176
10.2. Quadratic Programming......Page 177
10.3. Example: Quadratic Objective Function......Page 178
10.4. Removing Quadratic (and Higher Order) Terms in Constraints......Page 179
10.6. Exercises......Page 180
11.1. Integer Linear Programming Version of the TSP......Page 184
11.2. Greedy Algorithm to the TSP......Page 187
11.3. The Insertion Algorithm......Page 188
11.4. Sub-problems Method......Page 189
11.5. Exercises......Page 190
Chapter 12. Introduction to Stochastic Linear Programming......Page 192
12.1. Deterministic and Stochastic Oil Problems......Page 193
12.2. Expected Value approach......Page 194
12.3. Recourse Approach......Page 195
12.4. Probabilistic Constraints......Page 197
12.5. Exercises......Page 198
Part  4 . Fixed Point Theorems......Page 200
13.1. Definitions and Uses......Page 202
13.2. Examples......Page 204
13.3. Real Analysis Preliminaries......Page 205
13.4. One-Dimensional Fixed Point Theorem......Page 207
13.5. Newton’s Method versus Divide and Conquer......Page 209
13.6. Equivalent Regions and Fixed Points......Page 211
13.7. Exercises......Page 214
14.1. Definitions......Page 224
14.2. Fixed Points of Contraction Maps......Page 225
14.3. Introduction to Differential Equations......Page 228
14.4. Real Analysis Review......Page 231
14.5. First Order Differential Equations Theorem......Page 233
14.6. Examples of Picard’s Iteration Method......Page 236
14.7. Exercises......Page 238
15.1. Statement of Sperner’s Lemma......Page 244
15.2. Proof Strategies for Sperner’s Lemma......Page 247
15.3. Proof of Sperner’s Lemma......Page 249
15.4. Rental Harmony......Page 251
15.5. Exercises......Page 254
16.1. Bolzano-Weierstrass Theorem......Page 262
16.2. Barycentric Coordinates......Page 263
16.3. Preliminaries for Brouwer’s Fixed Point Theorem......Page 264
16.4. Proof of Brouwer’s Fixed Point Theorem......Page 267
16.5. Nash Equilibrium......Page 268
16.6. Exercises......Page 272
Part  5 . Advanced Topics......Page 276
17.1. Introduction......Page 278
17.2. Three Parties......Page 280
17.3. Gale-Shapley Algorithm......Page 281
17.4. Generalization......Page 284
17.5. Applications......Page 285
17.6. Exercises......Page 287
Chapter 18. Interpolating Functions......Page 290
18.1. Lagrange Interpolation......Page 291
18.2. Interpolation Error......Page 293
18.3. Chebyshev Polynomials and Interpolation......Page 295
18.4. Splines......Page 297
18.5. Exercises......Page 301
Chapter 19. The Four Color Problem......Page 306
19.1. A Brief History......Page 307
19.2. Preliminaries......Page 309
19.3. Birkhoff and the Modern Proof......Page 316
19.4. Appel-Haken Proof......Page 317
19.5. Computational Improvements......Page 320
19.6. Exercises......Page 324
20.1. Introduction......Page 326
20.2. Sphere Packing......Page 329
20.3. Challenges in Proving the Kepler Conjecture......Page 331
20.4. Local Density Inequalities......Page 333
20.5. Computer-Aided Proof......Page 336
20.6. Exercises......Page 338
Bibliography......Page 340
Index......Page 346
Back Cover......Page 353