Contents 0.1 Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1 Background 7 1.1 Euclidean spaces . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Symmetric matrices . . . . . . . . . . . . . . . . . . . . . . . . 16 2 Inequality constraints 22 2.1 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 Theorems of the alternative . . . . . . . . . . . . . . . . . . . 30 2.3 Max-functions and first order conditions . . . . . . . . . . . . 36 3 Fenchel duality 42 3.1 Subgradients and convex functions . . . . . . . . . . . . . . . 42 3.2 The value function . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3 The Fenchel conjugate . . . . . . . . . . . . . . . . . . . . . . 61 4 Convex analysis 78 4.1 Continuity of convex functions . . . . . . . . . . . . . . . . . . 78 4.2 Fenchel biconjugation . . . . . . . . . . . . . . . . . . . . . . . 90 4.3 Lagrangian duality . . . . . . . . . . . . . . . . . . . . . . . . 103 5 Special cases 113 5.1 Polyhedral convex sets and functions . . . . . . . . . . . . . . 113 5.2 Functions of eigenvalues . . . . . . . . . . . . . . . . . . . . . 120 5.3 Duality for linear and semidefinite programming . . . . . . . . 126 5.4 Convex process duality . . . . . . . . . . . . . . . . . . . . . . 132 6 Nonsmooth optimization 143 6.1 Generalized derivatives . . . . . . . . . . . . . . . . . . . . . . 143 3 6.2 Nonsmooth regularity and strict differentiability . . . . . . . . 151 6.3 Tangent cones . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 6.4 The limiting subdifferential . . . . . . . . . . . . . . . . . . . 167 7 The Karush-Kuhn-Tucker theorem 176 7.1 An introduction to metric regularity . . . . . . . . . . . . . . 176 7.2 The Karush-Kuhn-Tucker theorem . . . . . . . . . . . . . . . 184 7.3 Metric regularity and the limiting subdifferential . . . . . . . . 191 7.4 Second order conditions . . . . . . . . . . . . . . . . . . . . . 197 8 Fixed points 204 8.1 Brouwer’s fixed point theorem . . . . . . . . . . . . . . . . . . 204 8.2 Selection results and the Kakutani-Fan fixed point theorem . . 216 8.3 Variational inequalities . . . . . . . . . . . . . . . . . . . . . . 227 9 Postscript: infinite versus finite dimensions 238 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 9.2 Finite dimensionality . . . . . . . . . . . . . . . . . . . . . . . 240 9.3 Counterexamples and exercises . . . . . . . . . . . . . . . . . . 243 9.4 Notes on previous chapters . . . . . . . . . . . . . . . . . . . . 249 9.4.1 Chapter 1: Background . . . . . . . . . . . . . . . . . . 249 9.4.2 Chapter 2: Inequality constraints . . . . . . . . . . . . 249 9.4.3 Chapter 3: Fenchel duality . . . . . . . . . . . . . . . . 249 9.4.4 Chapter 4: Convex analysis . . . . . . . . . . . . . . . 250 9.4.5 Chapter 5: Special cases . . . . . . . . . . . . . . . . . 250 9.4.6 Chapter 6: Nonsmooth optimization . . . . . . . . . . 250 9.4.7 Chapter 7: The Karush-Kuhn-Tucker theorem . . . . . 251 9.4.8 Chapter 8: Fixed points . . . . . . . . . . . . . . . . . 251 10 List of results and notation 252 10.1 Named results and exercises . . . . . . . . . . . . . . . . . . . 252 10.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 Bibliography 276 Index
|