Convexity and Well-Posed Problems

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