Convex analysis and optimization

Dimitri P. Bertsekas , with Angelia Nedic and Asuman E. Ozdaglar.Convex Analysis and Optimization(Optimization and Computation Series, Vol.1)(AS,2003)(ISBN 1886529450)(600dpi)(549p)  ......Page 2
Copyright ......Page 3
Preface ix ......Page 8
Contents v ......Page 5
1. Basic Convexity Concepts 1 ......Page 15
1.1. Linear Algebra and Real Analysis 3 ......Page 17
1.1.1. Vectors and Matrices 5 ......Page 19
1.1.2. Topological Properties 8 ......Page 22
1.1.3. Square Matrices 15 ......Page 29
1.1.4. Derivatives 16 ......Page 30
1.2. Convex Sets and Functions 20 ......Page 34
1.3. Convex and Affine Hulls 35 ......Page 49
1.4. Relative Interior, Closure, and Continuity 39 ......Page 53
1.5. Recession Cones 49 ......Page 63
1.5.1. Nonemptiness of Intersections of Closed Sets 56 ......Page 70
1.5.2. Closedness Under Linear Transformations 64 ......Page 78
1.6. Notes, Sources, and Exercises 68 ......Page 82
2. Convexity and Optimization 83 ......Page 97
2.1. Global and Local Minima  84 ......Page 98
2.2. The Projection Theorem 88 ......Page 102
2.3. Directions of Recession and Existence of Optimal Solutions  92 ......Page 106
2.3.1. Existence of Solutions of Convex Programs 94 ......Page 108
2.3.2. Unbounded Optimal Solution Sets 97 ......Page 111
2.3.3. Partial Minimization of Convex Functions101 ......Page 115
2.4. Hyperplanes 107 ......Page 121
2.5.1. Nonvertical Hyperplanes p. 117 ......Page 131
2.5.2. Min Common/Max Crossing Duality 120 ......Page 134
2.6. Saddle Point and Minimax Theory 128 ......Page 142
2.6.1. Min Common/Max Crossing Framework for Minimax 133 ......Page 147
2.6.2. Minimax Theorems 139 ......Page 153
2.6.3. Saddle Point Theorems 143 ......Page 157
2.7. Notes, Sources, and Exercises 151 ......Page 165
3. Polyhedral Convexity 165 ......Page 179
3.1. Polar Cones166 ......Page 180
3.2. Polyhedral Cones and Polyhedral Sets  168 ......Page 182
3.2.1. Farkas’ Lemma and Minkowski-Weyl Theorem 170 ......Page 184
3.2.2. Polyhedral Sets175 ......Page 189
3.2.3. Polyhedral Functions 178 ......Page 192
3.3. Extreme Points 180 ......Page 194
3.3.1. Extreme Points of Polyhedral Sets 183 ......Page 197
3.4. Polyhedral Aspects of Optimization 186 ......Page 200
3.4.1. Linear Programming 188 ......Page 202
3.4.2. Integer Programming 189 ......Page 203
3.5.1. Polyhedral Proper Separation 192 ......Page 206
3.5.2. Min Common/Max Crossing Duality 196 ......Page 210
3.5.3. Minimax Theory Under Polyhedral Assumptions 199 ......Page 213
3.5.4. A Nonlinear Version of Farkas’ Lemma  203 ......Page 217
3.5.5. Convex Programming 208 ......Page 222
3.6. Notes, Sources, and Exercises210 ......Page 224
4. Subgradients and Constrained Optimization 221 ......Page 235
4.1. Directional Derivatives 222 ......Page 236
4.2. Subgradients and Subdifferentials 227 ......Page 241
4.3. e-Subgradients 235 ......Page 249
4.4. Subgradients of Extended Real-Valued Functions 241 ......Page 255
4.5. Directional Derivative of the Max Function 245 ......Page 259
4.6. Conical Approximations 248 ......Page 262
4.7. Optimality Conditions 255 ......Page 269
4.8. Notes, Sources, and Exercises 261 ......Page 275
5. Lagrange Multipliers  269 ......Page 283
5.1. Introduction to Lagrange Multipliers 270 ......Page 284
5.2. Enhanced Fritz John Optimality Conditions 281 ......Page 295
5.3. Informative Lagrange Multipliers 288 ......Page 302
5.3.1. Sensitivity 297 ......Page 311
5.3.2. Alternative Lagrange Multipliers  299 ......Page 313
5.4. Pseudonormality and Constraint Qualifications 302 ......Page 316
5.5. Exact Penalty Functions 313 ......Page 327
5.6. Using the Extended Representation 319 ......Page 333
5.7. Extensions Under Convexity Assumptions 324 ......Page 338
5.8. Notes, Sources, and Exercises 335 ......Page 349
6. Lagrangian Duality 345 ......Page 359
6.1. Geometric Multipliers 346 ......Page 360
6.2. Duality Theory 355 ......Page 369
6.3. Linear and Quadratic Programming Duality 362 ......Page 376
6.4. Existence of Geometric Multipliers 367 ......Page 381
6.4.1. Convex Cost - Linear Constraints 368 ......Page 382
6.4.2. Convex Cost - Convex Constraints 371 ......Page 385
6.5.1. Duality Gap and the Primal Function 374 ......Page 388
6.5.2. Conditions for No Duality Gap 377 ......Page 391
6.5.3. Subgradients of the Primal Function 382 ......Page 396
6.5.4. Sensitivity Analysis 383 ......Page 397
6.6. Fritz John Conditions when there is no Optimal Solution 384 ......Page 398
6.6.1. Enhanced Fritz John Conditions 390 ......Page 404
6.6.2. Informative Geometric Multipliers 406 ......Page 420
6.7. Notes, Sources, and Exercises 413 ......Page 427
7. Conjugate Duality 421 ......Page 435
7.1. Conjugate Functions 424 ......Page 438
7.2. Fenchel Duality Theorems 434 ......Page 448
7.2.1. Connection of Fenchel Duality and Minimax Theory 437 ......Page 451
7.2.2. Conic Duality 439 ......Page 453
7.3. Exact Penalty Functions 441 ......Page 455
7.4. Notes, Sources, and Exercises 446 ......Page 460
8. Dual Computational Methods 455 ......Page 469
8.1. Dual Derivatives and Subgradients 457 ......Page 471
8.2. Subgradient Methods 460 ......Page 474
8.2.1. Analysis of Subgradient Methods 470 ......Page 484
8.2.2. Subgradient Methods with Randomization 488 ......Page 502
8.3. Cutting Plane Methods 504 ......Page 518
8.4. Ascent Methods 509 ......Page 523
8.5. Notes, Sources, and Exercises  512 ......Page 526
References 517 ......Page 531
Index 529 ......Page 543
cover......Page 1