凸优化算法

本书的目标是让读者深入了解凸优化算法。重点是从基本原理推导出凸优化的关键算法，并根据输入长度建立精准的运行时间界限。鉴于这些方法的广泛适用性，一本书不可能展示这些方法对所有方法的应用。本书展示了对各种离散优化和计数问题的快速算法的应用。本书中选择的应用程序旨在说明连续优化和离散优化之间相当令人惊讶的桥梁。

尼什·K.毗湿诺 （Nisheeth K. Vishnoi）　 耶鲁大学计算机科学A. Bartlett Giamatti教授，拥有孟买理工学院计算机科学与工程学士学位和佐治亚理工学院算法、组合学与优化博士学位。他的研究领域包括理论计算机科学、优化和人工智能。他获得过2005年IEEE FOCS最佳论文奖、2006年IBM Research Pat Goldberg纪念奖、2011年印度国家科学院青年科学家奖和2019年ACM FAccT最佳论文奖。他于2019年当选为ACM会士。

适读人群 ：目标受众包括高级本科生、研究生和理论计算机科学、离散优化和机器学习的研究人员。
本书是一本很难得的凸优化算法的新近著作，介绍了凸优化在离散优化和连续优化中的应用，重点介绍了在离散优化算法设计中的应用。可以作为计算机科学、运筹学、离散优化、机器学习以及统计学专业高年级本科生和研究生教材，也可以作为凸优化或者算法设计导论课程的导论教材。

前 言
凸优化研究在凸集上最小化凸函数的问题。凸性及其众多衍生结论已被用来设计许
多凸规划的高效算法。因此，凸优化已广泛应用于科学和工程的多个领域。
近年来，凸优化算法在离散优化和连续优化问题中的应用已经彻底改革了算法设
计。例如，图中的最大流问题、二部图最大匹配以及次模函数最小化问题，通过使用梯
度下降法、镜像下降法、内点法和割平面法等凸优化算法获得了已知最快的算法。出人
意料的是，凸优化算法也被用于设计离散对象，如拟阵的计数问题。同时，凸优化算法
已成为许多现代机器学习应用的核心。更大更复杂的输入实现，对凸优化算法提出了更
高的要求，也推动了凸优化自身的发展。
本书的目标是让读者深入了解凸优化算法。重点是从基本原理推导凸优化的关键算
法，并建立关于输入长度的精确运行时间上界。鉴于这些方法的广泛适用性，单本书不
可能将这些方法的应用全部展示出来。本书展示了适用于各种离散优化和计数问题的快
速算法应用。本书所选的应用旨在说明连续优化和离散优化之间令人惊讶的联系。
本书的结构。本书的主体内容大致分为四个部分：第 3 ～ 5 章介绍了凸性、计算模
型和凸优化的高效性概念以及对偶性；第 6 ～ 8 章分别介绍了梯度下降法、镜像下降法
和乘性权重更新法以及加速梯度下降法等一阶方法；第 9 ～ 11 章介绍了牛顿法和线性
规划的各种内点法；第 12 章和第 13 章介绍了用于线性规划和一般凸规划的椭球法等
割平面方法。第 1 章通过讲述连续优化和离散优化之间的相互作用的简要历史来概述
本书：探索离散问题的快速算法如何推动凸优化算法的改进。
许多章都包含了广泛的应用，从寻找图中的最大流、最小割和完美匹配，到 0—1
多胞形上的线性优化，到次模函数最小化，再到计算组合多胞形上的最大熵分布等。
本书的内容较为完善，第 2 章回顾了微积分、线性代数、几何、动力系统和图论等
知识。本书中的习题不仅在检查理解方面起着重要作用，有时还通过它们引入和建立重
要的方法与概念，例如 Frank-Wolfe 方法、坐标下降法、随机梯度下降法、在线凸优化、
零和博弈的极小极大定理、用于分类的 Winnow 算法、Bandit 优化、共轭梯度法、原
始–对偶内点法和矩阵缩放等。
V
如何使用本书。本书既可作为高年级本科生或低年级研究生的教材，也可作为凸优
化或算法设计导论课程的补充材料。预期读者包括理论计算机科学、离散优化、运筹学、
统计学和机器学习领域的高年级本科生、研究生以及相关领域的研究人员。为了使不同
背景的读者掌握本书内容，本书的写作风格强调直觉，有时甚至以牺牲严谨性为代价。
理论计算机科学或离散优化领域的课程可以包括本书的全部内容。凸优化相关的课
程可以省略离散优化的应用，而根据教师的选择包含相关应用。最后，机器学习的凸优
化导论课程可以包括第 2 章到第 7 章的内容。
凸优化之外？本书还能帮助读者为在凸优化之外的领域工作做好准备，例如，目前
处于形成阶段的非凸优化和测地线凸优化等领域。
非凸优化。凸函数的一个性质是“局部”极小值也是“全局”最小值。因此，凸优
化算法本质上是寻找局部极小值。有趣的是，这种观点已经导致凸优化方法在非凸优化
问题上非常成功，特别是在机器学习中出现的问题。与凸优化问题不同（当然，一些凸
优化也可能是 NP 难），大多数有趣的非凸优化问题都是 NP 难。因此，在许多这些应
用中，我们会定义适当的局部极小值概念，并寻找可以将我们带到这个局部极小值的方
法。因此，凸优化算法对于非凸优化也非常重要，详见 Jain 和 Kar (2017) 的综述。
测地线凸优化。有时候，如果在欧氏空间中引入适当的黎曼度量并重新定义相对于
由此度量引发的“直线”（测地线）的凸性，那么原来在欧氏空间中非凸的函数可能会
变成凸函数。这样的函数称为测地线凸函数，出现在关于黎曼流形（如矩阵李群）上的
优化问题中，详见 Vishnoi (2018) 的综述。目前，关于测地线凸优化高效算法理论仍在
建设之中，Bürgisser 等 (2019) 的文献介绍了一些最新进展。

