Mathematics of Optimization: How to Do Things Faster (Pure and Applied Undergraduate Texts) (Pure and Applied Undergraduate Texts, 30)

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