《凸最佳化算法》是2016年5月清華大學出版社出版的圖書，作者是（美）Dimitri P. Bertsekas 。
基本介紹
- 中文名：凸最佳化算法
- 作者：（美）Dimitri P. Bertsekas
- 出版社：清華大學出版社
- 出版時間：2016年5月
- 定價：89 元
- ISBN：9787302430704
內容簡介,圖書目錄,
內容簡介
本書幾乎囊括了所有主流的凸最佳化算法。包括梯度法、次梯度法、多面體逼近法、鄰近法和內點法等。這些方法通常依賴於代價函式和約束條件的凸性（而不一定依賴於其可微性），並與對偶性有著直接或間接的聯繫。作者針對具體問題的特定結構，給出了大量的例題，來充分展示算法的套用。各章的內容如下： 第1章，凸最佳化模型概述； 第2章，最佳化算法概述； 第3章，次梯度算法； 第4章，多面體逼近算法； 第5章，鄰近算法； 第6章，其他算法問題。本書的一個特色是在強調問題之間的對偶性的同時，也十分重視建立在共軛概念上的算法之間的對偶性，這常常能為選擇合適的算法實現方式提供新的靈感和計算上的便利。
圖書目錄
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
