Information-based complexity of convex programming

Example: one-dimensional convex problems......Page 9
  Prerequisites......Page 17
  Brunn, Minkowski and Convex Pie......Page 18
 Class of general convex problems: description and complexity......Page 29
  Case of problems without functional constraints......Page 31
 The general case: problems with functional constraints......Page 36
 Exercises: Extremal Ellipsoids......Page 40
  Tschebyshev-type results for sums of random vectors......Page 46
 Lower complexity bound......Page 51
 The Ellipsoid method......Page 56
  Ellipsoids......Page 57
  The Ellipsoid method......Page 59
  Is it actually difficult to find the center of gravity?......Page 61
  Some extensions of the Cutting Plane scheme......Page 65
 Classes P and NP......Page 75
 Linear Programming......Page 78
  Polynomial solvability of FLP......Page 80
  From detecting feasibility to solving linear programs......Page 82
  Example of Klee and Minty......Page 84
  The method of outer simplex......Page 85
 Convex-concave games......Page 87
 Cutting plane scheme for games: updating localizers......Page 89
 Cutting plane scheme for games: generating solutions......Page 90
 Concluding remarks......Page 94
 Exercises: Maximal Inscribed Ellipsoid......Page 95
 Variational inequalities with monotone operators......Page 101
 Cutting plane scheme for variational inequalities......Page 108
 Exercises: Around monotone operators......Page 111
 Goals and motivations......Page 115
 The main result......Page 116
 Upper complexity bound: the Gradient Descent......Page 117
 The lower bound......Page 120
 Exercises: Around Subgradient Descent......Page 122
 Subgradient Descent method......Page 127
 Bundle methods......Page 132
  The Level method......Page 133
  Concluding remarks......Page 137
 Exercises: Mirror Descent......Page 138
Large-scale games and variational inequalities......Page 143
 Subrgadient Descent method for variational inequalities......Page 144
  Level method for games......Page 147
  Level method for variational inequalities......Page 150
  "Prox-Level"......Page 152
  Level for constrained optimization......Page 154
Smooth convex minimization problems......Page 159
 Traditional methods......Page 160
 Complexity of classes Sn(L,R)......Page 161
  Upper complexity bound: Nesterov's method......Page 162
  Lower bound......Page 166
  Appendix: proof of Proposition 10.2.1......Page 169
 Composite problem......Page 171
 Gradient mapping......Page 172
 Nesterov's method for composite problems......Page 175
 Smooth strongly convex problems......Page 178
 Complexity of quadratic problems: motivation......Page 181
 Families of source-representable quadratic problems......Page 183
 Lower complexity bounds......Page 184
 Complexity of linear operator equations......Page 187
 Exercises: Around quadratic forms......Page 192
Optimality of the Conjugate Gradient method......Page 195
 The Conjugate Gradient method......Page 196
 Main result......Page 197
  CGM and orthogonal polynomials......Page 198
  Momentum inequality......Page 201
  Proof of (13.3.20)......Page 202
  Concluding the proof of Theorem 13.2.1......Page 204
 Exercises: Around Conjugate Gradient Method......Page 206
Convex Stochastic Programming......Page 211
  The Stochastic Approximation method......Page 214
  Comments......Page 216
 MinMax Stochastic Programming problems......Page 218
Hints to exercises......Page 221
Solutions to exercises......Page 235