目录
第一章最优化简介1
1.1 最优化问题概括. . . . . . . . . . 1
1.1.1 最优化问题的一般形式. . . . . . .. 1
1.1.2 最优化问题的类型与应用背景. . . . . . . . . . . . . . 2
1.2 实例：稀疏优化. . . . . . . . 3
1.3 实例：低秩矩阵恢复. . . . . 7
1.4 实例：深度学习. . . . . . . 9
1.4.1 多层感知机. . . . . . . 9
1.4.2 卷积神经网络. . . . .. . . 10
1.5 最优化的基本概念. . . . .. . . 13
1.5.1 连续和离散优化问题. . .. . . . . 14
1.5.2 无约束和约束优化问题. . . . .. . . 14
1.5.3 随机和确定性优化问题. . . . . . . . 15
1.5.4 线性和非线性规划问题. . . . . . 15
1.5.5 凸和非凸优化问题. . . .. . . 16
1.5.6 全局和局部最优解. . . . . . 16
1.5.7 优化算法. . . . . 17
1.6 总结. . . . . . 22
习题1 . . . . . 23
第二章基础知识25
2.1 范数. . . . . 25
2.1.1 向量范数. .. . 25
2.1.2 矩阵范数. . . . 26

2.1.3 矩阵内积. .. . 27
2.2 导数. . . .. . . . . 28
2.2.1 梯度与海瑟矩阵. . . . . . . 28
2.2.2 矩阵变量函数的导数. . . . . .. . 32
2.2.3 自动微分. . . .. . . . . . 34
2.3 广义实值函数. . . . . . . 36
2.3.1 适当函数. .. . 37
2.3.2 闭函数. . .. . . 37
2.4 凸集. . . . . . . . . 40
2.4.1 凸集的相关定义. . .. 40
2.4.2 重要的凸集.. 43
2.4.3 保凸的运算. . .. . . . 45
2.4.4 分离超平面定理. .. . . 46
2.5 凸函数. . . . . . .. . 47
2.5.1 凸函数的定义. . .. . 48
2.5.2 凸函数判定定理. . . 49
2.5.3 保凸的运算. .. . . 55
2.5.4 凸函数的性质. . . . 58
2.6 共轭函数. . . . 60
2.6.1 共轭函数的定义和例子. . . . . . . . . . . . . . . . . . 60
2.6.2 二次共轭函数. . . . . . . . 62
2.7 次梯度. . . . . . . . 63
2.7.1 次梯度的定义. .. . . 63
2.7.2 次梯度的性质. . .. . . . 66
2.7.3 凸函数的方向导数. . . . . . 68
2.7.4 次梯度的计算规则. . .. . 70
2.8 总结. . . . .. . . . . 77
习题2 . . . . . . . . . . . 78
第三章优化建模81
3.1 建模技术. . . . . . . . . . 82
3.1.1 目标函数的设计. . . . . . 82
3.1.2 约束的设计. . .. . . 86
3.2 回归分析. . . .. . . 88

3.2.1 概述. . .. . 88
3.2.2 线性回归模型. . . . . . . 89
3.2.3 正则化线性回归模型. . . . . 90
3.3 逻辑回归. . . . . . 93
3.4 支持向量机. . . . . . 95
3.5 概率图模型. .. . . 97
3.6 相位恢复. . .. . . 100
3.7 主成分分析. . . . 103
3.8 矩阵分离问题. . . . . . 105
3.9 字典学习. . . . . . 106
3.10 K-均值聚类. . .. . 108
3.11 图像处理中的全变差模型. . . . . 110
3.12 小波模型. . . .. . . . 113
3.13 强化学习. . . . . . 115
3.14 总结. . . . . . . . . 118
习题3 . . . . . . . . 119
第四章典型优化问题123
4.1 线性规划. . . . . . . . . 123
4.1.1 基本形式和应用背景. . . . 123
4.1.2 应用举例. . . . . . . . 124
4.2 最小二乘问题. . . . . . . 127
4.2.1 基本形式和应用背景. .. 127
4.2.2 应用举例. . . .. . . . . 127
4.3 复合优化问题. . . . .. . . . 132
4.3.1 基本形式和应用背景. . . . . 132
4.3.2 应用举例. . . . . . 134
4.4 随机优化问题. . . . . . . . . 136
4.4.1 基本形式和应用背景. .. . . 136
4.4.2 应用举例. . . . . . . . . . 136
4.5 半定规划. . . . . . . . . . . . . . . . 138
4.5.1 基本形式和应用背景. . . . . . 138
4.5.2 应用举例. . . . . . . . . 139
4.6 矩阵优化. . . . . . . . . 142

