Optimization Theory (eBook)

Hubertus Th. Jongen, Klaus Meer, Eberhard Triesch (Autoren)

eBook Download: PDF

2007 | 1. Auflage
454 Seiten
Springer US (Verlag)
978-1-4020-8099-9 (ISBN)

Infos

Optimization Theory is becoming a more and more important mathematical as well as interdisciplinary area, especially in the interplay between mathematics and many other sciences like computer science, physics, engineering, operations research, etc. This volume gives a comprehensive introduction into the theory of (deterministic) optimization on an advanced undergraduate and graduate level. One main feature is the treatment of both continuous and discrete optimization at the same place. This allows to study the problems under different points of view, supporting a better understanding of the entire field. The book can be adapted well as an introductory textbook into optimization theory on a basis of a two semester course; however, each of its parts can also be taught separately. Many exercises are included to increase the reader's understanding.

 

---

Optimization Theory is becoming a more and more important mathematical as well as interdisciplinary area, especially in the interplay between mathematics and many other sciences like computer science, physics, engineering, operations research, etc. This volume gives a comprehensive introduction into the theory of (deterministic) optimization on an advanced undergraduate and graduate level. One main feature is the treatment of both continuous and discrete optimization at the same place. This allows to study the problems under different points of view, supporting a better understanding of the entire field. Audience: The book can be adapted well as an introductory textbook into optimization theory on a basis of a two semester course; however, each of its parts can also be taught separately. Many exercises are included to increase the reader's understanding.

Inhalt

Contents 5
Preface 9
Part I Continuous Optimization 13
1 Optimality Criteria on Simple Regions 14
1.1 Basic Definitions, Examples, Existence of Global Minima 14
1.2 Optimality Criteria of First and Second Order 18
1.3 Diffeomorphisms, Normal Forms (Morse Lemma) 25
2 Constraints, Lagrange Function, Optimality Criteria 30
2.1 Constraints, Standard – Diffeomorphism 30
2.2 Lagrange Function, Optimality Criteria 34
2.3 Symmetric Matrices 39
3 Parametric Aspects, Semi–Infinite Optimization 46
3.1 Parametric Aspects: The Unconstrained Case 46
3.2 Parametric aspects: The Constrained Case 51
3.3 Semi–Infinite Optimization, Chebyshev Approximation,Semi–Definite Optimization 55
4 Convex Functions, Duality, Separation Theorem 60
4.1 Convex Sets, Convex Functions 60
4.2 Primal Problem, (Wolfe –) Dual Problem 66
4.3 Separation Theorem, Subdifferential 70
5 Linear Inequalities, Constraint Qualifications 78
5.1 Linear Inequalities, Farkas’ Lemma 78
5.2 Constraint Qualifications, Optimality Criteria 82
5.3 Polyhedral Sets 87
6 Linear Programming: The Simplex Method 92
6.1 Preliminaries, Vertex Theorem, Standard Problem 92
6.2 Basis/ Vertex Exchange 97
6.3 Revision: The Appearing Systems of Linear Equations 101
6.4 The Simplex Method in Tableau Form 102
6.5 Anticycling: Strategy of Bland 104
6.6 The Determination of an Initial Vertex 106
6.7 Running Time Analysis 107
7 The Ellipsoid Method 108
7.1 Introduction 108
7.2 The One-Parametric Family of Ellipsoids 110
7.3 The Khachiyan Algorithm with Integer Data 116
7.4 Proof of Theorems 7.3.1, 7.3.2 118
8 The Method of Karmarkar for Linear Programming 124
8.1 Introduction 124
8.2 Geometric Interpretation of Karmarkar’s Algorithm 126
8.3 Proof of Theorem 8.1.2 (Polynomiality) 128
8.4 Transformation of a Linear Optimization Problem into Karmarkar’s Standard Form 131
9 Order of Convergence, Steepest Descent, (Lagrange-) Newton 136
9.1 Introduction, Steepest Descent 136
9.2 Search for Zeros of Mappings, Newton’s Method 139
9.3 Additional Notes on Newton’s Method 146
9.4 Lagrange 149
10 Conjugate Direction, Variable Metric 152
10.1 Introduction 152
10.2 Conjugate Gradient-, DFP-, BFGS- Method 155
11 Penalty–, Barrier–, Multiplier–, Interior Point–Methods 164
11.1 Active Set Strategy 164
11.2 Penalty–, Barrier–, Multiplier–Methods 165
11.3 Interior Point Methods 170
12 Search Methods without Derivatives 184
12.1 Rosenbrock’s Method and Davies – Swann – Campey’s Method 184
12.2 The Simplex Method (Nelder Mead) 187
13 One Dimensional Minimization 194
Part II Discrete Optimization 202
14 Graphs and Networks 204
14.1 Basic Definitions 204
14.2 Matchings 211
14.3 The bipartite case 213
14.4 Nonbipartite matching 225
14.5 Directed Graphs 234
14.6 Exercises 235
15 Flows in Networks 238
16 Applications of the Max-Flow Min-Cut Theorem 250
16.1 The Gale-Ryser-Theorem 250
16.2 König’s Theorem 253
16.3 Dilworth’s Theorem 253
16.4 Menger’s Theorem 257
16.5 The Minimum Cost Flow Problem 259
17 Integer Linear Programming 268
17.1 Totally unimodular matrices 268
17.2 Unimodularity and integer linear programming 269
17.3 Integral polyhedra 274
18 Computability the Turing machine
18.1 Finite Alphabets 283
18.2 The Turing machine 284
18.3 Decision problems undecidability
19 Complexity theory 294
19.1 Running time the class P
19.2 Some important decision problems 297
19.3 Nondeterministic Turing machines 302
19.4 The class NP 305
20 Reducibility and NP-completeness 312
20.1 Polynomial time reductions 312
20.2 NP-completeness 314
20.3 Cook’s theorem 315
20.4 A polynomial time algorithm for 2-SAT 321
21 Some NP-completeness results 324
22 The Random Access Machine 340
23 Complexity Theory over the Real Numbers 345
23.1 Motivation 345
23.2 The Blum-Shub-Smale machine decidability
23.3 Complexity classes over the reals 353
23.4 Further directions 360
23.5 Exercises 361
24 Approximating NP-hard Problems 364
24.1 Combinatorial optimization problems the class NPO
24.2 Performance ratio and relative error 368
24.3 Concepts of approximation 370
25 Approximation Algorithms for TSP 376
25.1 A negative result 376
25.2 The metric TSP Christofides’ algorithm
26 Approximation algorithms for Bin Packing 386
26.1 Heuristics for Bin Packing 386
26.2 A non-approximability result 391
27 A FPTAS for Knapsack 394
27.1 A pseudo-polynomial algorithm for Knapsack 394
27.2 A fully polynomial time approximation scheme 398
28 Miscellaneous 402
28.1 The PCP theorem 402
28.2 Dynamic Programming 404
28.3 Branch and Bound 406
28.4 Probabilistic Analysis 409
Index 420
Index of Symbols 432
References 438
More eBooks at www.ciando.com 0

Produkt-Details

• Erscheint lt. Verlag: 8.5.2007
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• ISBN-10: 1-4020-8099-9 / 1402080999
• ISBN-13: 978-1-4020-8099-9 / 9781402080999