目 录
译者序
前言
致谢
记号
第 1 章 连续优化与离散优化的关联　 1
1.1 一个例子：最大流问题 1
1.2 线性规划6
1.3 基于内点法的快速精确算法　 9
1.4 简单线性规划之外的椭球法 10
第 2 章 预备知识 13
2.1 导数、梯度和黑塞矩阵　 13
2.2 微积分基本定理 14
2.3 泰勒近似 15
2.4 线性代数、矩阵和特征值 16
2.5 柯西–施瓦茨不等式 18
2.6 范数　 19
2.7 欧几里得拓扑 20
2.8 动力系统 21
2.9 图　 21
2.9.1 图上的结构 22
2.9.2 图的关联矩阵 23
2.9.3 与图相关联的多胞形　 24
习题 24
注记 28
第 3 章 凸性　 29
3.1 凸集　 29
3.2 凸函数　 30
3.3 凸性的作用 35
3.3.1 凸集的分离超平面和支撑超
平面　 35
3.3.2 次梯度的存在性37
3.3.3 凸函数的局部最优值是全局
最优值　 38
习题 39
注记 41
第 4 章 凸优化与高效性 42
4.1 凸规划　 42
4.2 计算模型 44
4.3 凸集的从属问题 45
4.4 优化问题的求解 50
4.5 凸优化的多项式时间概念 53
习题 55
注记 57
第 5 章 对偶性与最优性 58
5.1 Lagrange 对偶　 58
5.2 共轭函数 63
X
5.3 KKT 最优条件 65
5.4 Slater 条件下的强对偶性证明　 66
习题 67
注记 70
第 6 章 梯度下降法 71
6.1 预备　 71
6.2 梯度下降法概论 71
6.2.1 为什么要沿梯度下降　 72
6.2.2 关于函数、梯度和初始点的
假设　 73
6.3 梯度 Lipschitz 连续时的分析　 75
6.3.1 下界　 79
6.3.2 约束优化的投影梯度下
降法　 80
6.4 应用：最大流问题　 81
6.4.1 s-t 最大流问题　 81
6.4.2 主要结果 82
6.4.3 建模成无约束凸规划　 82
6.4.4 梯度下降法中的步骤　 84
6.4.5 运行时间分析 85
6.4.6 处理近似解 86
习题 86
注记 90
第 7 章 镜像下降法和乘性权重更
新法　 92
7.1 Lipschitz 梯度条件之外 92
7.2 局部优化原理与正则化项 93
7.3 指数梯度下降法 96
7.3.1 指数梯度下降法的主要
定理　 99
7.3.2 Bregman 散度的性质 99
7.3.3 指数梯度下降法的收敛性
证明 101
7.4 镜像下降法　 103
7.4.1 指数梯度下降法的推广和近
端视角 103
7.4.2 镜像下降法的算法表述 104
7.4.3 收敛性证明　 105
7.5 乘性权重更新法 107
7.6 应用：二部图的完美匹配　108
7.6.1 主要结果　 109
7.6.2 算法 110
7.6.3 分析 110
习题　 113
注记　 122
第 8 章 加速梯度下降法 123
8.1 预备 123
8.2 加速梯度下降法的主要结果　 124
8.3 证明策略：估计序列 124
8.4 估计序列的构造 126
8.4.1 步骤 1：迭代的构造 126
8.4.2 步骤 2：确保下界条件 128
8.4.3 步骤 3：确保上界和 yt 的
动态更新　 129
8.4.4 步骤 4：确保条件（2）和
xt 的动态更新 131
8.5 算法及其分析　 131
8.6 强凸光滑函数的一种算法　 133
8.7 应用：线性方程组 134
习题　 136
注记　 138
XI
第 9 章 牛顿法139
9.1 求一元函数的根 139
9.1.1 迭代规则的推导 139
9.1.2 二次收敛　 141
9.2 多元函数的牛顿法 142
9.3 无约束优化的牛顿法 143
9.3.1 从优化到求根　 143
9.3.2 作为二阶方法的牛顿法 144
9.4 分析初探　 145
9.4.1 欧氏范数意义下的收敛
问题 146
9.4.2 牛顿法的仿射不变性 148
9.5 视为最速下降的牛顿法 148
9.5.1 局部范数意义下的最速下
降法 150
9.5.2 局部范数是黎曼度量 152
9.6 基于局部范数的分析 152
9.6.1 一个新的势函数 153
9.6.2 局部范数的界　 154
9.6.3 局部范数收敛性的证明 155
9.7 基于欧氏范数的分析 158
习题　 159
注记　 161
第 10 章 线性规划的内点法　 162
10.1 线性规划 162
10.2 利用障碍函数求解约束优化
问题 163
10.3 对数障碍函数 164
10.4 中心路径 165
10.5 线性规划的路径跟踪算法 166
10.6 路径跟踪算法的分析　 169
10.6.1 终止条件 172
10.6.2 初始化 176
10.6.3 定理 10.10的证明 182
习题　 183
注记　 188
第 11 章 内点法的变体与自和谐性　 189
11.1 最小成本流问题　 189
11.1.1 是否为基于线性规划的快
速算法 190
11.1.2 路径跟踪内点法的问题 190
11.1.3 剔除全维性的线性规划 191
11.2 一种求解线性规划标准型的内
点法 192
11.2.1 有等式约束的牛顿法　 193
11.2.2 在子空间上定义黑塞矩阵
和梯度 194
11.2.3 在