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. Undergraduate and graduate students interested in learning and teaching optimization and operation research. Miller S.J. Mathematics of Optimization: How to do Things Faster Titul Copyright Contents Acknowledgements Preface Course Outlines Part 1. Classical Algorithms Chapter 1. Effcient Multiplication, I 1.1. Introduction 1.2. Babylonian Multiplication 1.3. Horner’s Algorithm 1.4. Fast Multiplication 1.5. Strassen’s Algorithm 1.6. Eigenvalues, Eigenvectors and the Fibonacci Numbers 1.7. Exercises Chapter 2. Effcient Multiplication, II 2.1. Binomial Coeffcients 2.2. Pascal’s Triangle 2.3. Dimension 2.4. From the Pascal to the Sierpinski Triangle 2.5. The Euclidean Algorithm 2.6. Exercises Part 2. Introduction to Linear Programming Chapter 3. Introduction to Linear Programming 3.1. Linear Algebra 3.2. Finding Solutions 3.3. Calculus Review: Local versus Global 3.4. An Introduction to the Diet Problem 3.5. Solving the Diet Problem 3.6. Applications of the Diet Problem 3.7. Exercises Chapter 4. The Canonical Linear Programming Problem 4.1. Real Analysis Review 4.2. Canonical Forms and Quadratic Equations 4.3. Canonical Forms in Linear Programming: Statement 4.4. Canonical Forms in Linear Programming: Conversion 4.5. The Diet Problem: Round 2 4.6. A Short Theoretical Aside: Strict Inequalities 4.7. Canonical is Not Always Best 4.8. The Oil Problem 4.9. Exercises Chapter 5. Symmetries and Dualities 5.1. Tic-Tac-Toe and a Chess Problem 5.2. Duality and Linear Programming 5.3. Appendix: Fun Versions of Tic-Tac-Toe 5.4. Exercises Chapter 6. Basic Feasible and Basic Optimal Solutions 6.1. Review of Linear Independence 6.2. Basic Feasible and Basic Optimal Solutions 6.3. Properties of Basic Feasible Solutions 6.4. Optimal and Basic Optimal Solutions 6.5. Effciency and Euclid’s Prime Theorem 6.6. Exercises Chapter 7. The Simplex Method 7.1. The Simplex Method: Preliminary Assumptions 7.2. The Simplex Method: Statement 7.3. Phase II implies Phase I 7.4. Phase II of the Simplex Method 7.5. Run-time of the Simplex Method 7.6. Effcient Sorting 7.7. Exercises Part 3. Advanced Linear Programming Chapter 8. Integer Programming 8.1. The Movie Theater Problem 8.2. Binary Indicator Variables 8.3. Logical Statements 8.4. Truncation, Extrema and Absolute Values 8.5. Linearizing Quadratic Expressions 8.6. The Law of the Hammer and Sudoku 8.7. Bus Route Example 8.8. Exercises Chapter 9. Integer Optimization 9.1. Maximizing a Product 9.2. The Knapsack Problem 9.3. Solving Integer Programs: Branch and Bound 9.4. Exercises Chapter 10. Multi-Objective and Quadratic Programming 10.1. Multi-Objective Linear Programming 10.2. Quadratic Programming 10.3. Example: Quadratic Objective Function 10.4. Removing Quadratic (and Higher Order) Terms in Constraints 10.5. Summary 10.6. Exercises Chapter 11. The Traveling Salesman Problem 11.1. Integer Linear Programming Version of the TSP 11.2. Greedy Algorithm to the TSP 11.3. The Insertion Algorithm 11.4. Sub-problems Method 11.5. Exercises Chapter 12. Introduction to Stochastic Linear Programming 12.1. Deterministic and Stochastic Oil Problems 12.2. Expected Value approach 12.3. Recourse Approach 12.4. Probabilistic Constraints 12.5. Exercises Part 4. Fixed Point Theorems Chapter 13. Introduction to Fixed Point Theorems 13.1. Definitions and Uses 13.2. Examples 13.3. Real Analysis Preliminaries 13.4. One-Dimensional Fixed Point Theorem 13.5. Newton’s Method versus Divide and Conquer 13.6. Equivalent Regions and Fixed Points 13.7. Exercises Chapter 14. Contraction Maps 14.1. Definitions 14.2. Fixed Points of Contraction Maps 14.3. Introduction to Differential Equations 14.4. Real Analysis Review 14.5. First Order Differential Equations Theorem 14.6. Examples of Picard’s Iteration Method 14.7. Exercises Chapter 15. Sperner’s Lemma 15.1. Statement of Sperner’s Lemma 15.2. Proof Strategies for Sperner’s Lemma 15.3. Proof of Sperner’s Lemma 15.4. Rental Harmony 15.5. Exercises Chapter 16. Brouwer’s Fixed Point Theorem 16.1. Bolzano-Weierstrass Theorem 16.2. Barycentric Coordinates 16.3. Preliminaries for Brouwer’s Fixed Point Theorem 16.4. Proof of Brouwer’s Fixed Point Theorem 16.5. Nash Equilibrium 16.6. Exercises Part 5. Advanced Topics Chapter 17. Gale-Shapley Algorithm 17.1. Introduction 17.2. Three Parties 17.3. Gale-Shapley Algorithm 17.4. Generalization 17.5. Applications 17.6. Exercises Chapter 18. Interpolating Functions 18.1. Lagrange Interpolation 18.2. Interpolation Error 18.3. Chebyshev Polynomials and Interpolation 18.4. Splines 18.5. Exercises Chapter 19. The Four Color Problem 19.1. A Brief History 19.2. Preliminaries 19.3. Birkhoff and the Modern Proof 19.4. Appel-Haken Proof 19.5. Computational Improvements 19.6. Exercises Chapter 20. The Kepler Conjecture 20.1. Introduction 20.2. Sphere Packing 20.3. Challenges in Proving the Kepler Conjecture 20.4. Local Density Inequalities 20.5. Computer-Aided Proof 20.6. Exercises Bibliography Index 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