4.6.1
基本形式和应用背景 . . . . 142
4.6.2
应用举例 . . .. . . 144
4.7
整数规划 . . . . .. . . . . . 147
4.7.1
基本形式和应用背景 . . . .. 147
4.7.2
应用举例 . . . . . . 147
4.8
典型优化算法软件介绍 . . .. . . . . 150
4.9
优化模型语言 . . .. . . . . 151
4.9.1 CVX . . . . . . . 151
4.9.2 AMPL . .. . . . 152
4.10 总结 . . . . . . . . . 153
习题 4 . . . . . . . . 154
第五章 最优性理论
159
5.1
最优化问题解的存在性 . . . . . . . . 159
5.2
无约束可微问题的最优性理论 . . .. . 162
5.2.1 一阶最优性条件
. . . . . .. 162
5.2.2
二阶最优性条件
. . . . . .. . . 163
5.2.3
实例 . . . . . . . . . . 165
5.3
无约束不可微问题的最优性理论 . .. . 166
5.3.1
凸优化问题一阶充要条件 . . . . . . 166
5.3.2
复合优化问题的一阶必要条件 . . . . . . . 167
*5.3.3 非光滑非凸问题的最优性条件 . . . . . . . . 168
5.3.4
实例 . . . .. . 170
5.4
对偶理论 . . .. . . . 171
5.4.1
拉格朗日函数与对偶问题 . . . . . . . . . . . . . . . . 171
5.4.2
带广义不等式约束优化问题的对偶 . . . . . . . . . . . 174
5.4.3
实例 . . . . . . .. . . . 176
5.5
一般约束优化问题的最优性理论 . . . . . . 182
5.5.1
一阶最优性条件
. . . . . . . . . . . . . . . . . . . . . 182
5.5.2
二阶最优性条件
. . . . . . . . . . . 191
5.6
带约束凸优化问题的最优性理论 . . . . . . . . . . . . . . . . . 193
5.6.1 Slater 约束品性与强对偶原理 . . . . . . . . . . . . . . 194
5.6.2
一阶充要条件 . . . . . . . . . . . . . . . . . . . . . . . 197
*5.6.3 一阶充要条件：必要性的证明 . . . . . . . . . . . . . . 198

5.7
约束优化最优性理论应用实例 . . . . . . . . . . . . . . . . . . 205
5.7.1
仿射空间的投影问题 . . . . . . . . . 205
5.7.2
线性规划问题 . . . . . .. . . . . . . . 206
5.7.3
基追踪 . . . . . . . . . . . . . 207
5.7.4
最大割问题的半定规划松弛及其非凸分解模型 . . . . . 209
5.8
总结 . . . . . . .. . . . 211
习题 5 . . . . . . . . . . . 212
第六章 无约束优化算法
217
6.1
线搜索方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.1.1
线搜索准则 . . . . . . . . . . . . . . . . . . . . . . . . 218
6.1.2
线搜索算法 . . . . . . . . . . . . . . . . . . . . . . . . 223
6.1.3
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 224
6.2
梯度类算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
6.2.1
梯度下降法 . . . . . . . . . . . . . . . . . . . . . . . . 227
6.2.2 Barzilai-Borwein 方法 . . . . . . . . . . . . . . . . . . 231
6.2.3
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.3
次梯度算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
6.3.1
次梯度算法结构
. . . . . . . . . . . . . . . . . . . . . 239
6.3.2
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 239
6.3.3
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 243
6.4
牛顿类算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
6.4.1
经典牛顿法 . . . . . . . . . . . . . . . . . . . . . . . . 247
6.4.2
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 247
6.4.3
修正牛顿法 . . . . . . . . . . . . . . . . . . . . . . . . 249
6.4.4
非精确牛顿法 . . . . . . . . . . . . . . . . . . . . . . . 251
6.4.5
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 252
6.5
拟牛顿类算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
6.5.1
割线方程 . . . . . . . . . . . . . . . . . . . . . . . . . 255
6.5.2
拟牛顿矩阵更新方式 . . . . . . . . . . . . . . . . . . . 257
6.5.3
拟牛顿法的全局收敛性 . . . . . . . . . . . . . . . . . . 260
6.5.4
有限内存 BFGS 方法
. . . . . . . . . . . . . . . . . . 262
6.5.5
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 267
6.6
信赖域算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

