Jongen / Meer / Triesch Optimization Theory

1. Auflage 2007
ISBN: 978-1-4020-8099-9
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 454 Seiten

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.

Autoren/Hrsg.

Jongen, Hubertus Th.

Meer, Klaus

Triesch, Eberhard

Inhaltsverzeichnis

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