第1章 绪论 1
1.1最优化方法的发展历史 1
1.2最优化问题举例 3
1.3最优化问题的数学模型及相关概念 7
1.3.1最优化问题的数学模型及三要素 7
1.3.2可行点、非可行点、可行域 7
1.3.3其他形式优化问题的转化 8
1.4最优化方法的分类 8
1.5最优化方法的算法基本结构 9
1.6最优化算法的评价指标 10
第2章 无约束优化问题的基本概念与理论 11
2.1梯度信息 11
2.1.1梯度向量 11
2.1.2 Hesse矩阵 11
2.1.3 Hesse矩阵的正定、半正定、负定、半负定、不定性质及判定 12
2.1.4梯度向量与Hesse矩阵的关系 13
2.2 Taylor展开式与函数逼近 13
2.2.1一维函数的Taylor展开式 13
2.2.2多维函数的Taylor展开式 13
2.2.3多维函数的一阶与二阶Taylor展开式 14
2.3极值点与稳定点 14
2.3.1极值点 14
2.3.2稳定点 15
2.4凸集、凸函数与凸优化 16
2.4.1凸集 16
2.4.2凸函数和凹函数 16
2.4.3凸函数的相关性质 17
2.4.4函数凹凸性的判定 18
2.4.5凸优化问题的定义 21
2.4.6凸优化问题的判定准则 21
2.5无约束优化问题的最优性条件 22
2.5.1一阶必要条件 22
2.5.2二阶必要条件 23
2.5.3二阶充分条件 23
2.6下降方向 24
习题 24
第3章 精确一维搜索方法 25
3.1精确一维搜索介绍 25
3.1.1一维搜索在最优化方法中的地位 25
3.1.2精确一维搜索的问题描述与基本原理 25
3.1.3区间消去思想 25
3.1.4精确一维搜索方法的分类 26
3.2对分搜索法 27
3.2.1对分搜索法的原理 27
3.2.2对分搜索法的实现难点 27
3.2.3对分搜索法的计算步骤 27
3.2.4对分搜索法的流程图 28
3.2.5对分搜索法的MATLAB程序 29
3.2.6实例测试 31
3.3三点等间隔搜索法 33
3.3.1等间隔搜索原理 33
3.3.2三点等间隔搜索法的原理 34
3.3.3三点等间隔搜索法的计算步骤 34
3.3.4三点等间隔搜索法的流程图 35
3.3.5三点等间隔搜索法的MATLAB程序 35
3.3.6实例测试 38
3.4 Fibonacci搜索法 39
3.4.1对称区间消去原理 39
3.4.2对称区间消去法的缩减率特点 40
3.4.3 Fibonacci搜索法的原理 40
3.4.4 Fibonacci搜索法的实现难点 41
3.4.5 Fibonacci搜索法的计算步骤 42
3.4.6 Fibonacci搜索法的流程图 42
3.4.7 Fibonacci搜索法的MATLAB程序 43
3.4.8实例测试 46
3.5黄金分割法 48
3.5.1黄金分割法的基本原理 48
3.5.2黄金分割法与Fibonacci搜索法的关系 48
3.5.3黄金分割法的计算步骤 49
3.5.4黄金分割法的流程图 50
3.5.5黄金分割法的MATLAB程序 51
3.5.6实例测试 52
3.6三点二次插值法 54
3.6.1三点二次插值法的原理 54
3.6.2四种不同的区间消去情况 55
3.6.3三点二次插值法的计算步骤 56
3.6.4三点二次插值法的流程图 56
3.6.5三点二次插值法的MATLAB程序 57
3.6.6实例测试 60
习题 61
第4章 非精确一维搜索方法 62
4.1非精确一维搜索介绍 62
4.1.1非精确一维搜索方法的优势 62
4.1.2非精确一维搜索的问题描述与基本原理 62
4.1.3更新步长区间的两点抛物线插值方法 63
4.2 Armijo非精确搜索方法 63
4.2.1 Armijo条件 63
4.2.2 Armijo非精确搜索方法的计算步骤 64
4.2.3 Armijo非精确搜索方法的流程图 64
4.2.4 Armijo非精确搜索方法的MATLAB程序 65
4.2.5实例测试 67
4.3 Goldstein非精确搜索方法 69
4.3.1 Goldstein条件 69
4.3.2 Goldstein非精确搜索方法的计算步骤 70
4.3.3 Goldstein非精确搜索方法的流程图 71
4.3.4 Goldstein非精确搜索方法的MATLAB程序 72
4.3.5实例测试 74
4.4 Wolfe非精确搜索方法 75
4.4.1 Wolfe条件 75
4.4.2 Wolfe非精确搜索方法的计算步骤 76
4.4.3 Wolfe非精确搜索方法的流程图 77
4.4.4 Wolfe非精确搜索方法的MATLAB程序 77
4.4.5实例测试 80
4.5强Wolfe非精确搜索方法 81
4.5.1强Wolfe条件 81
4.5.2强Wolfe非精确搜索方法的计算步骤 82
4.5.3强Wolfe非精确搜索方法的流程图 83
4.5.4强Wolfe非精确搜索方法的MATLAB程序 83
4.5.5实例测试 86
习题 88
第5章 基本多维无约束优化方法 89
5.1多维无约束优化方法介绍 89
5.1.1多维无约束优化方法的地位 89
5.1.2多维无约束优化问题的描述 89
5.1.3多维无约束优化的方法分类 89
5.1.4算法的收敛准则 90
5.2最速下降法 90
5.2.1最速下降法的原理 90
5.2.2最速下降法的特点 91
5.2.3最速下降法的计算步骤 92
5.2.4最速下降法的流程图 93
5.2.5最速下降法的MATLAB程序 93
5.2.6实例测试 95
5.3牛顿法 97
5.3.1牛顿法的原理 97
5.3.2牛顿方向的特点 97
5.3.3牛顿法的实现难点 98
5.3.4牛顿法的计算步骤 99
5.3.5牛顿法的流程图 99
5.3.6牛顿法的MATLAB程序 100
5.3.7实例测试 101
5.4高斯牛顿法 104
5.4.1高斯牛顿法的原理 104
5.4.2高斯牛顿法的实现难点 105
5.4.3高斯牛顿法的计算步骤 105
5.4.4高斯牛顿法的流程图 106
5.4.5高斯牛顿法的MATLAB程序 106
5.4.6实例测试 108
习题 109
第6章 高级多维无约束优化方法 111
6.1共轭梯度法 111
6.1.1向量组共轭的相关概念与定理 111
6.1.2共轭方向法的基本原理 112
6.1.3共轭梯度法的基本原理 113
6.1.4共轭梯度法的性质 114
6.1.5共轭梯度法的计算步骤 114
6.1.6共轭梯度法的流程图 115
6.1.7 Dai-Yuan共轭梯度法的MATLAB程序 116
6.1.8 Hager-Zhang共轭梯度法的MATLAB程序 117
6.1.9实例测试 119
6.2拟牛顿法 121
6.2.1拟牛顿法的基本思想 121
6.2.2校正矩阵的构造方法 122
6.2.3 DFP校正公式 123
6.2.4 DFP拟牛顿法的性质 123
6.2.5 Sherman-Morrison公式及BFGS校正公式 124
6.2.6 DFP/BFGS拟牛顿法的计算步骤 125
6.2.7 DFP/BFGS拟牛顿法的流程图 125
6.2.8 DFP拟牛顿法的MATLAB程序 126
6.2.9 BFGS拟牛顿法的MATLAB程序 128
6.2.10实例测试 130
习题 132
第7章 带约束优化问题的基本概念与理论 133
7.1约束的分类及对求解的影响 133
7.1.1带约束优化问题的定义 133
7.1.2约束的分类 133
7.1.3约束对可行域的影响 134
7.1.4带不等式约束优化问题的可行方向 135
7.2带约束优化问题的最优性条件 137
7.2.1几个重要概念 137
7.2.2一阶必要条件 137
7.2.3 KKT条件的几何解释 139
7.2.4 KKT条件的拉格朗日函数表达形式 140
7.2.5二阶必要条件 140
7.2.6二阶充分条件 141
7.2.7对比无约束优化问题的最优性条件 141
7.3凸优化问题的性质 142
7.4凸优化问题的对偶性 145
7.4.1凸优化问题的拉格朗日对偶问题 145
7.4.2原问题与对偶问题之间的理论联系 147
7.5带约束优化问题的算法思想 148
7.5.1代入消去思想 148
7.5.2积极集思想 149
7.5.3内点逼近思想 150
7.5.4序列子问题逼近思想 150
习题 150
第8章 线性规划问题的单纯形法 152
8.1线性规划问题的模型及基本理论 152
8.1.1线性规划在优化中的地位 152
8.1.2线性规划问题的标准形式及转换方法 152
8.1.3标准型线性规划问题解的相关概念 153
8.1.4线性规划问题解的基本定理 154
8.1.5线性规划问题最优解的可能情况 154
8.1.6线性规划问题的图解法 155
8.1.7线性规划问题的穷举法 155
8.1.8线性规划问题的单纯形法 156
8.1.9单纯形法的难点 156
8.2决策变量非负线性规划问题的单纯形法 157
8.2.1问题形式 157
8.2.2决策变量非负线性规划问题单纯形法的基本原理 157
8.2.3通过两阶段法获取初始可行基 159
8.2.4两阶段改进型单纯形法的实现难点 160
8.2.5两阶段改进型单纯形法的计算步骤 162
8.2.6两阶段改进型单纯形法的流程图 163
8.2.7两阶段改进型单纯形法的MATLAB程序 164
8.2.8实例测试 173
8.3决策变量有界线性规划问题的单纯形法 176
8.3.1决策变量有界的标准型线性规划问题及转换方法 176
8.3.2决策变量有界问题的解的相关概念 177
8.3.3问题形式 177
8.3.4决策变量有界问题单纯形法针对的基本原理 178
8.3.5通过两阶段法获取初始可行基 182
8.3.6两阶段改进型单纯形法的计算步骤 183
8.3.7两阶段改进型单纯形法的流程图 184
8.3.8实例测试 185
8.4对单纯形法的进一步讨论 188
8.4.1两类标准型线性规划问题的关系 188
8.4.2线性规划问题的退化情况 188
8.4.3单纯形法的收敛性 189
8.4.4从凸优化的角度看线性规划问题 189
8.4.5从积极集思想看单纯形法 190
8.4.6实现单纯形法时的其他注意事项 190
习题 190
第9章 线性规划问题的内点法 192
9.1内点法的相关概念与基本原理 192
9.1.1内点法与单纯形法 192
9.1.2线性规划问题的对偶问题与对偶间隔 192
9.1.3内点与中心路径 194
9.1.4内点法的基本原理 196
9.2原-对偶可行路径跟踪法 196
9.2.1问题形式 196
9.2.2原-对偶可行路径跟踪法的基本原理 197
9.2.3原-对偶可行路径跟踪法的计算步骤 201
9.2.4原-对偶可行路径跟踪法的流程图 201
9.2.5原-对偶可行路径跟踪法的MATLAB程序 201
9.2.6实例测试 205
9.3原-对偶非可行路径跟踪法 208
9.3.1原-对偶非可行路径跟踪法的基本原理 208
9.3.2原-对偶非可行路径跟踪法的计算步骤 211
9.3.3原-对偶非可行路径跟踪法的流程图 211
9.3.4原-对偶非可行路径跟踪法的MATLAB程序 211
9.3.5实例测试 215
9.4带预测校正的原-对偶路径跟踪法 218
9.4.1带预测校正的原-对偶路径跟踪法的基本原理 218
9.4.2带预测校正的原-对偶路径跟踪法的计算步骤 221
9.4.3带预测校正的原-对偶路径跟踪法的流程图 222
9.4.4实例测试 222
习题 226
第10章 二次规划问题的积极集法 228
10.1二次规划问题介绍 228
10.1.1二次规划问题的标准形式及在优化中的地位 228
10.1.2凸二次规划问题 229
10.2等式约束凸二次规划问题的解法 229
10.2.1问题形式 229
10.2.2基于SVD分解转化为无约束问题 230
10.2.3基于QR分解转化为无约束问题 231
10.2.4基于KKT条件求解 232
10.2.5等式约束凸二次规划问题的解法比较 232
10.2.6等式约束凸二次规划问题的QR分解法计算步骤 233
10.2.7等式约束凸二次规划问题的QR分解法流程图 233
10.2.8等式约束凸二次规划问题的QR分解法MATLAB程序 233
10.2.9实例测试 235
10.3凸二次规划问题的积极集法 236
10.3.1问题形式 236
10.3.2凸二次规划的积极集法原理 236
10.3.3利用辅助线性规划问题寻找初始可行点 237
10.3.4“构造问题”与最优解的判断准则 237
10.3.5“构造问题”的“等价问题” 238
10.3.6待求问题、“构造问题”、“等价问题”之间的关系 239
10.3.7寻找使目标函数值更优的可行点 240
10.3.8凸二次规划问题的积极集法的计算步骤 241
10.3.9凸二次规划问题的积极集法的流程图 241
10.3.10凸二次规划问题的积极集法MATLAB程序 242
10.3.11实例测试 246
习题 249
第11章 二次规划问题的内点法 250
11.1原-对偶非可行路径跟踪法 250
11.1.1凸二次规划问题的内点法 250
11.1.2凸二次规划问题的对偶问题与对偶间隔 250
11.1.3原-对偶非可行路径跟踪法的基本原理 252
11.1.4原-对偶非可行路径跟踪法的计算步骤 255
11.1.5原-对偶非可行路径跟踪法的流程图 255
11.1.6原-对偶非可行路径跟踪法的MATLAB程序 255
11.1.7实例测试 259
11.2带预测校正的原-对偶路径跟踪法 262
11.2.1带预测校正的原-对偶路径跟踪法的基本原理 262
11.2.2带预测校正的原-对偶路径跟踪法的计算步骤 265
11.2.3带预测校正的原-对偶路径跟踪法的流程图 265
11.2.4实例测试 266
习题 269
第12章 序列二次规划方法 271
12.1从序列无约束优化到序列二次规划 271
12.2等式约束非线性优化问题的局部SQP方法 272
12.2.1问题形式 272
12.2.2拉格朗日函数以及相关记号 272
12.2.3用牛顿法解待求问题的KKT条件 273
12.2.4 KKT条件的线性化 274
12.2.5 SQP方法的基本思想 274
12.2.6二次规划子问题的进一步讨论 275
12.2.7等式约束非线性优化问题的局部SQP方法计算步骤 275
12.2.8等式约束非线性优化问题的局部SQP方法流程图 276
12.2.9等式约束非线性优化问题的局部SQP方法MATLAB程序 276
12.2.10实例测试 278
12.3一般非线性优化问题的局部SQP方法 282
12.3.1问题形式 282
12.3.2拉格朗日函数以及相关记号 283
12.3.3 KKT条件的线性化 284
12.3.4二次规划子问题的进一步讨论 285
12.3.5一般非线性优化问题的局部SQP方法计算步骤 286
12.3.6一般非线性优化问题的局部SQP方法流程图 286
12.3.7一般非线性优化问题的局部SQP方法MATLAB程序 286
12.3.8实例测试 289
12.4扩展为全局SQP方法的难点及对策 292
12.4.1扩展局部SQP方法的难点 292
12.4.2拉格朗日函数Hesse矩阵的BFGS近似 292
12.4.3使二次规划子问题有唯一解 293
12.4.4效益函数与全局收敛性 293
12.4.5二次规划子问题的可行性保证 295
12.4.6 Maratos效应的克服 295
12.5一般非线性优化问题的全局SQP方法 298
12.5.1非线性优化问题的全局SQP方法 298
12.5.2非线性优化问题的全局SQP方法计算步骤 298
12.5.3非线性优化问题的全局SQP方法流程图 299
12.5.4实例测试 299
习题 303
参考文献 305
附录 优化程序基本调用方法及参数说明 309