Atnaujinkite slapukų nuostatas

Mathematics of Optimization: How to Do Things Faster [Kietas viršelis]

4.00/5 (2 ratings by Goodreads)
  • Formatas: Hardback, 327 pages, aukštis x plotis: 254x178 mm, weight: 760 g
  • Serija: Pure and Applied Undergraduate Texts
  • Išleidimo metai: 30-Jan-2018
  • Leidėjas: American Mathematical Society
  • ISBN-10: 1470441144
  • ISBN-13: 9781470441142
Kitos knygos pagal šią temą:
Mathematics of Optimization: How to Do Things FasterDidesnis paveikslėlis
  • Formatas: Hardback, 327 pages, aukštis x plotis: 254x178 mm, weight: 760 g
  • Serija: Pure and Applied Undergraduate Texts
  • Išleidimo metai: 30-Jan-2018
  • Leidėjas: American Mathematical Society
  • ISBN-10: 1470441144
  • ISBN-13: 9781470441142
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9781470441142.html
Raktažodžiai:
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.
Acknowledgements xiii
Preface xv
Course Outlines xix
Part 1 Classical Algorithms
Chapter 1 Efficient Multiplication
3(18)
1.1 Introduction
3(1)
1.2 Babylonian Multiplication
4(1)
1.3 Horner's Algorithm
5(1)
1.4 Fast Multiplication
6(2)
1.5 Strassen's Algorithm
8(1)
1.6 Eigenvalues, Eigenvectors and the Fibonacci Numbers
9(2)
1.7 Exercises
11(10)
Chapter 2 Efficient Multiplication, II
21(26)
2.1 Binomial Coefficients
21(1)
2.2 Pascal's Triangle
22(2)
2.3 Dimension
24(2)
2.4 From the Pascal to the Sierpinski Triangle
26(2)
2.5 The Euclidean Algorithm
28(7)
2.6 Exercises
35(12)
Part 2 Introduction to Linear Programming
Chapter 3 Introduction to Linear Programming
47(20)
3.1 Linear Algebra
48(2)
3.2 Finding Solutions
50(1)
3.3 Calculus Review: Local versus Global
51(3)
3.4 An Introduction to the Diet Problem
54(1)
3.5 Solving the Diet Problem
55(4)
3.6 Applications of the Diet Problem
59(1)
3.7 Exercises
60(7)
Chapter 4 The Canonical Linear Programming Problem
67(16)
4.1 Real Analysis Review
68(2)
4.2 Canonical Forms and Quadratic Equations
70(1)
4.3 Canonical Forms in Linear Programming: Statement
71(2)
4.4 Canonical Forms in Linear Programming: Conversion
73(2)
4.5 The Diet Problem: Round 2
75(1)
4.6 A Short Theoretical Aside: Strict Inequalities
76(1)
4.7 Canonical is Not Always Best
77(1)
4.8 The Oil Problem
78(1)
4.9 Exercises
79(4)
Chapter 5 Symmetries and Dualities
83(12)
5.1 Tic-Tac-Toe and a Chess Problem
83(4)
5.2 Duality and Linear Programming
87(1)
5.3 Appendix: Fun Versions of Tic-Tac-Toe
88(2)
5.4 Exercises
90(5)
Chapter 6 Basic Feasible and Basic Optimal Solutions
95(12)
6.1 Review of Linear Independence
95(1)
6.2 Basic Feasible and Basic Optimal Solutions
96(1)
6.3 Properties of Basic Feasible Solutions
97(2)
6.4 Optimal and Basic Optimal Solutions
99(1)
6.5 Efficiency and Euclid's Prime Theorem
100(2)
6.6 Exercises
102(5)
Chapter 7 The Simplex Method
107(14)
7.1 The Simplex Method: Preliminary Assumptions
107(1)
7.2 The Simplex Method: Statement
108(1)
7.3 Phase II implies Phase I
109(1)
7.4 Phase II of the Simplex Method
110(3)
7.5 Run-time of the Simplex Method
113(1)
7.6 Efficient Sorting
113(2)
7.7 Exercises
115(6)
Part 3 Advanced Linear Programming
Chapter 8 Integer Programming
121(22)
8.1 The Movie Theater Problem
122(3)
8.2 Binary Indicator Variables
125(1)
8.3 Logical Statements
126(2)
8.4 Truncation, Extrema and Absolute Values
128(2)
8.5 Linearizing Quadratic Expressions
130(1)
8.6 The Law of the Hammer and Sudoku
131(3)
8.7 Bus Route Example
134(1)
8.8 Exercises
135(8)
Chapter 9 Integer Optimization
143(10)
9.1 Maximizing a Product
143(3)
9.2 The Knapsack Problem
146(1)
9.3 Solving Integer Programs: Branch and Bound
147(3)
9.4 Exercises
150(3)
Chapter 10 Multi-Objective and Quadratic Programming
153(8)
10.1 Multi-Objective Linear Programming
153(1)
10.2 Quadratic Programming
154(1)
10.3 Example: Quadratic Objective Function
155(1)
10.4 Removing Quadratic (and Higher Order) Terms in Constraints
156(1)
10.5 Summary
157(1)
10.6 Exercises
157(4)
Chapter 11 The Traveling Salesman Problem
161(8)
11.1 Integer Linear Programming Version of the TSP
161(3)
11.2 Greedy Algorithm to the TSP
164(1)
11.3 The Insertion Algorithm
165(1)
11.4 Sub-problems Method
166(1)
11.5 Exercises
167(2)
Chapter 12 Introduction to Stochastic Linear Programming
169(10)
12.1 Deterministic and Stochastic Oil Problems
170(1)
12.2 Expected Value approach
171(1)
12.3 Recourse Approach
172(2)
12.4 Probabilistic Constraints
174(1)
12.5 Exercises
175(4)
Part 4 Fixed Point Theorems
Chapter 13 Introduction to Fixed Point Theorems
179(22)
13.1 Definitions and Uses
179(2)
13.2 Examples
181(1)
13.3 Real Analysis Preliminaries
182(2)
13.4 One-Dimensional Fixed Point Theorem
184(2)
13.5 Newton's Method versus Divide and Conquer
186(2)
13.6 Equivalent Regions and Fixed Points
188(3)
13.7 Exercises
191(10)
Chapter 14 Contraction Maps
201(20)
14.1 Definitions
201(1)
14.2 Fixed Points of Contraction Maps
202(3)
14.3 Introduction to Differential Equations
205(3)
14.4 Real Analysis Review
208(2)
14.5 First Order Differential Equations Theorem
210(3)
14.6 Examples of Picard's Iteration Method
213(2)
14.7 Exercises
215(6)
Chapter 15 Sperner's Lemma
221(18)
15.1 Statement of Sperner's Lemma
221(3)
15.2 Proof Strategies for Sperner's Lemma
224(2)
15.3 Proof of Sperner's Lemma
226(2)
15.4 Rental Harmony
228(3)
15.5 Exercises
231(8)
Chapter 16 Brouwer's Fixed Point Theorem
239(16)
16.1 Bolzano-Weierstrass Theorem
239(1)
16.2 Barycentric Coordinates
240(1)
16.3 Preliminaries for Brouwer's Fixed Point Theorem
241(3)
16.4 Proof of Brouwer's Fixed Point Theorem
244(1)
16.5 Nash Equilibrium
245(4)
16.6 Exercises
249(6)
Part 5 Advanced Topics
Chapter 17 Gale-Shapley Algorithm
255(12)
17.1 Introduction
255(2)
17.2 Three Parties
257(1)
17.3 Gale-Shapley Algorithm
258(3)
17.4 Generalization
261(1)
17.5 Applications
262(2)
17.6 Exercises
264(3)
Chapter 18 Interpolating Functions
267(16)
18.1 Lagrange Interpolation
268(2)
18.2 Interpolation Error
270(2)
18.3 Chebyshev Polynomials and Interpolation
272(2)
18.4 Splines
274(4)
18.5 Exercises
278(5)
Chapter 19 The Four Color Problem
283(20)
19.1 A Brief History
284(2)
19.2 Preliminaries
286(7)
19.3 Birkhoff and the Modern Proof
293(1)
19.4 Appel-Haken Proof
294(3)
19.5 Computational Improvements
297(4)
19.6 Exercises
301(2)
Chapter 20 The Kepler Conjecture
303(14)
20.1 Introduction
303(3)
20.2 Sphere Packing
306(2)
20.3 Challenges in Proving the Kepler Conjecture
308(2)
20.4 Local Density Inequalities
310(3)
20.5 Computer-Aided Proof
313(2)
20.6 Exercises
315(2)
Bibliography 317(6)
Index 323
Steven J. Miller, Williams College, Williamstown, MA.