在人工智能与大数据时代，优化算法已成为机器学习与数据科学的核心支柱。本书以独特的应用视角，将抽象的数学理论与实际工程问题紧密结合，为读者架起了一座从理论到实践的桥梁。
本书由优化领域权威学者Stephen J. Wright和Benjamin Recht撰写，旨在为读者提供一本条理清晰、系统全面的优化技术指南，尤其聚焦数据科学与机器学习领域的核心优化技术。书中详细阐述了基本优化算法，并分析了它们的收敛性和复杂度。全书共11章，第1章通过典型案例阐释优化在现代数据分析中的应用；第2～10章深入剖析多种核心算法，包括加速梯度法、随机梯度法（机器学习的核心算法）、坐标下降法（高效处理高维问题的利器）、简单约束问题的梯度法、具有非平滑项的凸优化问题的理论和算法，以及约束优化问题的对偶方法；第11章拓展至深度学习与控制领域的梯度计算方法（如自动微分、反向传播的优化视角）。

本书由威斯康星大学Stephen J. Wright与加州大学伯克利分校Benjamin Recht教授联袂撰写，内容源自两所名校机器学习与优化课程讲义，经多年教学实践打磨而成。全书系统阐述数据分析与机器学习中的优化理论，涵盖梯度法、随机梯度法、坐标下降法等核心算法，并深入讲解深度学习中的梯度计算方法。每章配备习题，理论与实践紧密结合，既适合作为高年级本科生及低年级研究生教材，也适合作为机器学习工程师与科研人员的重要参考资料。译本由Airbnb和Meta资深机器学习工程师精心翻译，著译双馨。

前言
优化公式和算法长期以来一直在数据分析和机器学习中发挥着核心作用. 极大似然的概念可以追溯到18世纪后期高斯和拉普拉斯的研究，这类问题推动了20世纪下半叶无约束优化问题研究的发展. Mangasarian在20世纪60年代发表的关于使用线性规划进行模式分离的论文，在机器学习这一学科诞生初期就明确了机器学习和优化之间的联系. 在20世纪90年代，优化技术（尤其是二次规划和对偶）是支持向量机和核学习发展的关键. 在19972010年间，正则化/稀疏优化、变量选择和压缩感知之间出现了许多协同效应. 在当前深度学习时代，两种优化技术，即随机梯度和自动微分（又名反向传播）是十分重要的.
本书是对连续优化基础知识的介绍，着重讲解与数据分析和机器学习有关的技术. 我们主要（但不完全）针对凸问题讨论了基本算法，并分析了它们的收敛性和复杂度. 第1章概述了优化在现代数据分析中的应用. 第2～10章讨论了梯度法，包括加速梯度法和随机梯度法、坐标下降法、简单约束问题的梯度法、具有凸非平滑项的优化问题的理论和算法，以及约束优化问题的对偶方法. 第11章从多个角度探讨了深度学习和控制领域中出现的函数梯度计算方法. 本书适合作为高年级本科生或低年级研究生一个季度或一个学期的课程教材. 我们和同事已经在低年级研究生的课程中广泛使用了本书内容的初稿.
本书的写作可追溯至2010年左右，当时我们着手改革优化课程体系，试图在实用优化技术和对优化算法的非渐近性分析之间建立平衡. 那时，优化算法分析的风格正在转变为更加强调最坏情况的复杂性. 但人们更多的是根据算法的最坏情况界限来评估算法的优劣，而不是考虑它们在应用科学实践中的表现. 本书介于分析和实践之间.
从威斯康星大学的CS726和CS730课程开始，我们着手撰写讲义、习题和本书初稿. Benjamin 2013年到加州大学伯克利分校后，这些讲义成为EECS227C课程的核心内容. 本书的内容很大程度上来自优化算法理论的前沿发展成果. 例如，在文中的多个部分，我们利用了Lieven Vandenberghe多年来为加州大学洛杉矶分校ECE236C课程编写并经过多年完善的优秀课件. 我们对加速法的介绍反映了将优化算法视为动态系统的趋势，并且深受与Laurent Lessard和 Andrew Packard合作研究的影响. 在选择本书要包含的内容时，我们尽量不被那些在实践中未广泛使用的方法所干扰，同时强调理论如何指导应用研究人员选择和设计算法.
我们感谢许多其他同事，他们的意见优化了本书的内容. 在我们于2013年秋季在西蒙斯研究所大数据计划的训练营中介绍了有关优化算法的综述后，Moritz Hardt最初启发我们编写本书. 他随后就本书初稿的呈现方式和组织结构提供了反馈. Ashia Wilson曾是 Benjamin教授EECS227C课程的助教，她的意见和笔记在多个方面帮助我们厘清了教学信息. 最近，Martin Wainwright教授了EECS227C课程并提供了宝贵的反馈，Jelena
Diakonikolas在教授 CS726课程后对前几章进行了校正. André Wibisono提供了关于加速梯度法的见解，Ching?pei Lee提供了关于坐标下降法的有用建议. 我们还要感谢在威斯康星大学选修CS726和CS730课程以及在加州大学伯克利分校学习 EECS227C课程的众多学生，他们发现了书中的错别字，试做了课后习题，他们的支持让教授这门课程变得非常愉快. 最后，我们要感谢西蒙斯研究所多次给予我们的支持，包括2017年秋季，我们两人共同参与了西蒙斯优化领域的研究项目.

