目录

第1 引言 1

1.1 最优化为什么重要 1

1.2 最优化问题示例 1

1.3 优化的基本概念与思想 2

1.3.1 优化问题的一般形式 2

1.3.2 最优化的基本概念 3

1.3.3 迭代算法与收敛速率 4

1.3.4 优化的基本思想 7

第2 章基础知识 8

2.1 线性代数 8

2.1.1 线性空间与线性映射 8

2.1.2 内积与范数 12

2.1.3 线性方程组与矩阵 18

2.1.4 矩阵的基本运算与性质 19

2.1.5 矩阵的特征分解 21

2.2 多元微积分基础 28

2.2.1 多元可微函数 28

2.2.2 可微映射与微分的链式法则 32

2.2.3 矩阵函数的梯度 34

2.2.4 微分中值定理与Taylor 公式 37

2.2.5 切向量与切空间 39

第2 章练习 41

第3 章凸集与凸函数 43

3.1 凸集 43

3.2 凸函数 46

3.2.1 凸集与凸函数的关联 48

3.2.2 凸函数的性质 49

3.2.3 凸函数的判定条件 50

3.2.4 强凸函数及其性质 55

第3 章练习 56

第4 章最优性条件 58

4.1 极小值点的存在性条件 58

4.2 无约束优化的最优性条件 58

4.2.1 一阶必要条件 59

4.2.2 二阶最优性条件 60

4.2.3 不可微函数的最优性条件 62

4.3 等式约束优化的最优性条件 63

4.3.1 切空间 64

4.3.2 拉格朗日乘子与一阶条件 65

4.3.3 二阶条件 68

4.4 一般约束优化的最优性条件 72

4.4.1 可行方向 73

4.4.2 KKT 条件 75

4.4.3 二阶最优性条件 78

4.5 对偶理论 80

4.5.1 拉格朗日对偶 80

4.5.2 约束规范条件与强对偶 82

4.5.3 凸规划问题 84

第4 章练习 85

第5 章机器学习中的优化问题与模型 88

5.1 机器学习的基本概念 88

5.2 参数估计 89

5.2.1 最大似然原理 90

5.2.2 最大后验估计 94

5.3 线性模型 94

5.3.1 线性回归 94

5.3.2 引入正则化 95

5.3.3 从最大似然估计到最小二乘问题 96

5.3.4 线性分类器 98

5.4 数据降维与主成分分析 99

5.4.1 投影 99

5.4.2 总体近似误差最小化 101

5.4.3 k-维特征子空间 103

5.4.4 幂迭代方法 107

5.4.5 矩阵近似 108

5.5 支持向量机 111

5.5.1 线性支持向量机 111

5.5.2 最优性条件与对偶 112

5.5.3 非线性特征映射与核函数 114

5.5.4 软边距SVM  114

5.6 神经网络 116

5.6.1 层次化特征学习 116

5.6.2 计算图与自动微分 118

第5 章练习 120

第6 章无约束优化算法 122

6.1 线搜索 122

6.1.1 非精确线搜索准则 123

6.1.2 线搜索方法 125

6.1.3 线搜索算法的全局收敛性 127

6.2 梯度下降法 130

6.2.1 最速下降方向 130

6.2.2 梯度法在二次函数上的收敛速率 131

6.2.3 梯度下降法的收敛性分析 134

6.3 牛顿法 142

6.3.1 非线性方程的零点 142

6.3.2 牛顿法相关概念 143

6.3.3 牛顿法的收敛性分析 146

6.3.4 修正牛顿法 149

6.4 共轭梯度法 150

6.4.1 共轭方向 151

6.4.2 子空间扩展定理 152

6.4.3 共轭梯度法 154

6.4.4 非线性共轭梯度法 157

6.4.5 共轭梯度法的性质 157

6.5 拟牛顿法 159

6.5.1 截线法 159

6.5.2 拟牛顿法的推导 160

6.5.3 拟牛顿法的性质和收敛性 163

6.5.4 非单调下降步长：BB 方法 165

6.5.5 有限存储的L-BFGS  166

6.6 信赖域方法 169

6.6.1 信赖域 169

6.6.2 信赖域子问题的求解 169

6.6.3 信赖域半径的确定 171

6.7 非线性最小二乘问题算法 171

6.7.1 高斯-牛顿法 172

6.7.2 LMF 方法 173

第6 章练习 174

第7 章约束优化算法 177

7.1 罚函数法 177

7.1.1 外点罚函数法 177

7.1.2 内点罚函数法 181

7.2 增广拉格朗日函数法 182

7.2.1 等式约束的增广拉格朗日函数法 182

7.2.2 不等式约束的增广拉格朗日函数法 183

7.3 投影梯度法 185

7.3.1 投影梯度法的收敛性 187

7.3.2 向标准单纯形投影 190

第7 章练习 193

第8 章机器学习中的优化方法 194

8.1 随机优化方法 194

8.1.1 随机梯度下降 195

8.1.2 自适应优化方法 198

8.2 随机优化中的方差缩减 200

8.3 近端梯度法 206

8.4 Nesterov 加速梯度法 209

8.5 坐标下降法 211

8.5.1 随机坐标下降法 211

8.5.2 分块坐标下降法 213

8.6 交替方向乘子法 215

8.7 零阶优化方法 217

8.7.1 高斯平滑与梯度近似 217

8.7.2 演化策略 220

参考文献 224