Convex Optimization Theory

Bertsekas,D.P.Convex optimization theory(AS,2009)(ISBN 9781886529311)(600dpi)(258p) i ......Page 2
Copyright ii ......Page 3
Contents iii ......Page 4
Preface vii ......Page 8
1. Basic Concepts of Convex Analysis 1 ......Page 12
1.1. Convex Sets and Functions 2 ......Page 13
1.1.1. Convex Functions 5 ......Page 16
1.1.2. Closedness and Semicontinuity 9 ......Page 20
1.1.3. Operations with Convex Functions p. 11 ......Page 22
1.1.4. Characterizations of Differentiable Convex Functions 13 ......Page 24
1.2. Convex and Affine Hulls 19 ......Page 30
1.3. Relative Interior and Closure 23 ......Page 34
1.3.1. Calculus of Relative Interiors and Closures 28 ......Page 39
1.3.2. Continuity of Convex Functions 35 ......Page 46
1.3.3. Closures of Functions 37 ......Page 48
1.4. Recession Cones 43 ......Page 54
1.4.1. Directions of Recession of a Convex Function 50 ......Page 61
1.4.2. Nonemptiness of Intersections of Closed Sets 57 ......Page 68
1.4.3. Closedness Under Linear Transformations 64 ......Page 75
1.5. Hyperplanes 67 ......Page 78
1.5.1. Hyperplane Separation 68 ......Page 79
1.5.2. Proper Hyperplane Separation 73 ......Page 84
1.5.3. Nonvertical Hyperplane Separation 80 ......Page 91
1.6. Conjugate Functions 82 ......Page 93
1.7. Summary 89 ......Page 100
2. Basic Concepts of Polyhedral Convexity 91 ......Page 102
2.1. Extreme Points 92 ......Page 103
2.2. Polar Cones 99 ......Page 110
2.3.1. Polyhedral Cones and Farkas’ Lemma 102 ......Page 113
2.3.2. Structure of Polyhedral Sets 104 ......Page 115
2.3.3. Polyhedral Functions 109 ......Page 120
2.4. Polyhedral Aspects of Optimization 111 ......Page 122
3. Basic Concepts of Convex Optimization 115 ......Page 126
3.1. Constrained Optimization 116 ......Page 127
3.2. Existence of Optimal Solutions 118 ......Page 129
3.3. Partial Minimization of Convex Functions 122 ......Page 133
3.4. Saddle Point and Minimax Theory 127 ......Page 138
4. Geometric Duality Framework 131 ......Page 142
4.1. Min Common/Max Crossing Duality 132 ......Page 143
4.2.1. Connection to Conjugate Convex Functions 137 ......Page 148
4.2.2. General Optimization Duality 138 ......Page 149
4.2.3. Optimization with Inequality Constraints 139 ......Page 150
4.2.4. Augmented Lagrangian Duality 140 ......Page 151
4.2.5. Minimax Problems 141 ......Page 152
4.3. Strong Duality Theorem 146 ......Page 157
4.4. Existence of Dual Optimal Solutions 149 ......Page 160
4.5. Duality and Polyhedral Convexity 153 ......Page 164
4.6. Summary 158 ......Page 169
5. Duality and Optimization 159 ......Page 170
5.1. Nonlinear Farkas’ Lemma 160 ......Page 171
5.2. Linear Programming Duality 164 ......Page 175
5.3. Convex Programming Duality 167 ......Page 178
5.3.1. Strong Duality Theorem - Inequality Constraints 168 ......Page 179
5.3.2. Optimality Conditions 169 ......Page 180
5.3.3. Partially Polyhedral Constraints 171 ......Page 182
5.3.4. Duality and Existence of Optimal Primal Solutions 176 ......Page 187
5.3.5. Fenchel Duality 179 ......Page 190
5.3.6. Conic Duality 181 ......Page 192
5.4. Subgradients and Optimality Conditions 182 ......Page 193
5.4.1. Subgradients of Conjugate Functions 187 ......Page 198
5.4.2. Subdifferential Calculus 192 ......Page 203
5.4.3. Optimality Conditions 195 ......Page 206
5.4.4. Directional Derivatives 196 ......Page 207
5.5.1. Minimax Duality Theorems 200 ......Page 211
5.5.2. Saddle Point Theorems 204 ......Page 215
5.6. Theorems of the Alternative 209 ......Page 220
5.7. Nonconvex Problems 216 ......Page 227
5.7.1. Duality Gap in Separable Problems 217 ......Page 228
5.7.2. Duality Gap in Minimax Problems 226 ......Page 237
Appendix A: Mathematical Background 227 ......Page 238
Notes and Sources 239 ......Page 250
cover......Page 1