斯蒂芬·J. 赖特
（Stephen J. Wright）
现任威斯康星大学麦迪逊分校George B. Dantzig教授、 Sheldon Lubar讲席教授，以及 Amar和Balinder Sohi计算机科学教授，同时担任威斯康星州发现研究所（Wisconsin Institute for Discovery）的研究员。他主要研究计算优化及其在数据科学和科学工程其他领域的应用。他是美国工业与应用数学学会（SIAM）会士，曾获2014年IEEE W. R. G. Baker杰出论文奖、2020年INFORMS优化学会Khachiyan终身成就奖以及2020年NeurIPS时间检验奖。他著有多部优化领域经典教材与参考书，包括Primal Dual Interior-Point Methods（1987）和Numerical Optimization（2006）。
本杰明·雷希特
（Benjamin Recht）
加州大学伯克利分校电气工程与计算机科学系副教授。其研究团队致力于通过运用优化、统计和动力系统的数学工具，提升机器学习系统在动态不确定环境中的稳健性。他曾获总统科学家与工程师早期职业奖、Alfred P. Sloan研究奖、2012年SIAM/MOS拉格朗日连续优化奖、2014年Jamon奖、2015年William O. Baker研究倡议奖，以及2017年和2020年NeurIPS时间检验奖。

张璐，2021年7月至今于爱彼迎任算法工程师，此前曾在Facebook、eBay任软件工程师。2011年12月于密歇根州立大学获电子工程专业理学硕士学位，2009年7月于中国科学技术大学电子信息工程学院获工学学士学位。

