基本信息
【插图】
作译者
[俄] 尤里·涅斯捷罗夫（Yurii Nesterov ） 著：
尤里·涅斯罗杰夫（Yurii Nesterov）是著名的优化专家。他是Nesterov梯度加速法、多项式时间内点法、平滑技术、正则化牛顿法等方面开创性著作的作者。曾获丹吉格奖(2000)、冯·诺依曼理论奖(2009)、SIAM杰出论文奖(2014)、欧洲金奖(2016)等多项国际大奖。
尤里·涅斯罗杰夫（Yurii Nesterov）是著名的优化专家。他是Nesterov梯度加速法、多项式时间内点法、平滑技术、正则化牛顿法等方面开创性著作的作者。曾获丹吉格奖(2000)、冯·诺依曼理论奖(2009)、SIAM杰出论文奖(2014)、欧洲金奖(2016)等多项国际大奖。
目录
译者序
前言
致谢
引言
第一部分黑箱优化
第1章非线性优化
11非线性优化引论
111问题的一般描述
112数值方法的性能
113全局优化的复杂度界
114优化领域的“身份证”
12无约束极小化的局部算法
121松弛和近似
122可微函数类
123梯度法
124牛顿法
13非线性优化中的一阶方法
131梯度法和牛顿法有何不同
132共轭梯度法
133约束极小化问题
前言
致谢
引言
第一部分黑箱优化
第1章非线性优化
11非线性优化引论
111问题的一般描述
112数值方法的性能
113全局优化的复杂度界
114优化领域的“身份证”
12无约束极小化的局部算法
121松弛和近似
122可微函数类
123梯度法
124牛顿法
13非线性优化中的一阶方法
131梯度法和牛顿法有何不同
132共轭梯度法
133约束极小化问题
前言
写作本书的想法来自Springer的编辑，他们建议作者更新著作Introductory Lectures on Convex Optimization: Basic Course，这是2003年由Kluwer出版社出版的［39］.事实上，这本书的主要部分写于1997~1998年，所以其内容至少有20年的历史.对于凸优化这样一个活跃的领域，这确实是很长的时间.
然而，在开始研究相关内容之后，作者很快意识到，这一不大的目标根本无法实现.［39］主要是为关于凸优化的短学期课程(12节课)服务的，反映了当时该领域的主要算法成果.因此，一些重要的概念和想法，特别是与各种对偶理论有关的，被毫不留情地从内容中删除了.在某种意义上，［39］仍然适用于介绍凸优化算法基本概念的较短课程.对该内容的任何扩充都需要做出复杂的解释，以说明为什么所选的内容比书架上的许多其他有趣的候选材料更为重要.
于是，作者做出了一个艰难的决定——写一本新书，它包括［39］的所有内容，以及该领域在过去20年中最重要的进展.从时间节点上看，本书涵盖的时间段直到2012年当然，为了保持一致性，我们添加了几篇最新发表的论文成果，这对书中讨论的主题很重要. .因此，有关随机坐标下降法和通用方法的较新结果、零阶算法的复杂度结果和求解大规模问题的方法仍然没有包括进来.然而，在我们看来，这些非常有意义的主题还没有成熟到可以进行专题介绍的地步，尤其是以讲课的形式.
从方法论的角度看，这本书的新颖之处主要在于对偶的大量出现.现在读者可以从两个方面看待问题：原始和对偶.与［39］相比，本书的内容增加了一倍，这看起来对一个全面的介绍来说是合理的.但是很显然，本书的内容太多了，不适合作为一个学期的教材.然而，它很适合一个两学期的课程，或者，它的不同部分可以分别用于不同的现代优化教学课程.我们将在“引言”的最后讨论这个问题.
在本书中，我们包括三个对专题文献来说全新的主题.
● 光滑技术.该方法完全改变了我们对大多数应用中出现的非光滑优化问题复杂度的理解.它基于可用光滑函数逼近不可微凸函数，并用快速梯度法极小化新目标.与标准的次梯度法相比，新算法每次迭代的复杂度没有变化，然而，新算法迭代次数的估计值变成与标准次梯度算法迭代次数的平方根成正比.由于在实践中这些迭代次数通常是成千上万甚至百万的数量级，所以计算时间方面的好处非常惊人.
● 二阶算法的全局复杂度界.二阶算法及其最著名的代表——牛顿法，是数值分析中最古老的算法之一.然而，在牛顿法的三次正则化被发现之后，它们的全局复杂度分析才刚刚开始.对于这种经典算法的新变形，我们可以为不同问题类给出全局复杂度界.因此，我们现在可以比较不同的二阶方法的全局效率，并开发加速算法.这些算法的一个全新特点是极小化过程中用到目标函数的模型积累.同时，我们可以为它们推导复杂度下界，并研究最优的二阶算法.对于求解非线性方程组的算法也可以进行类似的修改.
● 相对尺度优化.定义最优化问题近似解的标准方法是引入绝对精度.然而，在许多工程应用中，以相对尺度(百分比)来度量解的质量是很自然的.为了朝这个方向调整极小化算法，我们引入了目标函数的一个特殊模型，并为计算一个与目标函数拓扑结构相兼容的适度度量应用了高效的预处理算法.因此，我们得到了非常有效的优化算法，其复杂度界与输入数据的大小具有弱依赖关系.
我们希望本书对广大读者有用处，包括数学、经济学和工程专业的学生，不同领域的实践者，以及优化理论、运筹学和计算机科学的研究人员.过去几十年这个领域发展的主要经验是，有效的优化算法只能通过智慧地使用特定问题实例的结构来研究.为了做到这一点，参考成功的例子总是有用的.我们相信本书将为感兴趣的读者提供大量这类信息.
尤里·涅斯捷罗夫，比利时新鲁汶
2018年1月
然而，在开始研究相关内容之后，作者很快意识到，这一不大的目标根本无法实现.［39］主要是为关于凸优化的短学期课程(12节课)服务的，反映了当时该领域的主要算法成果.因此，一些重要的概念和想法，特别是与各种对偶理论有关的，被毫不留情地从内容中删除了.在某种意义上，［39］仍然适用于介绍凸优化算法基本概念的较短课程.对该内容的任何扩充都需要做出复杂的解释，以说明为什么所选的内容比书架上的许多其他有趣的候选材料更为重要.
于是，作者做出了一个艰难的决定——写一本新书，它包括［39］的所有内容，以及该领域在过去20年中最重要的进展.从时间节点上看，本书涵盖的时间段直到2012年当然，为了保持一致性，我们添加了几篇最新发表的论文成果，这对书中讨论的主题很重要. .因此，有关随机坐标下降法和通用方法的较新结果、零阶算法的复杂度结果和求解大规模问题的方法仍然没有包括进来.然而，在我们看来，这些非常有意义的主题还没有成熟到可以进行专题介绍的地步，尤其是以讲课的形式.
从方法论的角度看，这本书的新颖之处主要在于对偶的大量出现.现在读者可以从两个方面看待问题：原始和对偶.与［39］相比，本书的内容增加了一倍，这看起来对一个全面的介绍来说是合理的.但是很显然，本书的内容太多了，不适合作为一个学期的教材.然而，它很适合一个两学期的课程，或者，它的不同部分可以分别用于不同的现代优化教学课程.我们将在“引言”的最后讨论这个问题.
在本书中，我们包括三个对专题文献来说全新的主题.
● 光滑技术.该方法完全改变了我们对大多数应用中出现的非光滑优化问题复杂度的理解.它基于可用光滑函数逼近不可微凸函数，并用快速梯度法极小化新目标.与标准的次梯度法相比，新算法每次迭代的复杂度没有变化，然而，新算法迭代次数的估计值变成与标准次梯度算法迭代次数的平方根成正比.由于在实践中这些迭代次数通常是成千上万甚至百万的数量级，所以计算时间方面的好处非常惊人.
● 二阶算法的全局复杂度界.二阶算法及其最著名的代表——牛顿法，是数值分析中最古老的算法之一.然而，在牛顿法的三次正则化被发现之后，它们的全局复杂度分析才刚刚开始.对于这种经典算法的新变形，我们可以为不同问题类给出全局复杂度界.因此，我们现在可以比较不同的二阶方法的全局效率，并开发加速算法.这些算法的一个全新特点是极小化过程中用到目标函数的模型积累.同时，我们可以为它们推导复杂度下界，并研究最优的二阶算法.对于求解非线性方程组的算法也可以进行类似的修改.
● 相对尺度优化.定义最优化问题近似解的标准方法是引入绝对精度.然而，在许多工程应用中，以相对尺度(百分比)来度量解的质量是很自然的.为了朝这个方向调整极小化算法，我们引入了目标函数的一个特殊模型，并为计算一个与目标函数拓扑结构相兼容的适度度量应用了高效的预处理算法.因此，我们得到了非常有效的优化算法，其复杂度界与输入数据的大小具有弱依赖关系.
我们希望本书对广大读者有用处，包括数学、经济学和工程专业的学生，不同领域的实践者，以及优化理论、运筹学和计算机科学的研究人员.过去几十年这个领域发展的主要经验是，有效的优化算法只能通过智慧地使用特定问题实例的结构来研究.为了做到这一点，参考成功的例子总是有用的.我们相信本书将为感兴趣的读者提供大量这类信息.
尤里·涅斯捷罗夫，比利时新鲁汶
2018年1月
媒体评论
凸优化在应用数学、经济金融、工程、计算机科学，特别是数据科学和机器学习方面越来越重要，本书对凸优化进行了全面且现代的介绍。
本书由该领域的权威专家撰写，内容包括凸优化的算法理论的新进展，不但包含一阶、二阶极小化加速技术的一个统一且严格的表述，而且为读者提供了光滑化方法的完整处理，这极大地扩展了梯度类型方法的应用范围。此外，本书还详细讨论了结构优化的几种有效方法，包括相对尺度优化法和多项式时间内点法。
本书对理论优化的研究人员以及从事优化问题工作的专业人士非常有用，它提供了许多成功的例子来说明如何开发非常快速的专门极小化算法。基于作者的讲座实践，本书自然也可以作为工程、经济、计算机科学和数学学科学生的介绍性及高级凸优化课程教材。
作者简介
尤里·涅斯捷罗夫（Yurii Nesterov）是著名的优化专家。他是Nesterov梯度加速法、多项式时间内点法、平滑技术、正则化牛顿法等方面开创性著作的作者。曾获丹吉格奖(2000)、冯·诺依曼理论奖(2009)、SIAM杰出论文奖(2014)、欧洲金奖(2016)等多项国际大奖。
本书由该领域的权威专家撰写，内容包括凸优化的算法理论的新进展，不但包含一阶、二阶极小化加速技术的一个统一且严格的表述，而且为读者提供了光滑化方法的完整处理，这极大地扩展了梯度类型方法的应用范围。此外，本书还详细讨论了结构优化的几种有效方法，包括相对尺度优化法和多项式时间内点法。
本书对理论优化的研究人员以及从事优化问题工作的专业人士非常有用，它提供了许多成功的例子来说明如何开发非常快速的专门极小化算法。基于作者的讲座实践，本书自然也可以作为工程、经济、计算机科学和数学学科学生的介绍性及高级凸优化课程教材。
作者简介
尤里·涅斯捷罗夫（Yurii Nesterov）是著名的优化专家。他是Nesterov梯度加速法、多项式时间内点法、平滑技术、正则化牛顿法等方面开创性著作的作者。曾获丹吉格奖(2000)、冯·诺依曼理论奖(2009)、SIAM杰出论文奖(2014)、欧洲金奖(2016)等多项国际大奖。
