Contents 

1. Convex Optimization Models: An Overview . . . . . . p. 1 

1.1. LagrangeDuality .......... .......... p.2 

1.1.1. Separable Problems 每 Decomposition . . . . . . . . . p. 7 

1.1.2. Partitioning .................... p.9 

1.2. Fenchel Duality and Conic Programming . . . . . . . . . . p. 10 

1.2.1. LinearConicProblems . . . . . . . . . . . . . . . p.15 

1.2.2. Second Order Cone Programming . . . . . . . . . . . p. 17 

1.2.3. Semide.nite Programming . . . . . . . . . . . . . . p. 22 

1.3. AdditiveCostProblems . . . . . . . . . . . . . . . . . p.25 

1.4. LargeNumberofConstraints . . . . . . . . . . . . . . . p.34 

1.5. ExactPenalty Functions . . . . . . . . . . . . . . . . p.39 

1.6. Notes,Sources,andExercises . . . . . . . . . . . . . . p.47 

2. Optimization Algorithms: An Overview . . . . . . . . p. 53 

2.1. IterativeDescentAlgorithms . . . . . . . . . . . . . . . p.55 

2.1.1. Di.erentiable Cost Function Descent 每 Unconstrained . . . . Problems ..................... p.58 

2.1.2. Constrained Problems 每 Feasible Direction Methods . . . p. 71 

2.1.3. Nondi.erentiable Problems 每 Subgradient Methods . . . p. 78 

2.1.4. Alternative Descent Methods . . . . . . . . . . . . . p. 80 

2.1.5. IncrementalAlgorithms . . . . . . . . . . . . . . . p.83 

2.1.6. Distributed Asynchronous Iterative Algorithms . . . . p. 104 

2.2. ApproximationMethods . . . . . . . . . . . . . . . p.106 

2.2.1. Polyhedral Approximation . . . . . . . . . . . . . p. 107 

2.2.2. Penalty, Augmented Lagrangian, and Interior . . . . . . . PointMethods .................. p.108 

2.2.3. Proximal Algorithm, Bundle Methods, and . . . . . . . . . TikhonovRegularization . . . . . . . . . . . . . . p.110 

2.2.4. Alternating Direction Method of Multipliers . . . . . p. 111 

2.2.5. Smoothing of Nondi.erentiable Problems . . . . . . p. 113 

2.3. Notes,Sources,andExercises . . . . . . . . . . . . . p.119 

3. SubgradientMethods . . . . . . . . . . . . . . . p.135 

3.1. Subgradients of Convex Real-Valued Functions . . . . . . p. 136 

iv 

Contents 

3.1.1. Characterization of the Subdi.erential . . . . . . . . p. 146 

3.2. Convergence Analysis of Subgradient Methods . . . . . . p. 148 

3.3. .-SubgradientMethods ................ p.162 

3.3.1. Connection with Incremental Subgradient Methods . . p. 166 

3.4. Notes,Sources,andExercises . . . . . . . . . . . . . . p.167 

4. Polyhedral Approximation Methods . . . . . . . . . p. 181 

4.1. Outer Linearization 每 Cutting Plane Methods . . . . . . p. 182 

4.2. Inner Linearization 每 Simplicial Decomposition . . . . . . p. 188 

4.3. Duality of Outer and Inner Linearization . . . . . . . . . p. 194 

4.4. Generalized Polyhedral Approximation . . . . . . . . . p. 196 

4.5. Generalized Simplicial Decomposition . . . . . . . . . . p. 209 

4.5.1. Di.erentiableCostCase . . . . . . . . . . . . . . p.213 

4.5.2. Nondi.erentiable Cost and Side Constraints . . . . . p. 213 

4.6. Polyhedral Approximation for Conic Programming . . . . p. 217 

4.7. Notes,Sources,andExercises . . . . . . . . . . . . . . p.228 

5. ProximalAlgorithms . . . . . . . . . . . . . . . p.233 

5.1. Basic Theory of Proximal Algorithms . . . . . . . . . . p. 234 

5.1.1. Convergence ................... p.235 