目录
译者序
前言
第1章　概述 1
1.1　数据分析和优化 1
1.2　最小二乘法 3
1.3　矩阵因子分解问题 4
1.4　支持向量机 5
1.5　逻辑回归 8
1.6　深度学习 9
1.7　重点 11
注释和参考 12
第2章　平滑优化的基础 13
2.1　优化问题的解的分类 13
2.2　泰勒定理 14
2.3　刻画平滑函数的最小值 16
2.4　凸集和函数 18
2.5　强凸函数 20
注释和参考 22
习题 22
第3章　下降法 24
3.1　下降方向 24
3.2　最速下降法 25
3.2.1　一般情况 26
3.2.2　凸函数情况 27
3.2.3　强凸函数情况 28
3.2.4　收敛速率的比较 30
3.3　下降法：收敛性 31
3.4　线搜索法：方向选择 33
3.5　线搜索法：步长选择 35
3.6?收敛到近似的二阶必要点 40
3.7　镜像下降 42
3.8　KL和PL属性 47
注释和参考 48
习题 48
第4章　使用动量的梯度法 51
4.1　来自微分方程的启发 52
4.2　Nesterov法：凸二次方程 53
4.3　强凸函数的收敛性 58
4.4　弱凸函数的收敛性 61
4.5　共轭梯度法 64
4.6　收敛速率的下界 66
注释和参考 67
习题 68
第5章　随机梯度法 71
5.1　示例与启发 72
5.1.1　噪声梯度 72
5.1.2　增量梯度法 73
5.1.3　分类和感知器 73
5.1.4　经验风险最小化 74
5.2　随机性和步长：深入分析 75
5.2.1　示例：计算均值 76
5.2.2　随机Kaczmarz法 77
5.3　收敛分析的关键假设 80
5.3.1　案例1：有界梯度(Lg=0) 81
5.3.2　案例2：随机Kaczmarz
(B=0, Lg=0) 81
5.3.3　案例3：加性高斯噪声 82
5.3.4　案例4：增量梯度 82
5.4　收敛分析 83
5.4.1　案例1：Lg=0 84
5.4.2　案例2：B=0 86
5.4.3　案例3：B和Lg都非零 87
5.5　实施方面的问题 89
5.5.1　轮次 89
5.5.2　迷你批量处理 89
5.5.3　使用动量加速 90
注释和参考 90
习题 91
第6章　坐标下降法 95
6.1　机器学习中的坐标下降法 96
6.2　平滑凸函数的坐标下降法 98
6.2.1　利普希茨常数 98
6.2.2　随机坐标下降法：有放回
抽样 99
6.2.3　循环坐标下降法 105
6.2.4　随机排列坐标下降法：无放回抽样 107
6.3　块坐标下降法 107
注释和参考 109
习题 110
第7章　约束优化的一阶方法 112
7.1　最优性条件 112
7.2　欧几里得投影 114
7.3　投影梯度算法 116
7.3.1　一般情况：一种短步法 117
7.3.2　一般情况：回溯法 118
7.3.3　平滑强凸情形 119
7.3.4　动量变体 120
7.3.5　其他搜索方向 120
7.4　条件梯度（Frank-Wolfe）法 121
注释和参考 123
习题 124
第8章　非平滑函数和次梯度 126
8.1　次梯度和次微分 127
8.2　次微分和方向导数 131
8.3　次微分运算 134
8.4　凸集和凸约束优化 137
8.5　复合非平滑函数的最优性条件 139
8.6　近端算子和莫罗包络 141
注释和参考 143
习题 143
第9章　非平滑优化方法 145
9.1　次梯度下降 146
9.2　次梯度法 148
9.3　正则化优化的近端梯度法 151
9.4　结构化非平滑函数的近端坐标
下降法 156
9.5　近端点法 158
注释和参考 159
习题 159
第10章　对偶性和算法 161
10.1　二次惩罚函数 161
10.2　拉格朗日函数和对偶性 162
10.3　一阶最优性条件 165
10.4　强对偶 168
10.5　对偶算法 170
10.5.1　对偶次梯度 170
10.5.2　增广拉格朗日函数法 170
10.5.3　交替方向乘数法 172
10.6　对偶算法的一些应用 173
10.6.1　共识优化 173
10.6.2　效用最大化 175
10.6.3　线性和二次规划 176
注释和参考 177
习题 178
第11章　微分和伴随 179
11.1　向量函数嵌套组合的链式法则 179
11.2　伴随法 181
11.3　深度学习中的伴随 182
11.4　自动微分 183
11.5　通过拉格朗日函数和隐函数定理
推导185
11.5.1　渐进式函数的约束优化
　公式 186
11.5.2　无约束和约束公式的一般
　观点 187
11.5.3　扩展：控制 188
注释和参考 188
习题 189
附　　录　一些背景信息 190
参考文献 209