凸优化算法

本书特色

[

本书几乎囊括了所有主流的凸优化算法。包括梯度法、次梯度法、多面体逼近法、邻近法和内点法等。这些方法通常依赖于代价函数和约束条件的凸性（而不一定依赖于其可微性），并与对偶性有着直接或间接的联系。作者针对具体问题的特定结构，给出了大量的例题，来充分展示算法的应用。各章的内容如下： 第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 

封面

书名:凸优化算法

作者:博塞卡斯

页数:564

定价:¥89.0

出版社:清华大学出版社

出版日期:2016-05-01

ISBN:9787302430704

PDF电子书大小:71MB 高清扫描完整版