本书提供了凸优化一个全面的、最新的介绍，这是一个日益重要的领域，在应用数学、经济和金融、工程和计算机科学，特别是在数据科学和机器学习领域有广泛应用。

无

写作本书的想法来自Springer的编辑，他们建议作者更新著作Introductory Lectures on Convex Optimization: Basic Course，这是2003年由Kluwer出版社出版的［39］.事实上，这本书的主要部分写于1997~1998年，所以其内容至少有20年的历史.对于凸优化这样一个活跃的领域，这确实是很长的时间.
然而，在开始研究相关内容之后，作者很快意识到，这一不大的目标根本无法实现.［39］主要是为关于凸优化的短学期课程(12节课)服务的，反映了当时该领域的主要算法成果.因此，一些重要的概念和想法，特别是与各种对偶理论有关的，被毫不留情地从内容中删除了.在某种意义上，［39］仍然适用于介绍凸优化算法基本概念的较短课程.对该内容的任何扩充都需要做出复杂的解释，以说明为什么所选的内容比书架上的许多其他有趣的候选材料更为重要.
于是，作者做出了一个艰难的决定——写一本新书，它包括［39］的所有内容，以及该领域在过去20年中最重要的进展.从时间节点上看，本书涵盖的时间段直到2012年当然，为了保持一致性，我们添加了几篇最新发表的论文成果，这对书中讨论的主题很重要. .因此，有关随机坐标下降法和通用方法的较新结果、零阶算法的复杂度结果和求解大规模问题的方法仍然没有包括进来.然而，在我们看来，这些非常有意义的主题还没有成熟到可以进行专题介绍的地步，尤其是以讲课的形式.
从方法论的角度看，这本书的新颖之处主要在于对偶的大量出现.现在读者可以从两个方面看待问题：原始和对偶.与［39］相比，本书的内容增加了一倍，这看起来对一个全面的介绍来说是合理的.但是很显然，本书的内容太多了，不适合作为一个学期的教材.然而，它很适合一个两学期的课程，或者，它的不同部分可以分别用于不同的现代优化教学课程.我们将在“引言”的最后讨论这个问题.
在本书中，我们包括三个对专题文献来说全新的主题.
● 光滑技术.该方法完全改变了我们对大多数应用中出现的非光滑优化问题复杂度的理解.它基于可用光滑函数逼近不可微凸函数，并用快速梯度法极小化新目标.与标准的次梯度法相比，新算法每次迭代的复杂度没有变化，然而，新算法迭代次数的估计值变成与标准次梯度算法迭代次数的平方根成正比.由于在实践中这些迭代次数通常是成千上万甚至百万的数量级，所以计算时间方面的好处非常惊人.
● 二阶算法的全局复杂度界.二阶算法及其最著名的代表——牛顿法，是数值分析中最古老的算法之一.然而，在牛顿法的三次正则化被发现之后，它们的全局复杂度分析才刚刚开始.对于这种经典算法的新变形，我们可以为不同问题类给出全局复杂度界.因此，我们现在可以比较不同的二阶方法的全局效率，并开发加速算法.这些算法的一个全新特点是极小化过程中用到目标函数的模型积累.同时，我们可以为它们推导复杂度下界，并研究最优的二阶算法.对于求解非线性方程组的算法也可以进行类似的修改.
● 相对尺度优化.定义最优化问题近似解的标准方法是引入绝对精度.然而，在许多工程应用中，以相对尺度(百分比)来度量解的质量是很自然的.为了朝这个方向调整极小化算法，我们引入了目标函数的一个特殊模型，并为计算一个与目标函数拓扑结构相兼容的适度度量应用了高效的预处理算法.因此，我们得到了非常有效的优化算法，其复杂度界与输入数据的大小具有弱依赖关系.
我们希望本书对广大读者有用处，包括数学、经济学和工程专业的学生，不同领域的实践者，以及优化理论、运筹学和计算机科学的研究人员.过去几十年这个领域发展的主要经验是，有效的优化算法只能通过智慧地使用特定问题实例的结构来研究.为了做到这一点，参考成功的例子总是有用的.我们相信本书将为感兴趣的读者提供大量这类信息.

尤里·涅斯捷罗夫，比利时新鲁汶
2018年1月

数学

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

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

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

本书是国际著名最优化理论与算法专家Yurii Nesterov的最新代表性专著，是他多年研究成果的总结，不但包括了传统最优化算法及其理论，而且系统性地给出了一些较新的研究成果.
凸优化在学术界、工程应用界都具有非常重要的地位，是所有最优化研究的基础.本书内容涵盖一般非线性凸优化的基本内容，包括光滑优化、非光滑优化、约束优化等问题的一阶算法和二阶算法的很多理论性成果，给出大量用对偶、路径跟踪、光滑化等技术处理各类优化问题的实例，并设计了具有收敛性保证的高效算法，同时给出利用复杂度下界引导设计最优算法的模式.其中利用牛顿法的三次正则化技术研究二阶算法的全局复杂度界、相对尺度优化等内容是其他优化专著少有的.
该书涉及的优化理论及相关算法设计相对完整，特别是算法复杂度上下界的具体证明、相应算法的具体设计都非常系统.它既可作为引导数学、工程、经济学等专业的学生涉足优化领域的教科书，也可作为不同领域的优化实践者有效选择优化算法来解决实际问题的工具书，同时还可作为优化、运筹学和计算机科学等领域的研究人员系统掌握优化理论的参考书.本书非常适合作为本科生、研究生的现代优化教学课程的教材.
本书作者是国际著名优化专家，为了尽可能准确地呈现作者想要表达的思想，在翻译过程中，在不影响内容理解的基础上，尽量遵照原文的表达，避免过度意译.如文中多次(甚至过多次)出现“我们”“那么/于是”等词，是由于原著有大量的“we”“then/thus”等.这类不影响意思表达的直译我们尽量保留.另外也注意到一些术语实在不便于用中文表达，就保留原英文.如“Oracle”这个词，字典中对它的翻译都很难匹配其在文中或参考文献中的意思，它在文中的不同地方出现时含义很难用一个中文专用名字概况，故保留原词.在人名的翻译方面我们也灵活处理：对译名用词固定的人名采用中文表达，如牛顿、拉格朗日、欧拉等；而有些人名其中文译名出现较少，中文译名在不同资料中也不统一，为了准确起见，我们采用原英文表述.另外有一些专业术语也存在不同资料译法不统一的情况，请读者留意.如proxfunction，有资料翻译为“近端函数”“近似函数”，而本书翻译为“近邻函数”(由于它体现了邻域的概念).又如“composite optimization”，有些资料翻译为“复合优化”或“组合优化”，但本书描述的是两个函数相加的优化问题，与“函数复合”、离散中的“排列组合”关系很弱，故翻译为“合成优化”.译者尽管从事了多年的最优化教学和研究工作，但在翻译工作上并不专业，在完美呈现著名大师的著作方面必然有不足之处，敬请谅解.
感谢陈玉雪、付翠、李冬、刘云瑞、马家军、平瑞、乔慧、万星、杨婷、张俊娜、张转等对本书翻译工作的付出，感谢同事冯象初教授，他就有关专业术语翻译与译者进行讨论.全书由周水生定稿并对全部翻译文字负责.

译者
2020年4月

译者序
前言
致谢
引言
第一部分黑箱优化
第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求解一些辅助优化问题
参考文献评注
参考文献
索引