Convex and stochastic optimization

Preface......Page 7
Contents......Page 8
  1.1.1 Optimization Problems......Page 13
  1.1.2 Separation of Convex Sets......Page 16
  1.1.3 Weak Duality and Saddle Points......Page 22
  1.1.4 Linear Programming and Hoffman Bounds......Page 23
  1.1.5 Conjugacy......Page 29
  1.2.1 Perturbation Duality......Page 44
  1.2.2 Subdifferential Calculus......Page 56
  1.2.3 Minimax Theorems......Page 61
  1.2.4 Calmness......Page 63
  1.3.1 Maxima of Bounded Functions......Page 65
  1.3.2 Linear Conical Optimization......Page 68
  1.3.3 Polyhedra......Page 69
  1.3.4 Infimal Convolution......Page 72
  1.3.5 Recession Functions and the Perspective Function......Page 74
  1.4.1 Convex Relaxation......Page 77
  1.4.2 Applications of the Shapley–Folkman Theorem......Page 82
  1.4.3 First-Order Optimality Conditions......Page 84
 1.5 Notes......Page 86
  2.1.1 The Frobenius Norm......Page 87
  2.1.2 Positive Semidefinite Linear Programming......Page 89
  2.2.1 Computation of the Subdifferential......Page 92
  2.2.2 Examples......Page 96
  2.2.3 Logarithmic Penalty......Page 97
  2.3.1 Relaxation of Quadratic Problems......Page 99
  2.3.2 Relaxation of Integer Constraints......Page 102
  2.4.1 Examples of SOC Reformulations......Page 103
  2.4.2 Linear SOC Duality......Page 105
  2.4.3 SDP Representation......Page 106
  2.5.1 Framework......Page 107
  2.5.2 Multipliers with Finite Support......Page 109
  2.5.3 Chebyshev Approximation......Page 113
  2.5.4 Chebyshev Polynomials and Lagrange Interpolation......Page 115
  2.6.1 Nonnegative Polynomials......Page 118
  2.6.2 Characterisation of Moments......Page 123
  2.6.3 Maximal Loading......Page 126
 2.7 Notes......Page 127
  3.1.1 Measurable Spaces......Page 129
  3.1.2 Measures......Page 134
  3.1.3 Kolmogorov\'s Extension of Measures......Page 137
  3.1.4 Limits of Measurable Functions......Page 139
  3.1.5 Integration......Page 140
  3.1.6 Lp Spaces......Page 146
  3.1.7 Bochner Integrals......Page 151
 3.2 Integral Functionals......Page 153
  3.2.1 Minimization of Carathéodory Integrals......Page 154
  3.2.2 Measurable Multimappings......Page 155
  3.2.3 Convex Integrands......Page 157
  3.2.4 Conjugates of Integral Functionals......Page 158
  3.2.5 Deterministic Decisions in mathbbRm......Page 162
  3.2.6 Constrained Random Decisions......Page 164
  3.2.7 Linear Programming with Simple Recourse......Page 165
  3.3.1 Integrals of Multimappings......Page 168
  3.3.2 Constraints on Integral Terms......Page 171
 3.4 Examples and Exercises......Page 173
 3.5 Notes......Page 176
  4.2.1 Framework......Page 177
  4.2.2 Optimized Utility......Page 179
  4.3.1 General Properties......Page 180
  4.3.2 Convex Monetary Measures of Risk......Page 181
  4.3.3 Acceptation Sets......Page 182
  4.3.5 Deviation and Semideviation......Page 184
  4.3.6 Value at Risk and CVaR......Page 186
 4.4 Notes......Page 188
  5.1.1 Maximum Likelihood......Page 189
  5.2.1 Probabilities over Metric Spaces......Page 190
  5.2.2 Convergence in Law......Page 191
  5.2.3 Central Limit Theorems......Page 197
  5.2.4 Delta Theorems......Page 198
  5.2.5 Solving Equations......Page 200
  5.3.1 The Empirical Distribution......Page 202
  5.3.2 Minimizing over a Sample......Page 203
  5.3.3 Uniform Convergence of Values......Page 205
  5.3.4 The Asymptotic Law......Page 206
  5.3.5 Expectation Constraints......Page 207
  5.4.1 The Principle of Large Deviations......Page 210
 5.5 Notes......Page 212
  6.1.2 Construction of the Conditional Expectation......Page 213
  6.1.4 Computation in Some Simple Cases......Page 218
  6.1.5 Convergence Theorems......Page 219
  6.1.6 Conditional Variance......Page 220
  6.1.7 Compatibility with a Subspace......Page 221
  6.1.8 Compatibility with Measurability Constraints......Page 224
  6.1.9 No Recourse......Page 225
  6.2.1 Dynamic Uncertainty......Page 226
  6.2.2 Abstract Optimality Conditions......Page 227
  6.2.3 The Growing Information Framework......Page 229
  6.2.4 The Standard full Information Framework......Page 230
  6.2.6 Elementary Examples......Page 231
  6.2.7 Application to the Turbining Problem......Page 232
 6.3 Notes......Page 234
  7.1.1 Markov Chains......Page 235
  7.1.2 The Dynamic Programming Principle......Page 241
  7.1.3 Infinite Horizon Problems......Page 243
  7.1.4 Numerical Algorithms......Page 247
  7.1.5 Exit Time Problems......Page 251
  7.1.6 Problems with Stopping Decisions......Page 252
  7.2.1 Expectation Constraints......Page 255
  7.2.2 Partial Information......Page 260
  7.2.3 Linear Programming Formulation......Page 266
  7.3.1 Orientation......Page 267
  7.3.2 Transient and Recurrent States......Page 268
  7.3.3 Ergodic Dynamic Programming......Page 275
 7.4 Notes......Page 278
  8.1.1 Static Case: Kelley\'s Algorithm......Page 279
  8.1.2 Deterministic Dual Dynamic Programming......Page 281
  8.1.3 Stochastic Case......Page 284
  8.2.1 About the Frobenius Norm......Page 287
  8.2.3 Linear Programming Reformulation......Page 288
  8.2.4 Linear Conic Reformulation......Page 289
  8.2.5 Dual Bounds in a Conic Setting......Page 290
 8.3 Notes......Page 293
  9.1.1 Generalized Fenchel Conjugates......Page 294
  9.1.2 Cyclical Monotonicity......Page 296
  9.1.4 Augmented Lagrangian......Page 298
 9.2 Convex Functions of Measures......Page 300
  9.2.1 A First Result......Page 301
 9.3 Transportation Theory......Page 304
  9.3.1 The Compact Framework......Page 305
  9.3.2 Optimal Transportation Maps......Page 307
  9.3.3 Penalty Approximations......Page 308
  9.3.4 Barycenters......Page 310
 9.4 Notes......Page 312
 References......Page 313
Index......Page 318