01 / 导读
导读
引用
Chong, E. K. P., Lu, W.-S., & Żak, S. H. (2023). An Introduction to Optimization: With Applications to Machine Learning (5th ed.). Wiley.
章节概要
全书分五个部分共31章，约670页，另有参考文献和索引。出版社称每章之后都有MATLAB练习和习题。据出版社介绍，第5版新增了一章拉格朗日对偶，并扩充了矩阵博弈、投影梯度算法和机器学习的内容。
第一部分（第1–5章）：数学回顾
第1章"证明方法与一些记号"仅用几页介绍真值表、德摩根律、条件语句与双条件语句、直接证明、反证法（逆否）、归谬法和归纳法，以及集合记号。第2章"向量空间与矩阵"讲向量与矩阵、秩、线性方程组、内积与范数。第3章"变换"讲线性变换、特征值与特征向量、正交投影、二次型和矩阵范数。第4章"几何中的概念"讲线段、超平面与线性簇、凸集、邻域、多胞形与多面体。第5章"微积分基础"讲数列与极限、可微性、导数矩阵、求导法则、水平集与梯度、泰勒级数。
第二部分（第6–14章）：无约束优化
第6章"集合约束与无约束优化基础"引入集合约束和无约束问题以及局部极小点的条件。第7章"一维搜索方法"讲黄金分割法、斐波那契法、二分法、牛顿法、割线法、括号法以及多维优化中的线搜索。第8章"梯度法"和第9章"牛顿法"连同分析一起介绍最速下降法和牛顿法，以及列文伯格–马夸特修正和非线性最小二乘。第10章"共轭方向法"和第11章"拟牛顿法"讲共轭梯度算法、秩一修正、DFP和BFGS。第12章"求解线性方程组"讲最小二乘、递推最小二乘、最小范数解和卡茨马兹算法。第13章"无约束优化与神经网络"讲单神经元训练和反向传播。第14章"全局搜索算法"讲内尔德–米德算法、模拟退火、粒子群优化和遗传算法。
第三部分（第15–19章）：线性规划
第15章"线性规划导论"讲简史、简单例子、二维线性规划、凸多面体、标准形和基本解。第16章"单纯形法"展开行运算、规范增广矩阵、单纯形算法、矩阵形式、两阶段法和修正单纯形法。第17章"对偶"讲对偶线性规划、其性质和矩阵博弈。第18章"非单纯形法"讲哈奇扬方法、仿射缩放法和卡玛卡方法。第19章"整数线性规划"讲幺模矩阵和戈莫里割平面法。
第四部分（第20–25章）：非线性约束优化
第20章"等式约束问题"讲切空间与法空间、拉格朗日条件、二阶条件，以及线性约束下二次函数的极小化。第21章"不等式约束问题"讲卡鲁什–库恩–塔克条件和二阶条件。第22章"凸优化问题"讲凸函数、凸优化问题和半定规划。第23章"拉格朗日对偶"（本版新增）讲原–对偶对、对偶的一般性质、强对偶和凸的情形。第24章"约束优化算法"讲投影、投影梯度法及其收敛性、拉格朗日算法和罚函数法。第25章"多目标优化"讲帕累托解、帕累托前沿的计算、化为单目标问题以及不确定的线性规划问题。
第五部分（第26–31章）：机器学习中的优化
第26章"机器学习问题与特征工程"讲数据归一化、方向梯度直方图、主成分分析与线性自编码器。第27章"随机梯度下降算法"讲随机梯度下降及其方差缩减的变体。第28章"线性回归及其变体"讲最小二乘回归、交叉验证和正则化。第29章"用于分类的逻辑回归"讲二分类和多类别分类。第30章"支持向量机"讲合页损失、二分类与多类别分类以及核技巧。第31章"K均值聚类"讲该算法、K-means++初始化、变体以及用向量量化进行图像压缩。
核心概念
第一部分：数学回顾
- 证明方法：直接证明、反证（逆否）、归谬和归纳。
- 二次型：后面用来陈述二阶条件的矩阵工具。
- 凸集与多面体：线性规划和凸优化所依赖的几何。
- 梯度与泰勒级数：局部极小点条件背后的微积分。
第二部分：无约束优化
- 局部极小点的条件：第6章中的一阶和二阶条件。
- 最速下降法、牛顿法与拟牛顿法：迭代算法的几个主要系列，在第8至11章中通过分析加以比较。
- 共轭梯度算法：为二次问题设计、并推广到非二次问题的方法。
- 反向传播：用于训练神经网络的梯度计算。
第三、四部分：线性与非线性约束优化
- 单纯形法与基本解：在多面体的顶点之间移动。
- 对偶：线性规划的对偶，以及新增的第23章中非线性规划的拉格朗日对偶。
- 卡鲁什–库恩–塔克条件：不等式约束的一阶条件。
- 帕累托前沿：多目标问题中权衡解的集合。
第五部分：机器学习
- 随机梯度下降：用样本而不是整个目标函数来更新。
- 逻辑回归与支持向量机：通过优化训练出来的分类器。
- K均值聚类：通过反复指派和更新中心来聚类。
评析
优点
- 自足的预备知识。 第一部分在优化各章开始之前复习所需的线性代数、几何和微积分，因此有知识缺口的读者可以在书中补上。
- 范围广而有条理。 一本书从无约束方法走到线性规划、非线性约束问题和机器学习。出版社把本书定位为一到两学期的本科高年级或研究生起始阶段课程的教材。
- 计算方面的支持。 出版社宣传每章之后的MATLAB练习和例题。作者的网页链接了算法的M文件、第五部分的数据集和代码，以及Paul Atzberger及其UCSB学生提供的部分算法的Python代码。
- 来自旧版书评的称赞。 封底引用了MAA Reviews对第3版的评价：本书引导读者沿着学习路径前进，例子陈述清楚，结果的呈现注重细节。
局限
- 解答手册仅限教师。 解答手册只提供给采用本书的教师，因此自学者只能在没有答案的情况下做题。
- 某些地方广而不深。 从目录看，有些话题的处理似乎很简短：半定规划只是第22章的一节，整数规划是只有三节的一章。需要全面学习凸优化的读者需要一本专门的教材。
- 神经网络止于基础。 它们只出现在第13章（单神经元训练和反向传播），而机器学习部分列出的是回归、逻辑回归、支持向量机和K均值，没有列出深度网络的结构。
- 对一门课来说篇幅很长。 31章、约670页，一门课必须取舍。
在课程中的定位
在最优化与应用数学的书单中，Chong、Lu和Żak是涵盖标准课程内容的通用教材。Guenin、Könemann和Tunçel的 A Gentle Introduction to Optimization 只假定学过线性代数的第一门课，以问题的建模和单纯形法为基础，是更平缓的第一门课。Boyd和Vandenberghe的 Convex Optimization 是当凸问题和对偶成为主题时更严格的后续读物，本书的第22、23章可以作为过渡。
书单上的其他书涵盖面更广：Ostaszewski的 Advanced Mathematical Methods 把线性代数和微积分与应用结合起来，Jacques的 Mathematics for Economics and Business 把优化放在经济背景下，Goriely的 Applied Mathematics: A Very Short Introduction 则是对应用数学家如何工作的非技术性概览。
如何使用本书
出版社把本书定位为最优化理论与方法的一到两学期的本科高年级或研究生起始阶段课程的教材，也供数学、运筹学、电气工程、经济学、统计学和商学领域的研究人员和从业者参考。本站列出的先修条件是多元微积分和线性代数。
一个实用的计划如下：
- 一学期课程的核心： 无约束优化的第6–11章、线性规划的第15–17章，以及约束优化的第20、21章。
- 拓展： 为走向现代理论的读者准备的凸优化第22章和拉格朗日对偶第23章；第12–14章和第18–19章可作为选读。
- 机器学习路线： 为第五部分做准备，较为合适的是提供梯度法、最小二乘和反向传播的第6–9章、第12章和第13章。
- 练习： 借助作者网页上的MATLAB或Python代码做练习，并把第一部分当作复习，而不是从头读到尾。