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	282
	18.1 Finite Alphabets	283
	18.2 The Turing machine	284
	18.3 Decision problems	290
	19 Complexity theory	294
	19.1 Running time	294
	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	348
	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	364
	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	377
	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