Preface vii
1 Background 1
1.1 Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 SymmetricMatrices . . . . . . . . . . . . . . . . . . . . . . 9
2 Inequality Constraints 15
2.1 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . 15
2.2 Theorems of the Alternative . . . . . . . . . . . . . . . . . . 23
2.3 Max-functions . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Fenchel Duality 33
3.1 Subgradients and Convex Functions . . . . . . . . . . . . . 33
3.2 The Value Function . . . . . . . . . . . . . . . . . . . . . . 43
3.3 The Fenchel Conjugate . . . . . . . . . . . . . . . . . . . . . 49
4 ConvexAnalysis 65
4.1 Continuity of Convex Functions . . . . . . . . . . . . . . . . 65
4.2 Fenchel Biconjugation . . . . . . . . . . . . . . . . . . . . . 76
4.3 Lagrangian Duality . . . . . . . . . . . . . . . . . . . . . . . 88
5 Special Cases 97
5.1 Polyhedral Convex Sets and Functions . . . . . . . . . . . . 97
5.2 Functions of Eigenvalues . . . . . . . . . . . . . . . . . . . . 104
5.3 Duality for Linear and Semidefinite Programming . . . . . . 109
5.4 Convex Process Duality . . . . . . . . . . . . . . . . . . . . 114
6 Nonsmooth Optimization 123
6.1 Generalized Derivatives . . . . . . . . . . . . . . . . . . . . 123
6.2 Regularity and Strict Differentiability . . . . . . . . . . . . 130
6.3 Tangent Cones . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.4 The Limiting Subdifferential . . . . . . . . . . . . . . . . . . 145
xi
xii Contents
7 Karush–Kuhn–Tucker Theory 153
7.1 An Introduction to Metric Regularity . . . . . . . . . . . . 153
7.2 The Karush–Kuhn–Tucker Theorem . . . . . . . . . . . . . 160
7.3 Metric Regularity and the Limiting Subdifferential . . . . . 166
7.4 Second Order Conditions . . . . . . . . . . . . . . . . . . . 172
8 Fixed Points 179
8.1 The Brouwer Fixed Point Theorem . . . . . . . . . . . . . . 179
8.2 Selection and the Kakutani–Fan Fixed Point Theorem . . . 190
8.3 Variational Inequalities . . . . . . . . . . . . . . . . . . . . . 200
9 More Nonsmooth Structure 213
9.1 Rademacher’s Theorem . . . . . . . . . . . . . . . . . . . . 213
9.2 Proximal Normals and Chebyshev Sets . . . . . . . . . . . . 218
9.3 Amenable Sets and Prox-Regularity . . . . . . . . . . . . . 228
9.4 Partly Smooth Sets . . . . . . . . . . . . . . . . . . . . . . . 233
10 Postscript: Infinite Versus Finite Dimensions 239
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10.2 Finite Dimensionality . . . . . . . . . . . . . . . . . . . . . 241
10.3 Counterexamples and Exercises . . . . . . . . . . . . . . . . 244
10.4 Notes on Previous Chapters . . . . . . . . . . . . . . . . . . 248
11 List of Results and Notation 253
11.1 Named Results . . . . . . . . . . . . . . . . . . . . . . . . . 253
11.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Bibliography 275
Index 289