Mathematics of Optimization: How to do Things Faster

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