Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
1 Convex sets and convex functions: the fundamentals . . . . . . . 1
1.1 Convex sets: basic definitions and properties . . . . . . . . . . . . . . . . 1
1.2 Convex functions: basic definitions and properties . . . . . . . . . . . 11
2 ContinuityandΓ(X) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1 Continuity and Lipschitz behavior . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Lower semicontinuity and Γ(X) . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 The derivatives and the subdifferential . . . . . . . . . . . . . . . . . . . . 31
3.1 Properties of the directional derivatives . . . . . . . . . . . . . . . . . . . . 32
3.2 The subgradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Gˆateaux and Fr´echet derivatives and the subdifferential . . . . . . 39
3.4 The subdifferential of the sum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5 The subdifferential multifunction . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.6 Twice differentiable functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.7 The approximate subdifferential . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4 Minima and quasi minima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1 The Weierstrass theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2 The Ekeland variational principle . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3 Minimizing a convex function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.1 Level sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5 The Fenchel conjugate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.1 Generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.2 The bijection between Γ(X) and Γ∗(X∗) . . . . . . . . . . . . . . . . . . . 83
5.3 The subdifferentials of f and f∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.4 The conjugate of the sum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
viii Contents
5.5 Sandwiching an affine function between a convex and a
concave function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.1 The setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.2 Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.3 The convex case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.4 Regular problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.5 The Lagrangean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.6 Examples of dual problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.6.1 Convex programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.6.2 An example in the calculus of variations . . . . . . . . . . . . . . 114
7 Linear programming and game theory . . . . . . . . . . . . . . . . . . . . . 117
7.1 Linear programming I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.2 Zero sum games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.3 Linear programming II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.4 Cooperative game theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8 Hypertopologies, hyperconvergences . . . . . . . . . . . . . . . . . . . . . . . 139
8.1 Definitions and examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.2 Relations among topologies, new topologies . . . . . . . . . . . . . . . . . 146
8.3 A convergence for sequences of convex sets. . . . . . . . . . . . . . . . . . 152
8.4 Metrizability and complete metrizability . . . . . . . . . . . . . . . . . . . . 154
8.5 A summary of the topologies when X is a normed space . . . . . . 160
8.6 Epiconvergence of functions and a first stability result . . . . . . . . 162
9 Continuity of some operations between functions . . . . . . . . . . 169
9.1 Continuity of the conjugation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
9.2 Continuity of the sum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9.3 Convergence of functions and of their subdifferentials . . . . . . . . 181
10 Well-posed problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
10.1 Tykhonov, Levitin–Polyak and strong well-posedness . . . . . . . . . 186
10.2 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
10.3 A new well-posedness concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
10.4 A digression: projecting a point on a closed convex set . . . . . . . 209
11 Generic well-posedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
11.1 Porosity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
11.2 Some observations on concave/convex functions . . . . . . . . . . . . . 223
11.3 Genericity results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
11.4 Porosity results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
11.4.1 Unconstrained convex problems . . . . . . . . . . . . . . . . . . . . . 233
11.4.2 Convex programming I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
11.4.3 Convex programming II . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Contents ix
11.4.4 Quadratic programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
12 More exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
A Functional analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
A.1 Hahn–Banach theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
A.2 The Banach–Dieudonn´e–Krein–Smulian theorem . . . . . . . . . . . . 261
B Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
B.1 The Baire theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
B.2 First countability of hypertopologies . . . . . . . . . . . . . . . . . . . . . . . 266
B.3 Convergence of nets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
B.4 A more sophisticated look at hypertopologies . . . . . . . . . . . . . . . 269
C More game theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
D Symbols, notations, definitions and important theorems . . . 291
D.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
D.2 Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
D.3 Spaces of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
D.4 Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
D.5 Important theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303