6.6.1
信赖域算法框架
. . . . . . . . . . . . . . . . . . . . . 269
6.6.2
信赖域子问题求解 . . . . . . . . . . . . . . . . . . . . 272
6.6.3
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 278
6.6.4
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 282
6.7
非线性最小二乘问题算法 . . . . . . . . . . . . . . . . . . . . 282
6.7.1
非线性最小二乘问题 . . . . . . . . . . . . . . . . . . . 284
6.7.2
高斯 – 牛顿算法 . . . . . . . . . . . . . . . . . . . . . 284
6.7.3 Levenberg-Marquardt 方法 . . . . . . . . . . . . . . . 288
6.7.4
大残量问题的拟牛顿法 . . . . . . . . . . . . . . . . . . 291
6.7.5
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 292
6.8
总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
习题 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
第七章 约束优化算法
301
7.1
罚函数法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
7.1.1
等式约束的二次罚函数法 . . . . . . . . . . . . . . . . 301
7.1.2
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 304
7.1.3
一般约束问题的二次罚函数法 . . . . . . . . . . . . . . 307
7.1.4
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 309
7.1.5
其他类型的罚函数法 . . . . . . . . . . . . . . . . . . . 312
7.2
增广拉格朗日函数法 . . . . . . . . . . . . . . . . . . . . . . . 315
7.2.1
等式约束优化问题的增广拉格朗日函数法 . . . . . . . 315
7.2.2
一般约束优化问题的增广拉格朗日函数法 . . . . . . . 321
7.2.3
凸优化问题的增广拉格朗日函数法 . . . . . . . . . . . 323
7.2.4
基追踪问题的增广拉格朗日函数法 . . . . . . . . . . . 326
7.2.5
半定规划问题的增广拉格朗日函数法 . . . . . . . . . . 334
7.3
线性规划内点法 . . . . . . . . . . . . . . . . . . . . . . . . . . 336
7.3.1
原始 – 对偶算法 . . . . . . . . . . . . . . . . . . . . . 337
7.3.2
路径追踪算法 . . . . . . . . . . . . . . . . . . . . . . . 339
7.4
流形约束优化算法 . . . . . . . . . . . . . . . . . . . . . . . . 342
7.4.1
流形的基本概念
. . . . . . . . . . . . . . . . . . . . . 343
7.4.2
典型流形介绍 . . . . . . . . . . . . . . . . . . . . . . . 347
7.4.3
最优性条件 . . . . . . . . . . . . . . . . . . . . . . . . 354
7.4.4
收缩算子以及平行移动 . . . . . . . . . . . . . . . . . . 356

