凸优化算法

目 录
译者序
前言
致谢
记号
第 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 在