5.1.2. RateofConvergence. . . . . . . . . . . . . . . . p.239 

5.1.3. Gradient Interpretation . . . . . . . . . . . . . . p. 246 

5.1.4. Fixed Point Interpretation, Overrelaxation, . . . . . . . . . andGeneralization ................ p.248 

5.2. DualProximalAlgorithms . . . . . . . . . . . . . . . p.256 

5.2.1. Augmented Lagrangian Methods . . . . . . . . . . p. 259 

5.3. Proximal Algorithms with Linearization . . . . . . . . . p. 268 

5.3.1. Proximal Cutting Plane Methods . . . . . . . . . . p. 270 

5.3.2. BundleMethods ................. p.272 

5.3.3. Proximal Inner Linearization Methods . . . . . . . . p. 276 

5.4. Alternating Direction Methods of Multipliers . . . . . . . p. 280 

5.4.1. Applications in Machine Learning . . . . . . . . . . p. 286 

5.4.2. ADMM Applied to Separable Problems . . . . . . . p. 289 

5.5. Notes,Sources,andExercises . . . . . . . . . . . . . . p.293 

6. Additional Algorithmic Topics . . . . . . . . . . . p. 301 

6.1. GradientProjectionMethods . . . . . . . . . . . . . . p.302 

6.2. Gradient Projection with Extrapolation . . . . . . . . . p. 322 

6.2.1. An Algorithm with Optimal Iteration Complexity . . . p. 323 

6.2.2. Nondi.erentiable Cost 每 Smoothing . . . . . . . . . p. 326 

6.3. ProximalGradientMethods . . . . . . . . . . . . . . p.330 

6.4. Incremental Subgradient Proximal Methods . . . . . . . p. 340 

6.4.1. Convergence for Methods with Cyclic Order . . . . . p. 344 

Contents 

6.4.2. Convergence for Methods with Randomized Order . . p. 353 

6.4.3. Application in Specially Structured Problems . . . . . p. 361 

6.4.4. Incremental Constraint Projection Methods . . . . . p. 365 

6.5. CoordinateDescentMethods . . . . . . . . . . . . . . p.369 

6.5.1. Variants of Coordinate Descent . . . . . . . . . . . p. 373 

6.5.2. Distributed Asynchronous Coordinate Descent . . . . p. 376 

6.6. Generalized Proximal Methods . . . . . . . . . . . . . p. 382 

6.7. .-Descent and Extended Monotropic Programming . . . . p. 396 

6.7.1. .-Subgradients .................. p.397 

6.7.2. .-DescentMethod........ ......... p.400 

6.7.3. Extended Monotropic Programming Duality . . . . . p. 406 

6.7.4. Special Cases of Strong Duality . . . . . . . . . . . p. 408 

6.8. InteriorPointMethods . . . . . . . . . . . . . . . . p.412 

6.8.1. Primal-Dual Methods for Linear Programming . . . . p. 416 

6.8.2. Interior Point Methods for Conic Programming . . . . p. 423 

6.8.3. Central Cutting Plane Methods . . . . . . . . . . . p. 425 

6.9. Notes,Sources,andExercises . . . . . . . . . . . . . . p.426 

Appendix A: Mathematical Background . . . . . . . . p. 443 

A.1. LinearAlgebra ........... ......... p.445 

A.2. TopologicalProperties . . . . . . . . . . . . . . . . p.450 

A.3. Derivatives ..................... p.456 

A.4. ConvergenceTheorems . . . . . . . . . . . . . . . . p.458 

Appendix B: Convex Optimization Theory: A Summary . p. 467 

B.1. Basic Concepts of Convex Analysis . . . . . . . . . . . p. 467 

B.2. Basic Concepts of Polyhedral Convexity . . . . . . . . . p. 489 

B.3. Basic Concepts of Convex Optimization . . . . . . . . . p. 494 

B.4. Geometric Duality Framework . . . . . . . . . . . . . p. 498 

B.5. Duality andOptimization . . . . . . . . . . . . . . . p.505 

References .............. ......... p.519 

Index ................. ......... p.557