7.4.5
一阶优化方法 . . . . . . . . . . . . . . . . . . . . . . . 359
7.4.6
二阶优化算法 . . . . . . . . . . . . . . . . . . . . . . . 361
7.4.7
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 364
7.4.8
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 367
7.5
总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
习题 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
第八章 复合优化算法
379
8.1
近似点梯度法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
8.1.1
邻近算子 . . . . . . . . . . . . . . . . . . . . . . . . . 380
8.1.2
近似点梯度法 . . . . . . . . . . . . . . . . . . . . . . . 385
8.1.3
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 387
8.1.4
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 389
*8.1.5 非凸函数的邻近算子与近似点梯度法 . . . . . . . . . . 393
8.2 Nesterov 加速算法 . . . . . . . . . . . . . . . . . . . . . . . . 395
8.2.1 FISTA 算法 . . . . . . . . . . . . . . . . . . . . . . . . 395
8.2.2
其他加速算法 . . . . . . . . . . . . . . . . . . . . . . . 400
8.2.3
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 402
8.2.4
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 405
8.3
近似点算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
8.3.1
近似点算法 . . . . . . . . . . . . . . . . . . . . . . . . 410
8.3.2
与增广拉格朗日函数法的关系 . . . . . . . . . . . . . . 411
8.3.3
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 413
8.3.4
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 418
8.3.5 Moreau-Yosida 正则化 . . . . . . . . . . . . . . . . . . 420
8.4
分块坐标下降法 . . . . . . . . . . . . . . . . . . . . . . . . . . 423
8.4.1
问题描述 . . . . . . . . . . . . . . . . . . . . . . . . . 424
8.4.2
算法结构 . . . . . . . . . . . . . . . . . . . . . . . . . 426
8.4.3
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 429
*8.4.4 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 436
8.5
对偶算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
8.5.1
对偶近似点梯度法 . . . . . . . . . . . . . . . . . . . . 449
8.5.2
原始 – 对偶混合梯度算法 . . . . . . . . . . . . . . . . 454
8.5.3
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 457

8.5.4
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 461
8.6
交替方向乘子法 . . . . . . . . . . . . . . . . . . . . . . . . . . 467
8.6.1
交替方向乘子法
. . . . . . . . . . . . . . . . . . . . . 467
8.6.2 Douglas-Rachford Splitting 算法 . . . . . . . . . . . . 473
8.6.3
常见变形和技巧
. . . . . . . . . . . . . . . . . . . . . 477
8.6.4
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 480
*8.6.5 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 492
8.7
随机优化算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
8.7.1
随机梯度下降算法 . . . . . . . . . . . . . . . . . . . . 500
8.7.2
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 507
8.7.3
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 510
8.7.4
方差减小技术 . . . . . . . . . . . . . . . . . . . . . . . 519
8.8
半光滑牛顿算法 . . . . . . . . . . . . . . . . . . . . . . . . . . 526
8.8.1
半光滑性介绍 . . . . . . . . . . . . . . . . . . . . . . . 526
8.8.2
半光滑牛顿算法
. . . . . . . . . . . . . . . . . . . . . 535
8.8.3
应用举例 . . . . . . . . . . . . . . . . . . . . . . . . . 541
8.8.4
收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . 550
8.9
总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
习题 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
附录 A 符号表
561
附录 B 数学基础
565
B.1 线性代数基础 . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
B.1.1 矩阵内积与迹 . . . . . . . . . . . . . . . . . . . . . . . 565
B.1.2 正交矩阵与（半）正定矩阵 . . . . . . . . . . . . . . . 565
B.1.3 矩阵的秩 . . . . . . . . . . . . . . . . . . . . . . . . . 566
B.1.4 像空间和零空间
. . . . . . . . . . . . . . . . . . . . . 566
B.1.5 行列式 . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
B.1.6 特征值与特征向量 . . . . . . . . . . . . . . . . . . . . 567
B.1.7 广义逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
B.1.8 Sherman-Morrison-Woodbury 公式 . . . . . . . . . . . 569
B.1.9 Schur 补 . . . . . . . . . . . . . . . . . . . . . . . . . . 570
B.2 数值代数基础 . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

B.2.1 解线性方程组 . . . . . . . . . . . . . . . . . . . . . . . 571
B.2.2 系数矩阵为特殊矩阵的方程组解法 . . . . . . . . . . . 574
B.2.3 特征值分解与奇异值分解 . . . . . . . . . . . . . . . . 576
B.2.4 数值代数软件 . . . . . . . . . . . . . . . . . . . . . . . 579
B.3 概率基础 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
B.3.1 概率空间 . . . . . . . . . . . . . . . . . . . . . . . . . 584
B.3.2 随机变量 . . . . . . . . . . . . . . . . . . . . . . . . . 585
B.3.3 条件期望 . . . . . . . . . . . . . . . . . . . . . . . . . 591
B.3.4 随机变量的收敛性 . . . . . . . . . . . . . . . . . . . . 595
B.3.5 随机过程 . . . . . . . . . . . . . . . . . . . . . . . . . 596
B.3.6 概率不等式 . . . . . . . . . . . . . . . . . . . . . . . . 598
参考文献
601
索引
623