01 / 导读
导读
引用
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. 官方免费版本：https://web.stanford.edu/~boyd/cvxbook/
章节概要
全书共十一章，分为理论、应用、算法三部分，另有三个附录，每章末附习题。前言把目标定为掌握凸优化的实用知识：能够识别、建模并求解凸问题。
第1章：Introduction（引言）
本章先给出一般的优化问题，把最小二乘和线性规划作为有可靠求解方法的两类问题，并把凸优化呈现为它们的共同推广。随后对比局部优化与全局优化，说明凸问题如何帮助处理非凸问题（提供初始点、稀疏解之类的启发式方法、下界），并概述全书三个部分。
第2章：Convex sets（凸集）
先讲仿射集与凸集、锥，以及标准例子（超平面、球与椭球、范数锥、多面体和半正定锥）。接着介绍保持凸性的运算、关于真锥的广义不等式、分离与支撑超平面，以及对偶锥。
第3章：Convex functions（凸函数）
本章通过一阶与二阶条件、下水平集、上境图和 Jensen 不等式定义凸函数，并列出大量例子。随后建立保持凸性运算的“演算”（求和、逐点最大、复合、极小化、透视），再讲共轭函数、拟凸函数、对数凹与对数凸函数，以及关于广义不等式的凸性。
第4章：Convex optimization problems（凸优化问题）
这是讲建模的一章。内容包括标准形式、等价问题以及可微目标的最优性准则，然后按一般程度递增列出主要问题族：线性规划、二次规划与二阶锥规划、几何规划、锥规划与半定规划，以及带有 Pareto 最优性和标量化的向量（多准则）优化。
第5章：Duality（对偶）
由 Lagrange 函数、对偶函数和对偶问题引出弱对偶、强对偶与 Slater 约束规范。随后给出几何解释与鞍点解释、KKT 最优性条件、扰动与灵敏度分析、先变换问题再求对偶的实例、择一定理，以及向广义不等式的推广。
第6章：Approximation and fitting（逼近与拟合）
范数逼近、最小范数问题、正则化逼近（包括双准则权衡、平滑与去噪）、鲁棒逼近（随机与最坏情形），以及函数拟合与插值；拟合部分还包括通过基追踪得到稀疏表示。
第7章：Statistical estimation（统计估计）
极大似然与极大后验估计、非参数分布估计、最优检测器设计与假设检验、Chebyshev 与 Chernoff 界，以及实验设计，均表述为凸问题。
第8章：Geometric problems（几何问题）
集合上的投影、集合间的距离、Euclid 距离与角度问题、极值体积椭球、定心（Chebyshev 中心、最大体积椭球中心与解析中心）、线性与非线性判别的分类、布局与定位，以及平面布置。
第9章：Unconstrained minimization（无约束极小化）
本章在强凸性假设下引入下降方法，随后讲梯度下降、不同范数下的最速下降和 Newton 法，每种方法都有收敛性分析和数值例子。接着引入自协调性，这是 Newton 法进一步收敛分析所依据的条件，最后给出计算 Newton 步的实现说明。
第10章：Equality constrained minimization（等式约束极小化）
Newton 法被推广到带线性等式约束的问题：先讲消元法和通过对偶求解，再讲带等式约束的 Newton 步和不可行起点 Newton 法。凸凹博弈作为一个应用出现，实现一节讨论 KKT 系统的求解。
第11章：Interior-point methods（内点法）
对数障碍函数与中心路径引出障碍法，随后是收敛分析、寻找可行点的第一阶段方法，以及基于自协调性的复杂度分析。本章还把障碍法推广到广义不等式，介绍原始—对偶内点法，最后讨论线性规划、半定规划和网络速率优化的实现。复杂度一节的小结指出，最坏情形的界远高于实践中观察到的迭代次数。
附录 A–C：Mathematical background；Problems involving two quadratic functions；Numerical linear algebra background（数学背景；涉及两个二次函数的问题；数值线性代数背景）
附录 A 汇集范数、分析、函数、导数和线性代数，并确定记号。附录 B 处理含两个二次函数的优化问题（S 引理和两个对称矩阵的值域），并给出相关强对偶结果的证明。附录 C 涵盖矩阵结构与浮点运算量、分解—求解法、LU、Cholesky 与 LDL^T 分解、分块消元与 Schur 补。
核心概念
第2–3章：凸集；凸函数
- 保持凸性的运算：交集、仿射映射、非负加权和与逐点最大等规则，使读者能把复杂的集合或函数拆成简单部分，从而识别其凸性。
- 广义不等式：由真锥定义的序，使向量与矩阵不等式可以像标量不等式一样处理。
第4章：凸优化问题
- 问题层级：线性、二次、二阶锥、几何和半定规划，是一层比一层一般的凸问题类。
- Pareto 最优性：多准则问题中最优权衡的概念，通过标量化加以研究。
第5章：对偶
- Lagrange 对偶与强对偶：对偶问题给出最优值的下界，Slater 条件保证凸问题中该下界是紧的。
- KKT 条件：把原始可行性、对偶可行性与互补松弛结合起来的最优性条件。
- 灵敏度分析：由对偶变量读出约束变化时最优值的响应。
第6–8章：应用
- 正则化与鲁棒性：在数据拟合与第二个准则之间权衡，或抵御数据中的不确定性。
- 极大似然估计：把参数估计表述为对数似然函数的最大化。
第9–11章：算法
- Newton 步与 Newton 减量：由二次模型得到的下降方向，以及用来衡量进展和停止的量。
- 自协调性：关于三阶导数的条件，支撑 Newton 法的复杂度界。
- 障碍法与中心路径：通过一系列等式约束问题来求解不等式约束问题。
评析
优点
- 以建模能力为组织主线。 前言和第1章指出，凸优化的难处在于识别和建模问题，全书结构随之展开：第2至4章借助集合、函数与问题类的目录训练识别能力，第二部分则加以应用。
- 简短易懂的应用。 第二部分采用统计、几何和数据拟合中的简化案例，篇幅精简，照顾非专业读者。
- 清晰的算法层级。 第三部分从二次问题出发，经带等式约束的 Newton 法到内点法，使每种方法都化为一系列更简单的问题。
- 训练建模的习题。 许多习题要求证明凸性或对问题建模，部分数值习题只需少量编程。
局限
- 并非凸分析的理论专著。 前言说明本书主要不是讲凸分析，也不给出结果的最一般形式；需要这类深度的读者须另读其他教材。
- 只讲选定的算法。 第三部分只限于 Newton 型和内点法，且是简化形式。作者把拟 Newton、共轭梯度、束方法和割平面法列为未涵盖的类别。
- 习题难度不一。 引言说明难度会毫无预告地从简单变到棘手，因此选题需要一些斟酌。
- 要求一定的数学成熟度。 前言要求读者熟悉高等微积分和线性代数，并指出没学过基础分析与概率的读者仍能掌握要点，但未必能跟上每一个论证。
在课程中的定位
Boyd 与 Vandenberghe 是本课程中专讲凸优化的教材。书单中另有两本起点更早：A Gentle Introduction to Optimization 面向学过线性代数入门课的学生，讲线性与整数规划及单纯形法；Chong、Lu 与 Żak 的 An Introduction to Optimization 为高年级本科生讲无约束、线性与约束非线性优化。两者都可在读本书之前打下最优性条件和线性规划的基础，而本书前言正是把高等线性代数与线性规划当作自然的先修内容。
Boyd 与 Vandenberghe 与它们的不同在于一切围绕凸性组织：对偶、锥规划和内点法居于核心，而不是后加的内容。书单中关于高等数学方法以及经济与商业数学的另两本书范围更广，优化只是其中一个主题，因此当项目需要认真地为凸问题建模并求解时，应选用本书。
如何使用本书
本书面向使用优化的研究人员、科学家和工程师，也适合研究生课程。作者称，一个学季的研究生课程可以讲完大部分内容但不深入，一个学期则可以安排更多应用并做一个小项目。前言说明所需背景仅为高等微积分和线性代数；懂一些分析和概率则能跟上每一处论证。
实用的阅读安排：
- 核心： 第1章；第2、3章选读（例子和保持凸性的运算比每个证明更重要）；第4、5章通读。这四章承载建模与对偶的技能。
- 应用： 按兴趣从第6至8章选读，例如第6章讲拟合与正则化，第7章讲统计，第8章讲几何与分类。
- 算法： 按顺序读第9至11章，因为每章都建立在前一章之上。第11.5节的复杂度分析初读时可跳过；该节自己的小结称其主要具有理论意义。
- 附录： 附录 A 用来查记号，实现 Newton 步和 KKT 系统求解前再读附录 C。
先做要求建模或证明凸性的习题，再做数值习题，并把每个建模都写成标准形式。用求解器在小规模实例上检验建模，是检验理解最直接的办法。
版本与来源
本导读依据第一版（Cambridge University Press，2004），采用作者网站上发布的版本，即 2009 年含勘误的第七次印刷。官方免费版本见 https://web.stanford.edu/~boyd/cvxbook/。该版本由前言、完整目录、全部节与小节标题、完整的引言，以及各章的选读段落（包括第11章的复杂度小结和 Newton 步的实现说明）为依据。