凸优化教程(原书第2版)

凸优化在应用数学、经济金融、工程、计算机科学，特别是数据科学和机器学习方面越来越重要，本书对凸优化进行了全面且现代的介绍。 本书由该领域的权威专家撰写，内容包括凸优化的算法理论的新进展，不但包含一阶、二阶极小化加速技术的一个统一且严格的表述，而且为读者提供了光滑化方法的完整处理，这极大地扩展了梯度类型方法的应用范围。此外，本书还详细讨论了结构优化的几种有效方法，包括相对尺度优化法和多项式时间内点法。本书对理论优化的研究人员以及从事优化问题工作的专业人士非常有用，它提供了许多成功的例子来说明如何开发非常快速的专门极小化算法。基于作者的讲座实践，本书自然也可以作为工程、经济、计算机科学和数学学科学生的介绍性及高级凸优化课程教材。

尤里·涅斯捷罗夫（Yurii Nesterov）是有名的优化专家。他是Nesterov梯度加速法、多项式时间内点法、平滑技术、正则化牛顿法等方面开创性著作的作者。曾获丹吉格奖(2000)、冯·诺依曼理论奖(2009)、SIAM杰出论文奖(2014)、欧洲金奖(2016)等多项国际大奖。

译者序
前言
致谢
引言
第一部分黑箱优化
第1章非线性优化
1.1非线性优化引论
1.1.1问题的一般描述
1.1.2数值方法的性能
1.1.3全局优化的复杂度界
1.1.4优化领域的“身份证”
1.2无约束极小化的局部算法
1.2.1松弛和近似
1.2.2可微函数类
1.2.3梯度法
1.2.4牛顿法
1.3非线性优化中的一阶方法
1.3.1梯度法和牛顿法有何不同
1.3.2共轭梯度法
1.3.3约束极小化问题
第2章光滑凸优化
2.1光滑函数的极小化
2.1.1光滑凸函数
2.1.2函数类F∞,1L(n)的复杂度下界
2.1.3强凸函数类
2.1.4函数类S∞,1μ,L(n)的复杂度下界
2.1.5梯度法
2.2很优算法
2.2.1估计序列
2.2.2降低梯度的范数
2.2.3凸集
2.2.4梯度映射
2.2.5简单集上的极小化问题
2.3具有光滑分量的极小化问题
2.3.1极小极大问题
2.3.2梯度映射
2.3.3极小极大问题的极小化方法
2.3.4带有函数约束的优化问题
2.3.5约束极小化问题的算法
第3章非光滑凸优化
3.1一般凸函数
3.1.1动机和定义
3.1.2凸函数运算
3.1.3连续性和可微性
3.1.4分离定理
3.1.5次梯度
3.1.6次梯度计算
3.1.7很优性条件
3.1.8极小极大定理
3.1.9原始对偶算法的基本要素
3.2非光滑极小化方法
3.2.1一般复杂度下界
3.2.2估计近似解性能
3.2.3次梯度算法
3.2.4函数约束的极小化问题
3.2.5很优拉格朗日乘子的近似
3.2.6强凸函数
3.2.7有限维问题的复杂度界
3.2.8割平面算法
3.3完整数据的算法
3.3.1目标函数的非光滑模型
3.3.2Kelley算法
3.3.3水平集法
3.3.4约束极小化问题
第4章二阶算法
4.1牛顿法的三次正则化
4.1.1二次逼近的三次正则化
4.1.2一般收敛性结果
4.1.3具体问题类的全局效率界
4.1.4实现问题
4.1.5全局复杂度界
4.2加速的三次牛顿法
4.2.1实向量空间
4.2.2一致凸函数
4.2.3牛顿迭代的三次正则化
4.2.4一个加速算法
4.2.5二阶算法的全局非退化性
4.2.6极小化强凸函数
4.2.7伪加速
4.2.8降低梯度的范数
4.2.9非退化问题的复杂度
4.3很优二阶算法
4.3.1复杂度下界
4.3.2一个概念性很优算法
4.3.3搜索过程的复杂度
4.4修正的高斯牛顿法
4.4.1高斯牛顿迭代的二次正则化
4.4.2修正的高斯牛顿过程
4.4.3全局收敛速率
4.4.4讨论
第二部分结构优化
第5章多项式时间内点法
5.1自和谐函数
5.1.1凸优化中的黑箱概念
5.1.2牛顿法实际上做什么
5.1.3自和谐函数的定义
5.1.4主要不等式
5.1.5自和谐性和Fenchel对偶
5.2自和谐函数极小化
5.2.1牛顿法的局部收敛性
5.2.2路径跟踪算法
5.2.3强凸函数极小化
5.3自和谐障碍函数
5.3.1研究动机
5.3.2自和谐障碍函数的定义
5.3.3主要不等式
5.3.4路径跟踪算法
5.3.5确定解析中心
5.3.6函数约束问题
5.4显式结构问题的应用
5.4.1自和谐障碍函数参数的下界
5.4.2上界：通用障碍函数和极集
5.4.3线性和二次优化
5.4.4半定优化
5.4.5特别椭球
5.4.6构造凸集的自和谐障碍函数
5.4.7自和谐障碍函数的例子
5.4.8可分优化
5.4.9极小化算法的选择
第6章目标函数的原始对偶模型
6.1目标函数显式模型的光滑化
6.1.1不可微函数的光滑近似
6.1.2目标函数的极小极大模型
6.1.3合成极小化问题的快速梯度法
6.1.4应用实例
6.1.5算法实现的讨论
6.2非光滑凸优化的过间隙技术
6.2.1原始对偶问题的结构
6.2.2过间隙条件
6.2.3收敛性分析
6.2.4极小化强凸函数
6.3半定优化中的光滑化技术
6.3.1光滑化特征值的对称函数
6.3.2极小化对称矩阵的优选特征值
6.4目标函数的局部模型极小化
6.4.1Oracle线性优化
6.4.2合成目标函数的条件梯度算法
6.4.3收缩型条件梯度
6.4.4原始对偶解的计算
6.4.5合成项的强凸性
6.4.6极小化二次模型
第7章相对尺度优化
7.1目标函数的齐次模型
7.1.1圆锥无约束极小化问题
7.1.2次梯度近似算法
7.1.3问题结构的直接使用
7.1.4应用实例
7.2凸集的近似
7.2.1计算近似椭球
7.2.2极小化线性函数的优选绝对值
7.2.3具有非负元素的双线性矩阵博弈
7.2.4极小化对称矩阵的谱半径
7.3障碍函数次梯度算法
7.3.1自和谐障碍函数的光滑化
7.3.2障碍函数次梯度法
7.3.3正凹函数极大化
7.3.4应用
7.3.5随机规划的替代——在线优化
7.4混合精度优化
7.4.1严格正函数
7.4.2拟牛顿法
7.4.3近似解的解释
附录A求解一些辅助优化问题
参考文献评注
参考文献
索引