1. Basic Concepts of Convex Analysis . . t ~ ~ ~ ~ ~ p. 1
1.1. Convex Sets and Functions _ - p. 2
1.1.1. Convex Functions _ . - - - - - - - . - p. 5
1.1.2. Closedness and Semicontinuity _ . - p. 9
1.1.3. Operations with Convex Functions _ - p. 11
1.1.4. Characterizations of Differentiable Convex Functions _ p. 13
1.2. Convex and Affine Hulls . _ - p. 19
1.3. Relative Interior and Closure _ - p. 23
1.3.1. Calculus of Relative Interiors and Closures _ p. 28
1.3.2. Continuity of Convex Functions _ p. 35
1.3.3. Closures of Functions - . . . . . . . - p. 37
1.4. Recession Cones _ - - p. 43
1.4.1. Directions of Recession of a Convex Function . . . . p. 50
1.4.2. Nonemptiness of Intersections of Closed Sets _ p. 57
1.4.3. Closedness Under Linear rlyansformations _ p. 64
1.5. Hyperplanes _ . . - . - . - - - - p. 67
1.5.1. Hyperplane Separation . . . - - - . - - - - p. 68
1.5.2. Proper Hyperplane Separation . . . . . . . . . . p. 73
1.5.3. Nonvertical Hyperplane Separation . . . . p. 80
1.6. Conjugate Functions - . - - - - - - - p. 82
1.7. Summary _ - - p. 89
2. Basic Concepts of Polyhedral Convexity ~ ~ ~ ~ ~ ~ p. 91
2.1. Extreme Points . _ . . - - - - - - p. 92
2.2. Polar Cones _ - - p. 99
2.3. Polyhedral Sets and Functions . . - - - - - . - - - p. 102
2.3.1. Polyhedral Cones and Farkas' Lemma _ p. 102
2.3.2. Structure of Polyhedral Sets . _ _ _ _ . - - - - p. 104
2.3.3. PolyhedralFunctions _ . . . - - - - . - - - p. 109
2.4. Polyhedral Aspects of Optimization . . . . . . . . p. 111
3. Basic Concepts of Convex Optimization ~ ~ ~ ~ ~ p. 115
3.1. Constrained Optimization . . . . . . . . . - - . - p. 116
3.2. Existence of Optimal Solutions . . . - - - - - . - - p. 118
3.3. Partial Minimization of Convex Functions . _ _ . . . p. 122
3.4. Saddle Point and Minimax Theory . _ _ . _ _ _ _ . p. 127
4. Geometric Duality Framework . . . . ~ ~ ~ ~ ~ p. 131
4.1. Min Common/Max Crossing Duality . _ _ _ . . . . p. 132
4.2. Some Special Cases . _ p. 137
4.2.1. Connection to Conjugate Convex Functions _ p. 137
4.2.2. General Optimization Duality . _ _ . _ _ _ _ . p. 138
4.2.3. Optimization with Inequality Constraints _ p. 139
4.2.4. Augmented Lagrangian Duality _ . _ . . p. 140
4.2.5. Minimax Problems _ - p. 141
4.3. Strong Duality Theorem . . . . _ _ _ _ . . . p. 146
4.4. Existence of Dual Optimal Solutions . . . . . . . . p. 149
4.5. Duality and Polyhedral Convexity . - - - - - - . . p. 153
4.6. Summary _ _ _ p. 158
5. Duality and Optimization . .
5.1. Nonlinear Farkas' Lemma _ . . . p. 160
5.2. Linear Programming Duality _ p. 164
5.3. Convex Programming Duality . . _ . . _ _ _ . . p. 167
5.3.1. Strong Duality Theorem - Inequality Constraints .
5.3.2. Optimality Conditions _ . . . . _ _ . . p. 169
5.3.3. Partially Polyhedral Constraints .
L _ p. 171
5.3.4. Duality and Existence of Optimal Primal Solutions
t ns _ p. 176
5.3.5. Fenchel Duality .
t- . . - - p. 179
5.3.6. Conic Duality . p. 181
t - p.
5.4. Subgradients and Optimality Conditions . _ . _ . p. 182
5.4.1. Subgradients of Conjugate Function
L ions _ p. 187
5.4.2. Subdifferential Calculus .
L _ _ p. 192
5.4.3. Optimality Conditions _ . _ . _ _ _ . . p. 195
5.4.4. Directional Derivatives _
L _ p. 196
5.5. Minimax Theory _ . . . . . . _ _ . . . p. 200
5.5.1. Minimax Duality Theorems . _ _ _ _ . 'p. 200
5.5.2. Saddle Point Theor
U eorems _ . _ _ . . p. 204
5.6. Theorems ofthe Alternative . _ _ _ _ _ _ . _ . . p. 209
5.7. Nonconvex Problems _ . _ _ ' ' _ . . . p. 216
5.7.1. Duality Gap in Separable Problems . _ _ _ . . p. 217
5.7.2. Duality Gap in Minimax Problems . . . - - . . p. 226
Appendix A: Mathematical Background . . . . . . p. 227
Notes and Sources . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ p. 239
Supplementary Chapter 6 0n Convex Optimization Algorithms . . p. 247
